본문 바로가기

알고리즘/프로그래머스

(45)
[프로그래머스][Python] 등굣길 문제를 정리해보자. m x n 크기의 격자 모양이 있다. (1, 1)에는 집이 있고, (m, n)에는 학교가 있다. 일부 칸은 물에 잠겨 있다. 물에 잠긴 칸은 지나갈 수 없다. 집에서 학교까지 갈 수 있는 최단 경로의 개수를 구하자. 단, 이동은 오른쪽과 아래쪽만 가능하다. 풀이를 생각해보자. 이동은 무조건 오른쪽과 아래쪽으로만 가능하다. 따라서 어떻게 가도 최단 경로이다. 오른쪽 그림을 보자. 각 좌표까지의 최단 경로를 나타냈다. 마지막 (m-1, n-1)는 위에서 2가지, 왼쪽에서 2가지로 경로가 총 4가지이다. ((0, 0)이 시작이라고 잡았기 때문에 도착은 (m-1, n-1)이다.) 구현해보자. BFS를 이용해서 (0, 0)부터 인접한 좌표로 이동하게 했다. 다만, check리스트를 이용해서 방..
[프로그래머스][Python] 정수 삼각형 문제를 정리해보자. 위와 같은 삼각형이 있다. 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾으면 된다. 이동할 때는 대각선 방향으로 한 칸 왼쪽 또는 오른쪽으로만 이동할 수 있다. 예) 3에서는 8또는 1로만 이동할 수 있다. 풀이를 생각해보자. 거쳐 간 숫자의 합이 가장 크도록 그렸다. 사진을 보면 알 수 있다. 대각선의 값은 현재 수의 누적값 + 다음 수이다. 다음 수를 기준으로 왼쪽 대각선에서 오는 값과 오른쪽 대각선에서 오는 값 중 큰 값이 다음 수의 누적값이 된다. 예) 1은 왼쪽 대각선에서 오는 값이 11, 오른쪽 대각선에서 오는 값이 16이다. 따라서 16을 선택한다. 이것은 1의 누적값이 된다. (구현할 때는 왼쪽 값을 먼저 저장하고, 오른쪽 값이 왔을 때 ..
[프로그래머스][Python] 단어 변환 문제를 정리해보자. 시작단어, 목표단어, words가 주어진다. 시작단어를 목표단어가 되도록 변환해야 한다. 아래와 같은 규칙으로 단어를 변환할 수 있다. 시작단어가 목표단어가 되기 위해 몇 단계가 필요한가? 프로그래머스에 있는 예를 보자. 시작단어 : "hit" 목표단어 : "cog" words : ["hot","dot","dog","lot","log","cog"] "hit" -> "hot" -> "dot" -> "dog" -> "cog" 이렇게 4단계가 필요하다. 풀이를 생각해보자. 위의 예에서, 자리 별로 바꿀 수 있는 알파벳을 생각해보자. 첫 번째 : h, d, l, c 두 번째 : o 세 번째 : t, g 변환해보자. 지금단어 : hit 첫 번째 변환 : hit, dit, lit, cit, 두 ..
[프로그래머스][Python] 네트워크 문제를 정리해보자. A와 B가 직접적으로 연결되어 있고 B와 C가 직접적으로 연결되어 있다면, A와 C는 간접적으로 연결된 것이다. 따라서 A, B, C 모두 연결되어 있다. 이를 모두 같은 네트워크상에 있다고 한다. 몇 개의 네트워크가 있는지 구하는 문제이다. 제한사항과 입출력 예를 보자. [[1, 1, 0], [1, 1, 0], [0, 0, 1]]은 양방향이다. 표로 나타내면 아래와 같다. 1이면 길이 있고, 0이면 길이 없다. 풀이를 생각해보자. 예를 들어보자. 노드는 12개이다. 네트워크는 3개이다. 시작노드 0번을 연결된 노드를 확인한다. 0번 -> 1번 -> 2번 -> 5번 -> 7번 -> 6번 -> 3번 -> 4번 이렇게 직접적으로 연결된 부분을 확인한다. (DFS) 다음 시작노드는 1번이다..
[프로그래머스][Python] 타겟 넘버 문제를 정리해보자. n개의 음이 아닌 정수가 있다. 이 수들을 적절히 더하거나 빼서 원하는 숫자를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들어보자. 위와 같이 5가지 방법이 있다. 주의해야 할 점은 연산순서가 바뀐다고 경우의 수가 늘어나지 않는다. 예를 들어 [1, 2, 3]으로 -6을 만든다고 해보자. -1-2-3, -2-1-3, -3-2-1등 다 같은 경우이다. 풀이를 생각해보자. 예를 들어 [1, 1, 2, 3]을 가지고 있다고 해보자. 1. 시작은 1, 2, 3중 하나로 잡는다. (사진에서는 1로 잡았다. 하나를 잡아야 중복되는 결과가 나오지 않는다.) 2. 누적값에 해당 수로 +와 -연산한다. (누적값이 없다면 0으로 시작) 3. 그 값을 누적시킨다. 4. 잡지 않..
[프로그래머스][Python] 징검다리 문제를 정리해보자. 1. n개의 바위를 제거한다. 2. 출발지점, 도착지점, 바위 간의 거리를 구한다. 3. 거리의 최솟값을 구한다. n개의 바위를 제거하는 경우의 수만큼 최솟값이 여러 개 나온다. 그중에 최댓값이 정답이다. 풀이를 생각해보자. 문제에 나와 있는 예를 보자. 출발지점 : 0, 바위지점 : [2, 11, 14 , 17, 21], 도착지점 : 25 => [0, 2, 11, 14, 17, 21, 25] 제거해야 하는 바위 개수 : 2 바위는 최대 50,000개이다. 50,000 C 2로 제거할 수 있는 모든 경우의 수를 찾고, 경우마다 최솟값을 찾으려 하면 시간초과가 난다. 그렇다면 어떻게 해야 할까? 모든 경우의 수를 보지 않고, 바위를 제거하는 방법을 찾아야 한다. 최솟값을 지정하면 된다...
[프로그래머스][Python] 체육복 문제를 정리해보자. 여벌의 체육복을 가지고 있는 학생은 체육복이 없는 학생에게 빌려줄 수 있다. 단, 양옆의 학생에게만 빌려줄 수 있다. 하지만 여벌의 체육복을 가지고 있는 학생이 체육복을 도난당했다면 빌려줄 수 없다. (자신이 사용해야 하기 때문이다.) 체육복이 있어야 체육수업을 들을 수 있다. 체육수업을 들을 수 있는 학생의 최댓값을 구해야 한다. 풀이를 생각해보자. 1) 도난당한 학생 => 체육복이 없다. 2) 도난당한 학생이며 여벌이 있는 학생 => 체육복이 있다. 빌려줄 체육복이 없다. 3) 여벌이 있는 학생 => 체육복이 있다. 빌려줄 체육복도 있다. 3번 학생만 1번 학생을 빌려주면 된다. 구현해보자. # 전체 학생의 수 : n # 도난당한 학생들의 번호가 담긴 배열 : lost # 여벌의 ..
[프로그래머스][Python] 섬 연결하기 문제를 정리해보자. n개의 섬 사이에 다리를 건설하는 비용이 주어진다. 최소의 비용으로 모든 섬이 통행 가능하도록 만든다. 따라서 최소 비용이 얼마인지 구해야 한다. 풀이를 생각해보자. 모든 섬을 방문한다. 그런데 최소 비용으로 방문한다. 최소 신장 트리이다. 구현해보자. 프림 알고리즘을 이용하자. import heapq def solution(n, costs): graph = [[] for _ in range(n)] for li in costs: graph[li[0]].append([li[2], (li[0], li[1])]) graph[li[1]].append([li[2], (li[1], li[0])]) count = 0 # 방문 노드 개수 dp = [0] * n # 방문 노드 result = 0 # ..
[프로그래머스][Python] 큰 수 만들기 문제를 정리해보자. 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하자. 예) 1924에서 2개를 제거하면 19, 12, 14, 92, 94, 24이다. 여기서 가장 큰 수는 94이다. 풀이를 생각해보자. '가장 큰 수'를 만들려면 어떻게 해야 할까? 앞자리에 큰 수가 있어야 한다. 따라서 k개만큼 제거하되 앞자리일수록 큰 수가 와야 한다. 1) 1924를 예로 들어보자. (k = 2) 9는 1보다 크다. 따라서 1보다 앞에 위치해야 한다. 따라서 1을 제거하고 9를 앞에 위치시킨다. 이제 제거할 수 있는 수는 1개이다. (결과 : 924) 4는 2보다 크다. 따라서 2보다 앞에 위치해야 한다. 따라서 2를 제거하고 4를 앞에 위치시킨다. 이제 제거할 수 있는 수는 0개이다. (..
[프로그래머스][Python] 구명보트 문제를 정리해보자. 구명보트를 이용해 모두를 탈출시켜야 한다. 구명보트에는 최대 2명이 탑승한다. 탑승자의 무게 합이 제한을 초과하면 안 된다. 모든 사람을 구출하는 데 필요한 구명보트의 최솟값을 구해야 한다. 풀이를 생각해보자. 1. 두 사람이 타는 경우 (가장 무거운 사람 + 가장 가벼운 사람)이 무게 제한을 초과하지 않으면 둘 다 태운다. 한 번 태운 사람은 두 번 다시 태우지 않는다. 2. 한 사람이 타는 경우 (가장 무거운 사람 + 가장 가벼운 사람)이 무게 제한을 초과한다면, 가장 무거운 사람만 태운다. 3. 마지막 사람 50은 70, 80이 나갔기 때문에 배열에 혼자 남겨졌다. 따라서 가장 무거운 사람도 아니고, 가장 가벼운 사람도 아니다. 이 경우는 '마지막 사람'이라고 생각한다. 그냥 내..