[프로그래머스][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] 단어 변환
문제를 정리해보자. 시작단어, 목표단어, 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로 제거할 수 있는 모든 경우의 수를 찾고, 경우마다 최솟값을 찾으려 하면 시간초과가 난다. 그렇다면 어떻게 해야 할까? 모든 경우의 수를 보지 않고, 바위를 제거하는 방법을 찾아야 한다. 최솟값을 지정하면 된다...
