Programmers

출처 Programmers 등산코스 정하기(2022 KAKAO TECH INTERNSHIP) 접근 문제 분석 산의 봉우리까지 이동하는 과정을 시뮬레이션 하는 문제입니다. Intensity는 이동 과정에서 가장 긴시간을 뜻합니다. 문제에서는 정상에 도착한 후, 다시 출입구로 돌아와야 한다고 했지만 올라갔던 길을 그대로 내려올 수 있기 때문에, 정상까지만 경로를 추적하면 됩니다. 따라서 각 출발지(Gate)에서 도착지(Summit)까지의 Intensity가 최소가 되도록 완전탐색을 수행해야 합니다. 조건 분석 문제에서 주어진 정점(Vertex)은 n = 50,000 이고 간선(Edge)은 paths = 200,000입니다. 탐색의 시작점이 최대 n이기 때문에, 각 간선을 1번씩만 방문하도록 최적화하면 시간복잡도 내 문제를 해결할 수 있습니다. O(N) = n + paths = 250,000 ...

출처 2024 KAKAO WINTER INTERNSHIP 산 모양 타일링 접근 시간복잡도 구하기 n <= 100,000 이므로 전체 타일의 개수는 최대 사다리꼴의 윗변의 모든 자리에 삼각형을 넣을 수 있으므로 2n + 1 + n <= 300,001개 입니다. 이러한 삼각형의 배치를 완전탐색으로 구하는 것은 불가능하기 때문에, DP를 통한 최적화가 필요합니다. 규칙성 찾기 예제의 타일을 1칸씩 세면서 경우의 수를 세면 규칙성을 확인할 수 있습니다. 다음과 같이 (1 ~ 9) 순으로 예제타일의 규칙성을 구해보겠습니다. ...

출처 프로그래머스 멀쩡한 사각형 접근 규칙을 알고 나면 구하기 쉽지만, 모르면 생각보다 까다로운 문제입니다. 규칙 구하기 주어진 예시 (w = 8, h = 12)에 대해 규칙을 확인해보겠습니다. 문제의 예시를 자세히 보면 작은 사각형이 반복되는 것을 알 수 있습니다. w = 8과 h = 12의 최대공약수인 4개의 사각형이 생성됩니다. 즉, 최대공약수로 해당 길이를 나누었을 때 생성된 작은 사각형의 잘린 개수를 구하면 됩니다. 최대공약수로 나눠진 사각형(nw x nh = 2 x 3)의 잘린 개수는 다음과 같이 구할 수 있습니다. ...

출처 수식 최대화(2020 KAKAO Internship) 접근 완전탐색(DFS) 각 연산자의 우선순위를 변경하면서 전체 탐색을 하고, 변경된 우선순위마다 수식을 계산해서 최댓값을 갱신합니다. 연산자 순서에 따라 결과가 달라지므로, 순열(Permutation)에 해당합니다. 다양한 구현방법이 있지만, 개인적으로 다양한 조건을 만족하는 순열(조합)을 빠르게 구현할 수 있는 DFS를 선호합니다. 3가지 연산자만 있으므로, 모든 경우의 수를 구해도 6가지이기 때문에 시간복잡도는 충분합니다. 후위 표기 변환(InFix to PostFix) 보통 사람이 계산을 할 때는 A + B * C의 형태로 수식을 써서 계산을 합니다. 이 때, A와 B 사이에 연산자가 있는 형태를 중위 표기(InFix)라고 합니다. ...

출처 2021 KAKAO BLIND RECRUITMENT 순위 검색 접근 와일드카드 검색 와일드카드(-) 없이 검색을 구현하는 것은 각 지원자의 속성에 코딩테스트 점수를 저장하면, 속성별로 검색이 가능하기 때문에 큰 어려움이 없습니다. 와일드카드가 없는 상황은 다음과 같이 트리 구조로 데이터를 저장할 수 있습니다. 트리 구조로 지원자 정보를 저장합니다. 리프 노드에는 리스트로 코딩테스트 점수를 저장합니다. 하지만, 문제에서 주어진 것처럼 쿼리 시 와일드카드가 나오면 모든 정보를 포함하도록 탐색을 해야 하기 때문에 이를 구현하기 위해 별도의 공간에 와일드카드 속성들을 저장해야 합니다. ...