Go Gradually - Repository

사라지는 발판 - 2022 KAKAO BLIND RECRUITMENT

문제 링크 상태 전이 개념 + 백트래킹 알고리즘의 적용을 학습하기 좋았던 문제였기에 이렇게 포스트로 기록해둔다. 이 문제를 읽어보고 나면, 전형적인 게임 이론 문제로 보인다. 게임 이론 문제에는 크게 두가지 접근 방식이 있다.게임 로직으로 인해 게임 시작 시 바로 결정되는 승자와 패자를 파악하고, 승자와 패자가 각자의 전략에 맞춰 최적으로 행동하는 방법상태 기계를 설계해, 서로간에 최적의 행동을 직접 수행시켜보고, 행동했을 때 자신이 얻을 수 있는 결과 중 최적을 반환하는 방법 이 문제의 경우, 게임 시작 시 바로 결정되는 승자와 패자를 파악하기 어려웠다. 따라서 직접 시뮬레이션해보는 두 번째 접근 방식으로 자연스레 손이 가게 되는데,이러면 -> 내가 이기는 경우, 가장 빨리 끝나는 결과를 알아둔다..

개인적으로 모빌리티 도메인에 관심이 있어 이쪽으로 지원했는데, 카카오라는 그룹 이름에 걸맞게 재밌고 수준높은 문제가 출제되었다.1번문자열 검사 문제였다.2번 for문을 돌면서 Set을 통해 중복을 제거하면 해결할 수 있는 문제였다.2번사이클 내 모두 같은 값을 갖게 되는 최소시간을 탐색하는 문제였다lcm으로 제한을 걸면 100만 내 사이클이 끝나기 때문에, 이를 이용해 푸는 문제였다.척 보고 바로 안건 아니고, 편집기 내에서 print 문으로 직접 찍어 확인했다.3번나한테는 이게 제일 골치 아팠다.이 문제에만 2시간 10분을 사용했다.최대 높이가 하나라도 높아지는 순간에 분배도가 올라간다.같은 높이에선 분배 노드가 추가되더라도 분배도는 달라지지 않는다.선택한 건기본 트리 구성: 완전탐색리프 노드 추가: ..

위상 정렬이란, Directed Acyclic Graph(DAG)의 정점들을 각 정점이 자신의 자식 정점들보다 먼저 방문되도록 나열하는 것을 의미한다.방향 그래프(directed graph)는 간선을 한쪽 방향으로만 이동할 수 있는 그래프를 의미한다.또한 비순환 그래프(acyclic graph)는 순환(cycle)을 포함하지 않는 그래프를 의미한다.이는 하나 이상의 간선을 따라가서 출발한 정점으로 다시 돌아올 수 없는 구조를 말한다.이 두 정의를 합치면, 방향 비순환 그래프(directed acyclic graph, 줄여서 DAG)는 간선을 한쪽 방향으로만 이동할 수 있고 순환을 포함하지 않는 그래프이다.위상 정렬 (Topological Sort) - Course Schedule다음 문제를 풀어보자. C..

