Programmers

출처 에어컨 접근 문제 분석 에어컨을 켜서 온도를 설정하거나, 끄면서 차량의 온도를 조절하는데 최소의 비용이 들 수 있도록 해야 합니다. 탑승객이 존재할때만 온도가 유지되면 됩니다. 시간복잡도 분석 온도의 범위는 -10 <= temperature <= 40로, 전체 범위를 확인하는데 많은 시간복잡도가 필요하지 않습니다. 전체 탑승객의 정보(시간)인 onboard의 길이는 2 <= onboard.length <= 1,000으로, 전체 시간을 탐색하는데 O(N^3)의 알고리즘까지 사용이 가능합니다. 다만 온도 범위를 모두 탐색하는 것까지 고려하면 O(N^3)이하의 알고리즘이 필요합니다. 대부분의 완전탐색 알고리즘을 통해 문제를 해결할 수 있음을 알 수 있습니다. 공간복잡도 분석 시간복잡도와 마찬가지로, 공간복잡도는 고려하지 않아도 될 정도로 주어진 변수의 범위가 작은 편입니다. 풀이 DP 완전탐색을 구현하기 위해 DP를 사용했습니다. DFS로도 가지치기만 잘하면서 백트래킹하면 시간복잡도 내에 가능할 것으로 보이지만, DP가 구현이 더 쉽고 직관적이기 때문에 DP로 풀이했습니다. ...

출처 프로그래머스 봉인된 주문 접근 문제 분석 알파벳 순으로 정렬된 주문서에서 주어진 숫자(n)에 해당하는 주문서를 찾는 문제입니다. 이 때, 특정 주문(bans)이 삭제되어 있는 상태입니다. 시간복잡도 분석 주어진 숫자는 n = 10^15 인 long 타입의 숫자입니다. 따라서 해당 숫자에서 글자를 가져오는 알고리즘은 O(N)보다 작아야 합니다. 주어진 주문인 bans는 길이가 300,000이하입니다. 또한, 각 주문의 길이는 최대 11입니다. 모든 주문의 알파벳을 비교하기 위해서는 300,000 x 300,000(주문 간 비교) x 11(주문 길이) = 9x10^12 x 11 이므로 시간복잡도가 초과될 가능성이 있습니다. 따라서 전체 주문을 최대 O(NlogN)까지 확인할 수 있습니다. ...

출처 Programmers 불량 사용자(2019 카카오 개발자 겨울 인턴십) 접근 문제 분석 주어진 응모자 아이디에서 불량 사용자가 될 수 있는 모든 경우를 탐색하는 완전탐색(Brute Force) 문제입니다. 시간복잡도 분석 주어진 사용자 아이디와 조합의 개수가 n <= 8 이므로, 모든 경우를 선택하는 시간복잡도는 불량 사용자 조합의 크기인 8! = 40,302 가 됩니다. 또한, 모든 사용자와 조합을 각각 1회씩 비교할 경우 시간복잡도는 8 x 8 = 64입니다. 따라서 완전탐색을 구현하기만 하면 시간복잡도는 충분함을 알 수 있습니다. ...

출처 프로그래머스 GPS(2017 카카오코드 본선) 접근 문제 분석 오류가 발생한 택시의 경로를 최소한으로 수정하여 정확한 이동 경로를 구하는 문제입니다. 우선, 택시의 이동을 표현하기 위한 그래프 구조가 필요합니다. 문제에서 최소한으로 이동하는 경로를 찾기 위해서는 갈 수 있는 모든 경로에 대해 완전탐색을 수행해야 합니다. 시간복잡도 분석 완전탐색 전체 경우의 수를 BFS 또는 DFS를 활용해서 제한시간 내 목적지까지 갈 수 있는 모든 경로를 찾아서 주어진 경로와의 차이를 비교하는 방법이 있습니다. 이러한 경우, 한 거점에서 다음 거점으로 이동하는 경우의 수는 정점과 연결된 간선(m)만큼 곱해지게 됩니다. 정점(n = 200)과 간선(m = 10,000)이 균일하게 연결된 그래프로 가정하면 한 정점에 연결된 간선의 수가 50개이기 때문에, 전체 경우의 수는 정점 1개에 50개씩 증가하여 O(N) = 50 ^ 200이 됩니다. ...

출처 Programmers 자물쇠와 열쇠(2020 KAKAO BLIND RECRUITMENT) 접근 문제 분석 주어진 자물쇠와 열쇠를 이동시키고 돌려서 맞출 수 있는지 확인하는 문제입니다. 열쇠 혹은 자물쇠를 돌리는 로직과, 이동시키는 로직을 구현하면 됩니다. 문제에서 주어진 열쇠보다 자물솨의 크기가 작기 때문에, 자물쇠를 이동시키고 돌리는 식으로 구현하는 것이 더 효율적입니다. 모든 칸에 대해서 자물쇠를 돌리면서 맞추고, 이동하는 식으로 완전탐색을 진행합니다. 시간복잡도 분석 자물쇠와 열쇠의 크기는 M <= N <= 20이므로, 전체 칸의 개수는 M^2 <= N^2 <= 400입니다. ...

출처 프로그래머스 110 옮기기 접근 문제 분석 주어진 이진 문자열에서 110이라는 문자열을 이동시켜야 하는 문제입니다. 문자열에서 110을 제거한 뒤, 새로운 위치에 얼마나 빨리 삽입할 수 있는지가 포인트입니다. 주어진 문자열의 길이는 1,000,000으로, O(N)혹은 O(NlogN) 이내의 시간복잡도를 구현해야 합니다. 퓰이 우선 문제에서 주어진대로 110을 옮겨야 하기 때문에, 우선 110을 모두 제거하고 그 개수를 저장해야 합니다. 110 제거 그러나 문자열에서 110을 제거하는 과정이 만만치 않습니다. 문자열에서 단순히 110이라는 글자를 찾아 삭제하면 끝일 것 같지만, 다음과 같은 경우에는 한번에 끝나지 않습니다. 다음과 같이 문자열이 주어졌다고 가정해보겠습니다. 문자열에서 110을 제거하면, 다시 110이라는 문자열이 나타납니다. 따라서, 문자열에서 110이 나타나지 않을 때까지 110을 제거해야 합니다. 또한, 단순히 제거만 하는게 아니라 제거한 횟수를 별도로 저장해야 합니다. ...

출처 Programmers 표 병합(2023 KAKAO BLIND RECRUITMENT) 접근 문제 분석 표 편집 프로그램의 기능을 구현해야 합니다. UPDATE : 셀 1개의 값 바꾸기, 모든 셀의 값 찾아 바꾸기 MERGE : 셀 합치기(그룹화) UNMERGE : 셀 분리하기(그룹화 해제) PRINT : 셀 1개의 값 출력하기 표의 크기가 50 x 50이고, 명령의 길이가 1000 이하이므로, 시간복잡도는 충분한 편입니다. UPDATE는 비교적 쉽게 구현할 수 있지만, 문제의 이름처럼 표 병합을 얼마나 정확하고 빠르게 구현하는지가 중요한 문제입니다. ...

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

출처 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)의 잘린 개수는 다음과 같이 구할 수 있습니다. ...