반응형 Problem Solving242 백준 12100번 2048 (Easy) - 스위프트(Swift) 풀이 + 그림 설명 1. 미는 방향으로 블록을 몬다. 2. 인접한 두 블록을 미는 방향으로 합칠 수 있으면 합친다. 3. 합치면서 생긴 빈자리를 없앤다. 4. 4^5가지 경우에 대해 전부 다 시뮬레이션(1-3과정)하여 최댓값을 구한다. 1. 미는 방향으로 블록을 몬다. 아래와 같은 보드 상태에서 위로 밀어야 하는 상황이다. 열 별로 차례로 밀어줄 것이다. 1열부터 밀어보자. 먼저 빈 공간이 없도록 윗방향으로 블록들을 몰아준다. 2. 인접한 두 블록을 미는 방향으로 합칠 수 있으면 합친다. 이제 합칠 차례이다. 만약 인접한 두 블록을 합칠 수 있는 경우 합친다. 미는 방향이 윗방향이기 때문에 윗블록이 남고 아랫 블록은 사라진다. 3. 합치면서 생긴 빈자리를 없앤다. 합치면서 생긴 빈자리를 또 메꿔주면 미는 작업이 끝난다. 나.. 2022. 1. 29. 백준 2623번 음악프로그램 - 스위프트(Swift) 풀이 1. 각 출연자를 정점으로 생각하고, 보조 PD들이 만든 순서가 A B C D라면 A→B, B→C, C→D로 가는 간선을 추가한다. 2. 완성된 그래프에 대해 위상 정렬을 한다. 3. 위상 정렬 결과에 포함된 정점 개수가 N개가 아니라면 순서를 정하는 것이 불가능한 경우이다. 1. 각 출연자를 정점으로 생각하고, 보조 PD들이 만든 순서가 A B C D라면 A→B, B→C, C→D로 가는 간선을 추가한다. 선행 관계가 주어진 작업들의 순서 정하기 문제이다. 위상 정렬 알고리즘을 사용하여 해결할 수 있다. 현재 상황을 그래프로 변환한다. 보조 PD들이 만든 X명의 순서를 차례로 쪼개면 X-1개의 선행 관계가 나오게 된다. 위와 같이 선행 관계로 쪼개 간선을 추가해준다. 2. 완성된 그래프에 대해 위상 정렬.. 2022. 1. 28. 백준 1202번 보석 도둑 - C++(cpp) 풀이 + 그림 설명 1. 용량이 적은 가방부터 채운다. 2. 가방에 담을 수 있는 보석 중 가격이 가장 높은 것을 담는다. 3. 남은 가방에 대해 1-2를 반복한다. 1. 용량이 작은 가방부터 채운다. 한 가방에는 한 개의 보석만 담을 수 있으므로 그리디 하게 풀 수 있는 상황이다. 용량이 적은 가방에 들어가지 못한 보석이 용량이 큰 가방에는 들어갈 수도 있다. 반대로 용량이 큰 가방에 들어가지 못한 보석이 용량이 적은 가방에는 들어갈 일은 없다. 따라서 용량이 작은 가방부터 최선으로 채워나가면 최선의 결과를 얻을 수 있음이 보장된다. 2. 가방에 담을 수 있는 보석 중 가격이 가장 높은 것을 담는다. 먼저 용량이 C인 가방에 담을 수 있는 보석들을 걸러내기 위해 보석을 무게 순으로 정렬한다. 아래와 같은 상황이고, 가방의.. 2022. 1. 28. 백준 2056번 작업 - C++(cpp) 풀이 1. 각 작업을 정점으로, 작업 순서를 방향 간선으로 나타낸다. 2. 그래프에 대해 위상 정렬을 한다. 3. 위상 정렬 과정에서 totalCost[i] = max(totalCost[prev]) + i번 작업에 걸리는 시간을 구한다. 4. max(totalCost[i])를 출력한다. 1516번 게임 개발 문제와 똑같으니 1,2,3번 풀이는 아래에서 확인! 백준 1516번 게임 개발 - C++(cpp) 풀이 1. 각 건물을 정점으로, 건설 순서를 방향 간선으로 나타낸다. 2. 그래프에 대해 위상 정렬을 한다. 3. 위상 정렬 과정에서 totalCost[i] = max(totalCost[prev]) + i번 건물을 짓는 데 걸리는 시간을 구한다. 1 please-amend.tistory.com 4. max(t.. 2022. 1. 28. 백준 1516번 게임 개발 - C++(cpp) 풀이 1. 각 건물을 정점으로, 건설 순서를 방향 간선으로 나타낸다. 2. 그래프에 대해 위상 정렬을 한다. 3. 위상 정렬 과정에서 totalCost[i] = max(totalCost[prev]) + i번 건물을 짓는 데 걸리는 시간을 구한다. 1. 각 건물을 정점으로, 건설 순서를 방향 간선으로 나타낸다. 이렇게 선행 관계가 정해져있는 작업들을 순서대로 수행하는 상황은 그래프 위상 정렬 알고리즘으로 해결할 수 있다. 먼저 주어진 상황을 그래프로 나타낸다. 2. 그래프에 대해 위상 정렬을 한다. 위상 정렬을 해준다. 아래 코드에서는 큐를 사용하였고, 선행 작업들이 모두 완료된 작업들만 큐에 들어가게 된다. 3. 위상 정렬 과정에서 totalCost[i] = max(totalCost[prev]) + i번 건물.. 2022. 1. 28. 이전 1 ··· 35 36 37 38 39 40 41 ··· 49 다음 반응형
