[BOJ] 2025 실골랜디
Gold Random Defense
💻250101~250110 (골5~골4)
1. 창영이와 퇴근 (골4) 22116
다익스트라
다익스트라는 INF로 배열을 만든 후 더 작은 값이 있으면 갱신해준다.
visited 필요 없는 이유: height[x][y]가 c보다 작으면 이미 방문을 한 것이므로 height로 방문 여부를 대체 할 수 있다.
A[nx][ny]로 가는 최대 경사를 구한 후 new_cost가 현재 height[nx][ny]보다 작으면 갱신한 후 heap에 넣는다.
2. 시간낭비 (골2) 30464
DP
a[i]이 0이면 같은 공간에 계속 갈 수 있다. 이때 예외처리를 해주어야 한다.
1)앞으로, 2)뒤로, 3)앞으로 가면서 dp 계산을 해주는데 최댓값으로 계속 갱신하면 된다.
3. 최소비용 구하기 (골5) 1916
다익스트라
전형적인 다익스트라 문제이다.
answer에는 누적된 값이 들어가기 때무에 INF를 100,000이 아니라 매우 큰 수로 초기화해야 한다.
최소 힙에 (가중치, 출발지)을 넣는다. 이미 최솟값이면 연산을 건너뛴다. 아니라면 graph에서 도착지를 찾아 갱신 해준 후 힙에 넣는다.
4. 백도어 (골5) 17396
다익스트라
A[i]가 0인 곳만 갈 수 있으므로 26, 27번째 줄을 추가해준다.
나머지는 다익스트라 코드와 동일
5. 미로만들기 (골4) 2665
다익스트라
검정을 만나면 가중치를 +1 해준다.
가중치가 현재 값보다 작으면 갱신한 후 힙에 추가한다.
6. 호석이 두 마리 치킨 (골5) 21278
플로이드 워셜
Dijkstra: 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.
Floyd Warshall: 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.
주의할 점: 음수 간선은 없고 자기 자신 노드로 가는 최솟값이 0이기 때문에 미리 0으로 초기화해줘야 한다.
임의 두 개의 행을 뽑아 각 열 최솟값들의 합으로 total을 만든다. 왕복이므로 그 total의 두 배가 답이 된다.
플로이드 워셜 출력 결과
9223372036854775807 0 2 1 3 3
9223372036854775807 2 0 1 1 1
9223372036854775807 1 1 0 2 2
9223372036854775807 3 1 2 0 2
9223372036854775807 3 1 2 2 0
(건물1, 건물2, 최솟값 배열, total) 출력 결과
1 2 [0, 0, 1, 1, 1] 3 # 정답: 1 2 6
1 3 [0, 1, 0, 2, 2] 5
1 4 [0, 1, 1, 0, 2] 4
1 5 [0, 1, 1, 2, 0] 4
2 3 [1, 0, 0, 1, 1] 3
2 4 [2, 0, 1, 0, 1] 4
2 5 [2, 0, 1, 1, 0] 4
3 4 [1, 1, 0, 0, 2] 4
3 5 [1, 1, 0, 2, 0] 4
4 5 [3, 1, 2, 0, 0] 6
7. 알고스팟 (골4) 1261
다익스트라
백도어와 풀이 동일
8. 특정한 최단 경로 (골4) 1504
다익스트라
시작하는 곳으로 다익스트라 결과 배열을 생성한 후 거기서 종료 지점을 인덱스로 추출해서 쓸 수 있다.
따라서 answer를 return하고 종료 지점을 바꿔가며 result를 구하면 된다.
💻250111~250120 (골5~골2)
1. 네트워크 복구 (골2) 2211
다익스트라
answer는 [C, A, B]인 배열이다.
new_C가 원래 answer C보다 작으면 answer의 값을 갱신하고 힙에 추가한다.
최종 answer 2부터 N까지의 [A, B]을 출력하는 문제이므로 K는 무조건 N-1이 된다.
K > N-1: 최소 개수를 복구하는 것이 아니다.
K < N-1: 작으면 1번 컴퓨터에서 도달할 수 없는 존재한다. 이는 문제 조건과 맞지 않는다.("통신 가능하도록 복구한다.")
2. 입국심사 (골5) 3079
이분탐색
현재 mid로 T[i]를 나눈 몫을 다 더해서 그것이 M보다 크거나 같으면 answer를 갱신한다.
3. 타임머신 (골4) 11657
벨만포드
음의 간선이 포함된 상황에서도 사용 가능, 음수 간선 순환을 감지할 수 있다.
모든 간선을 모든 노드만큼 확인한다. → O(VE)
다익스트라와 다르게 모든 간선을 순회하기 때문에 start와 이어져 있는지 판단하기 어렵다.
따라서 if문에 'dist[cur] != INF'을 추가하여 start와 이어져 있는 곳의 노드만 갱신할 수 있다.
마지막 노드에서도 값이 갱신된다면 음수 순환이 존재하는 것이다.
4. 웜홀 (골3) 1865
벨만포드
출발 지점이 정해져있지 않기 때문에 음수 순회가 존재하면 "YES"를 출력한다.
그렇게 때문에 dist[start]를 초기화하지 않아도 되고, "!=INF"라는 조건이 없어도 된다.
5. 중량제한 (골3) 1939
다익스트라
지금까지 경로의 최소 중량을 구한다.
그 최소 중량이 dist[도착노드]보다 크다면 dist를 갱신하고 힙에 추가한다.
dist는 최대한 큰 값이어야 하므로 최대힙으로 구한다. 즉, a노드로 가는 새로운 중량이 dist[a]보다 작으면 갱신하기 않아도 된다.
💡 핵심은 중량 최소의 최대를 구하는 것
💻250301~250331 (골5~골2)
1. 1학년 (골5) 5557
DP
0~20까지이기 때문에 dp를 Nx21로 정의하고 풀면 된다.
이전까지의 개수를 현재 dp에 계속 더해서 푸는 방식이다.
[예제 입력 1] dp 출력 결과
11
8 3 2 4 8 7 2 4 0 8 8
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0]
[0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
[0, 0, 1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 2, 0, 0, 0, 1, 0, 1, 0, 1]
[1, 0, 1, 0, 2, 0, 3, 0, 3, 0, 4, 0, 2, 0, 3, 0, 1, 0, 2, 0, 1]
[2, 0, 3, 0, 4, 0, 5, 0, 4, 0, 6, 0, 4, 0, 6, 0, 3, 0, 3, 0, 1]
[4, 0, 6, 0, 8, 0, 10, 0, 8, 0, 12, 0, 8, 0, 12, 0, 6, 0, 6, 0, 2]
[8, 0, 12, 0, 8, 0, 12, 0, 10, 0, 12, 0, 10, 0, 10, 0, 8, 0, 12, 0, 8]
10
2. 1, 2, 3 더하기 5 (실1) 15990
DP
1, 2, 3 개수를 저장하는 배열이 있어야 하므로 2차원 dp이다.
연속된 숫자가 나오면 안 되므로 dp[i][1]은 dp[i-1][2]와 dp[i-1][3]을 더한 값이다.
마찬가지로 dp[i][2]는 i-2번째의 1과 3을 더한 값이다.
숫자가 나타내는 것은 무엇일까? 가지치기의 첫 번째 숫자이다.
4는 (1,3), (1,2,1), (3,1)로 나타낼 수 있다.
이때 1로 시작하는 것이 2개, 3으로 시작하는 것이 1개라서 dp[4]가 [2, 0, 1]이 되는 것이다.
dp[10]까지 출력
0 [0, 0, 0, 0]
1 [0, 1, 0, 0]
2 [0, 0, 1, 0]
3 [0, 1, 1, 1]
4 [0, 2, 0, 1]
5 [0, 1, 2, 1]
6 [0, 3, 3, 2]
7 [0, 5, 2, 2]
8 [0, 4, 5, 3]
9 [0, 8, 7, 6]
10 [0, 13, 7, 7]
3. 트리와 쿼리 (골5) 15681
트리+DP
트리와 DP를 합친 문제이다. 즉, size가 DP가 되는 것
1. makeTree로 childNode를 저장하는 배열을 만든다.
2. countSubtreeNodes로 현재 노드의 서브 트리 노드 개수를 size에 저장한다.
※ 리프 노드부터 계산하며, 자식size+1로 계산하는 것을 알 수 있다.
[예제 입력 1] currentNode와 size 출력 결과
5
4
3
1
1 [0, 1, 0, 1, 1, 1, 0, 0, 0, 0]
2
2 [0, 1, 1, 2, 1, 1, 0, 0, 0, 0]
3 [0, 1, 1, 3, 1, 1, 0, 0, 0, 0]
4 [0, 1, 1, 3, 4, 1, 0, 0, 0, 0]
6
7
7 [0, 1, 1, 3, 4, 5, 1, 1, 0, 0]
9
9 [0, 1, 1, 3, 4, 5, 2, 1, 0, 1]
8
8 [0, 1, 1, 3, 4, 5, 3, 1, 1, 1]
6 [0, 1, 1, 3, 4, 5, 4, 1, 1, 1]
5 [0, 1, 1, 3, 4, 9, 4, 1, 1, 1]
4. 트리 노드 합의 최댓값 (골4) 25515
트리+DP
트리와 DP를 합친 문제이다.
1. 단방향 그래프이기 때문에 graph는 자식만 갖고 있다.
2. 리프 노드부터 돌면서 "현재 노드"와 "현재 노드+자식 노드" 중 큰 수를 현재 노드로 갱신한다.
※ 리프 노드부터 계산하며, 자식size+1로 계산하는 것을 알 수 있다.
[예제 입력 1] dp 출력 결과
[1, -5, 0, -1, 0, 0, 0, 0]
[1, -5, 0, -1, 10, 0, 0, 0]
[1, 5, 0, -1, 10, 0, 0, 0]
[6, 5, -10, -1, 10, 20, 0, 0]
[6, 5, 10, -1, 10, 20, -5, 20]
[6, 5, 10, -1, 10, 20, 15, 20]
[6, 5, 25, -1, 10, 20, 15, 20]
[31, 5, 25, -1, 10, 20, 15, 20]
5. 사회망 서비스(SNS) (골3) 2533
트리+DP
트리와 DP를 합친 문제이다.
1. dp가 1이면 얼리 아답터이고, 0이면 얼리 아답터가 아니다. 초깃값은 0이다.
2. 자식 노드를 보면서 자식 모든 노드가 얼리 아답터이면 부모는 얼리 아답터가 아니라. 자식 노드 중 하나라도 얼리 아답터가 아니면 부모는 얼리 아답터가 된다.
3. 그 계산은 "max(1-dp[node], dp[current])"이다. 0이 하나라도 있으면 "1-dp[node]"에 의해 dp[current]는 1이 되고, 한 번 1이 되면 max 함수가 있어 계속 1이 된다.
[예제 입력 1] dp 출력 결과
• 5, 6 -> 2가 얼리 아답터됨
• 3 -> 1이 얼리 아답터됨
• 7, 8 -> 4가 얼리 아답터됨
[0, 1, 1, 0, 1, 0, 0, 0, 0]
[예제 입력 2] dp 출력 결과
• 7, 8, 9 -> 4가 얼리 아답터됨
• 2 -> 1이 얼리 아답터됨
• 5, 6 -> 3이 얼리 아답터됨
[0, 1, 0, 1, 1, 0, 0, 0, 0, 0]
6. 공통 부분 문자열 (골5) 5582
DP
1. 투포인터로도 풀 수 있는 문제이다.
2. 문자열 중 짧은 것을 s1, 긴 것을 s2로 두고, s1을 반복문 돌린다.
3. 현재 dp는 최소 이전 dp 값과 같으므로 갱신을 해준다.
4. 현재 dp만큼 이전 문자열부터 현재 문자열까지가 s2에 있다면 현재 dp를 증가시킨다. 즉, i가 5이고 dp[i]가 3이면 s1[2:5]가 s2에 있는지 확인하는 것이다.
[예제 입력 1] dp 변화
[1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0] -> A
[1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0] -> AB
[1, 2, 3, 3, 0, 0, 0, 0, 0, 0, 0] -> ABR
[1, 2, 3, 3, 3, 0, 0, 0, 0, 0, 0]
[1, 2, 3, 3, 3, 3, 0, 0, 0, 0, 0]
[1, 2, 3, 3, 3, 3, 3, 0, 0, 0, 0]
[1, 2, 3, 3, 3, 3, 3, 4, 0, 0, 0] -> CADA
[1, 2, 3, 3, 3, 3, 3, 4, 4, 0, 0]
[1, 2, 3, 3, 3, 3, 3, 4, 4, 5, 0] -> ADABR
[1, 2, 3, 3, 3, 3, 3, 4, 4, 5, 5]
7. 문제 추천 시스템 Version 1 (골4) 21939
힙+딕셔너리
1. 최솟값, 최댓값 출력은 힙, 값 탐색 및 삭제는 딕셔너리를 활용한다.
2. 입력을 배열로 받아 힙, 딕셔너리에 넣어준다. 이 배열은 참조되어 있기 때문에 한 곳에서 바뀌면 다른 곳에서도 바뀐다.
3. 힙은 (정렬 조건, 배열)로 넣어주고, 딕셔너리는 "entry[문제번호] = 배열"로 하여 문제 번호로 탐색할 수 있게 한다.
1. recommend: 최댓값 또는 최솟값 출력이다. 이때는 힙을 사용하므로 top이 REMOVED로 표시가 되어있다면 pop을 해주고 heap[0]을 출력한다.
2. add: 새로운 값을 추가한다. 아직 pop되지 않은 문제가 heap에 남아있어도 참조값이 다르기 때문에 덮어씌워지지 않는다.
3. solved: entry[문제번호][0]를 REMOVED로 체크한다. 그러면 heap에 있는 해당 참조값의 e[0]도 REMOVED로 표시된다. 이때 삭제된 문제에 대해 다른 난이도로 입력이 다시 들어온다면 entry는 덮어씌워진다.그렇지만 값만 바뀌는 것이 아니라 참조가 바뀌게 되어 heap의 새로운 입력을 가리키게 된다.
💡 e[0]이 숫자라면 REMOVED 상수 값도 숫자여야 한다. 문자열이면 타입 에러가 뜬다.
[예제 입력 1] entry 변화
add 1402 59
{1000: [1000, 1], 1001: [1001, 2], 19998: [19998, 78], 2667: [2667, 37], 2042: [2042, 55], 1402: [1402, 59]}
recommend 1
19998
{1000: [1000, 1], 1001: [1001, 2], 19998: [19998, 78], 2667: [2667, 37], 2042: [2042, 55], 1402: [1402, 59]}
solved 1000
{1000: [0, 1], 1001: [1001, 2], 19998: [19998, 78], 2667: [2667, 37], 2042: [2042, 55], 1402: [1402, 59]}
-> 1000 제거: entry[1000][0]이 0으로 바뀜
solved 19998
{1000: [0, 1], 1001: [1001, 2], 19998: [0, 78], 2667: [2667, 37], 2042: [2042, 55], 1402: [1402, 59]}
-> 19998 제거: entry[19998][0]이 0으로 바뀜
recommend 1
1402
{1000: [0, 1], 1001: [1001, 2], 19998: [0, 78], 2667: [2667, 37], 2042: [2042, 55], 1402: [1402, 59]}
recommend -1
1001
{1000: [0, 1], 1001: [1001, 2], 19998: [0, 78], 2667: [2667, 37], 2042: [2042, 55], 1402: [1402, 59]}
solved 1001
{1000: [0, 1], 1001: [0, 2], 19998: [0, 78], 2667: [2667, 37], 2042: [2042, 55], 1402: [1402, 59]}
-> 1001 제거: entry[1001][0]이 0으로 바뀜
recommend -1
2667
{1000: [0, 1], 1001: [0, 2], 19998: [0, 78], 2667: [2667, 37], 2042: [2042, 55], 1402: [1402, 59]}
-> 2667 제거: entry[2667][0]이 0으로 바뀜
8. 양팔저울 (골3) 2629
DP
배낭 문제 일종, "1학년" 문제와 비슷하다.
1. 각 추가 i이며 dp 계산을 하기 전에 dp[i][무게]=1 처리를 해준다.
2. 이전 dp 값이 1이면 현재 dp도 1로 갱신해준다.
3. 그 후 무게를 더하고 뺀 절댓값이 범위 안에 들어온다면 1로 갱신해준다.
[예제 입력 2] dp 변화
2 [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
3 [0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0]
3 [0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0]
3 [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
💻250401~250430 (골2)
1. 컵라면 (골2) 1781
힙
1. 입력 받는 힙: (데드라인 오름차순, 컵라면 내림차순)
2. 정답 구하는 힙: (컵라면 오름차순)
3. answer의 길이는 현재 데드라인을 절대 넘을 수 없다.
4. answer의 길이와 데드라인이 같다면 answer의 최솟값(answer[0])과 현재 컵라면 수를 비교한 후 더 큰 것으로 바꾼다.
2. 알약 (골5) 4811
DP
1. 알약 온전한 한 개를 꺼내는 경우의 수 생각한다.
2. dp[3]을 예시로 생각해보자. 맨 앞 W와 맨 뒤 H는 고정이므로 가운데 4개에서 W가 들어갈 위치를 생각하면 된다.
WWWHHH, WWHWHH -> 앞에 두 개를 선택: dp[2]*dp[0]
WWHHWH -> 앞에 하나 뒤에 하나 선택: dp[1]*dp[1]
WHWWHH, WHWHWH -> 뒤에 두 개를 선택: dp[0]*dp[2]
3. 뮤탈리스크 (골4) 12869
DP+BFS
1. 3개를 동시에 확인해야 하므로 3차원 dp로 둔다.
2. 최솟값을 구해야하므로 INF로 초기화하고 시작값을 0으로 한다.
3. (0, 1, 2)가 될 수 있는 모든 순열을 구해서 모든 damage 경우를 구한다. 해당 dp가 최소로 갱신될 때 q에 넣는다.
4. x, y, z가 모두 0이 되면 해당 dp가 공격 횟수이므로 반환한다.
4. 안녕 (실2) 1535
DP
💡 배낭 문제 팁: 기쁨을 구하는 것이면 dp[i][j]는 기쁨 합이 된다. (행-입력 받은 배열, 열-체력(제한된 숫자임))
13줄: j가 현재 체력보다 작으면 현재 기쁨을 추가할 수 없기 때문에 dp[i-1][j]를 그대로 현재 dp에 넣는다.
15줄: 현재 체력만큼 왔으면 현재 기쁨을 넣을 수 있다. 단, 넣는 것(dp[i-1][j-L[i]]+J[i])과 안 넣는 것(dp[i-1][j]) 중 뭐가 더 큰지 판단해야 한다.
dp[i-1][j-체력]+기쁨 vs 이전 dp 값
5. 게임 (골2) 1103
백트래킹+DP
현재 위치에서 최대 얼만큼 갈 수 있는지 백트래킹으로 구하고 dp로 메모이제이션한다.
사이클 구하는 방법: 백트래킹을 돌고 있는데 방문한 곳을 또 방문했다면 사이클이 있는 것
백트래킹이기 때문에 visited를 0으로 초기화해준다.
6. 자두나무 (골5) 2240
DP
j가 짝수일 때는 무조건 1에 위치하고, 홀수일 때는 무조건 2에 위치하기 때문에 3차원이 아니라 2차원 dp로 해도 괜찮다.
pos(위치): j가 짝수면 1에 위치, 홀수면 2에 위치
get(자두 받을 수 있는지): 자두 떨어지는 위치와 현재 pos가 같으면 1, 다르면 0
j가 0이면 이전 값에 get을 더한다.
dp[i-1][j]: 안 움직였을 때, dp[i-1][j-1]: 이전에서 이동해서 지금 위치에 왔을 때
[예제 입력 1] dp 출력 결과
0 1 2
[0, 0, 0]
2 [0, 1, 0]
1 [1, 1, 2]
1 [2, 1, 3]
2 [2, 3, 3]
2 [2, 4, 3]
1 [3, 4, 5]
1 [4, 4, 6]
댓글남기기