그래프에 간선을 추가하고 그래프의 두 정점이 연결되어 있는지 검사할 수 있게 해 주는 자료구조가 분리 집합(DSU, Union-Find) 이다.USACO.guide는 알고리즘의 원리와 정의보단 어떻게 이 정의를 떠올릴 수 있는지에 집중한다.알고리즘의 원리와 정의가 중요하지 않다는 뜻이 아니다.실제 Union-find의 원리와 관련된 내용은 다음 링크를 참고 바란다. CS Academy csacademy.com 구현(Implementation)import java.util.*;public class DisjointSets { int[] parents; int[] sizes; public DisjointSets(int size) { parents = new int[size]; ..

공식 풀이는 다음 링크를 통해 확인하실 수 있습니다.https://tech.kakao.com/posts/567 2023 카카오 신입 공채 1차 온라인 코딩 테스트 for Tech developers 문제해설 - tech.kakao.com2023 KAKAO BLIND RECRUITMENT 1차 코딩 테스트가 지난 9월...tech.kakao.com 카카오 공채도 썼겠다, 지난 카카오 공채의 코딩테스트 문제도 풀어보고, 프로그래머스 환경도 체험해보고자 프로그래머스에 존재하는 카카오 2023 블라인드 공채에 출제되었던 문제를 5시간동안 풀어보았다. 5시간동안 5문제를 풀었는데, 문제가 복잡해졌을 때 생각을 키보드로만 정리하는 과정이 좀 고되긴 하다.그림같은 걸 그릴 수 있을 수 있으면 좋을텐데, 이건 코테 환..

문제를 해설할 때 특수한 DP로 카데인을 자주 언급하게 되는데,카데인 알고리즘이 정확히 어떤 이점이 있는지, 다른 DP와는 무엇이 다른지 명확히 설명한 글이 없어 이렇게 글을 작성한다. 핵심 아이디어는 다음과 같다.dp[i]: 반드시 i에서 끝나는 최대 부분 배열 합즉, 한쪽 끝을 고정함으로써 중간의 연산을 최적 부분구조 + 중복 부분 문제의 형태로 만드는 아이디어가 핵심이다. 그러면 이 문제에서 전체 정답은 max_i dp[i] 가 된다.마지막 원소 a[i]를 포함해야 하므로 두 선택지뿐이다.a[i] 혼자로 새로 시작한다.i−1에서 끝나는 최적해 dp[i−1]에 a[i]를 이어붙인다.따라서 점화식은 다음과 같다.초기값이 점화식은 “끝이 i인 최적해”의 정의에서 바로 나온다.아이디어임의의 최적 부분 배..

배낭(knapsack) 문제는 보통 제한된 용량의 컨테이너에 물건들의 부분집합을 넣되, 물건과 관련된 어떤 양을 세거나(카운트) 최적화하는 문제를 다룬다.거의 항상 각 물건은 양의 무게를 가지며, 우리가 선택한 물건들의 총 무게는 어떤 수로 주어지는 컨테이너의 용량을 초과해서는 안 된다. 배낭 유형 문제의 변형으로는 다음과 같은 것들이 있다.0/1 배낭 문제: 물건들의 부분집합을 골라 총 가치를 최대화하되, 총 무게가 컨테이너의 용량을 넘지 않도록 한다.가능한 총 무게 찾기: 컨테이너 용량을 넘지 않게 임의의 부분집합으로 만들 수 있는 모든 총 무게를 구한다.정확히 채우는 경우의 수 세기: 총 무게가 정확히 컨테이너 용량이 되도록 하는 물건의 순서열이 몇 개인지 센다(순서가 중요할 수도 있고 중요하지 않..

사실 '다이나믹'도 아니고, '프로그래밍'도 아닌 다이나믹 프로그래밍은 알고리즘 문제의 단골 요소이자 매우 효율적인 컴퓨터공학의 계산 효율화 방법이다.DP는 벨만-포드 알고리즘과 벨만 방정식, 강화학습의 토대를 마련한 미국의 응용수학자 리처드 E. 벨만이 발견했다. 이는 리액트의 렌더링 및 BFS, 캐싱, 비즈니스 로직 및 게임 엔진 최적화부터 심지어는 RL에까지 등장하고 있다. 이 DP에 대해, 지금부터 차근차근 알아보자.DP의 성질은 딱 두가지로 정리가 가능하다최적 부분구조중복 부분문제최적 부분구조최적 부분구조(Optimal Substructure)은 "경로에 관계없이" 다음 문제의 해답이 이전 부분문제의 최적화로 구해지는 구조를 의미한다.이를 다르게 표현하면, 뒷 문제의 정답을 구하는 과정이 앞 문..

모듈러 연산에서는 정수 그 자체로 계산하지 않고, 어떤 수를 m으로 나눈 나머지로 계산한다.이를 "모듈러 m을 취한다”라고 부른다. 예를 들어 m=23이라면, x=247 대신 x  mod  23=17을 사용한다.보통 m은 문제에서 주어지는 큰 소수(prime)이며, 가장 흔한 값은1000000007998 244 353=119⋅2^23+1이다.모듈러 산술은 내장 자료형의 범위를 넘는(오버플로) 큰 수를 다루지 않기 위해 사용되며, 다음 공식을 이용해 나머지를 취할 수 있다.Modular Exponentiation (모듈러 거듭제곱)거듭제곱 (Easy)https://cses.fi/problemset/task/1095 CSES - ExponentiationCSES - Exponentiation Time lim..

이와 같은 수학 문제는 코딩 테스트에는 잘 출제되지 않기 때문에 건너뛰는 사람들도 많지만,나는 시간복잡도 계산에 가장 강력한 인사이트를 부는 내용이 바로 이 수학 부분이라고 생각한다.그래서 이 수학 파트도 건너뛰지 않고 어느정도 설명을 진행하도록 하겠다.소인수분해 (Prime Factorization)양의 정수 a가 음이 아닌 정수 b의 약수(divisor) 또는 인수(factor)라고 불리는 것은, b가 a로 나누어떨어진다는 의미이다. 즉, 어떤 정수 k가 존재하여 b = ka가 되는 경우이다.정수 n > 1이 소수(prime)라는 것은 그 약수가 1과 n뿐일 때를 말한다.1보다 큰 정수 중 소수가 아닌 수는 합성수(composite)라고 한다. 모든 양의 정수는 유일한 소인수분해를 가진다. 즉, 소수..