본문 바로가기

전체 글

 (171)
[프로그래머스][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 # ..

티스토리툴바