[Programmers] Level 3

문제 목록 바로가기 : https://programmers.co.kr/learn/challenges

섬 연결하기

Link : https://programmers.co.kr/learn/courses/30/lessons/42861

solution

그냥 크루스칼로 풀면 되지 않을까? 라고 시작했는데 모든 섬의 경로를 더할 방법을 떠올리기가 힘들었다.
결론적으로는 최소 스패닝 트리(MST)를 이용했다.
BOJ 1922: 네트워크 연결과 같은 문제.

단속카메라

Link : https://programmers.co.kr/learn/courses/30/lessons/42884

solution

union-find로 해결했다. 되게 간단해 보였지만 머리를 좀 굴려야 했다..
대부분 스위핑 문제가 그렇듯이 시작점과 끝점을 분리해서 정렬하고 시작한다.
시작점만 연달아 나온다면 같은 집합으로 묶는다.
끝점이 나온다면 그 점이 속한 집합이 체크되지 않았다는 가정하에
해당되는 집합을 체크하고 답을 +1, 부모를 초기화한다.

정수 삼각형

Link : https://programmers.co.kr/learn/courses/30/lessons/43105

solution

현재 위치가 \((x, y)\)라면 대각선 왼쪽, 오른쪽은 각각 \((x+1, y), (x+1, y+1)\)이다.
점화식은 다음과 같다.
\(f(x, y) = max(f(x+1, y), f(x+1, y+1)) + triangle[x][y]\)

여행경로

Link : https://programmers.co.kr/learn/courses/30/lessons/43164

solution

맵을 사용하면서 조금 난잡해진 감이 있지만.. 그래도 어떻게 비비다보니 통과했다.
일단 모든 공항이 문자열이므로 이 문자열 자체만으로는 인덱스로 활용할 수가 없어서 맵을 이용했다.
모든 티켓을 사용하는게 목적이므로 티켓에 적힌 공항 정보를 숫자로 매핑시키고 서로 연결한 후
DFS를 통해 모든 이웃으로 이동하도록 했다.
처음에 visited(chk)를 공항 넘버로 각각 설정했는데 자꾸 오류가 떴었다. ㅠㅠ
같은 정보가 든 티켓이 들어있을 수 있기 때문에 그렇다고 한다. 때문에 chk[공항넘버][티켓넘버]로 설정했다.

이중우선순위큐

Link : https://programmers.co.kr/learn/courses/30/lessons/42628

solution

특정 숫자를 삽입, 최대/최솟값 삭제 등의 쿼리를 처리하면 되는 문제.
최대/최솟값을 O(1)만에 찾고 삭제할 수 있으려면 정렬된 상태로 유지해야 한다.
들어오는 값을 이분 탐색해서 넣든 들어올 때마다 정렬을 하든 상관없다.
정렬된 상태만 유지한다면 상관없으므로 set을 이용해 풀었다.

베스트앨범

Link : https://programmers.co.kr/learn/courses/30/lessons/42579

solution

주어진 조건에 맞춰서 정렬을 해서 앨범당 2곡을 담으면 된다.
크게 설명할게 없는 문제.

등굣길

Link : https://programmers.co.kr/learn/courses/30/lessons/42898

solution

단순한 DP 문제다.
이동 가능한 방향, 이동 불가능한 위치들이 정의 돼있으므로
이에 맞춰 이동 가능한 모든 방향을 탐색한다.
범위에서 벗어나는지도 꼭 체크해주자.

보행자 천국

Link : https://programmers.co.kr/learn/courses/30/lessons/1832

solution

현재 위치에 해당되는 값이 2일 때 이전에 향했던 방향을 고려해주면 된다.
이 부분만 제외한다면 간단한 DP문제다. 인자가 3개가 되는게 포인트.