반응형 Problem Solving242 백준 16234번 인구 이동 - 스위프트(Swift) 풀이 1. 인접한 두 칸의 차이가 L 이상 R이하인 곳은 간선으로 연결되어있다고 생각한다. 2. 매일 BFS로 연합을 만들고 인구 이동을 처리해준다. 3. BFS가 하나도 이루어지지 않으면 이동이 끝난 것이다. 1. 인접한 두 칸의 차이가 L이상 R이하인 곳은 간선으로 연결되어있다고 생각한다. 현재 상황을 그래프로 바꾸어줄 것이다. 각 칸을 정점으로 생각하고, 인접한 두 칸(정점)의 인구수 차이가 L 이상 R이하라면 두 정점을 연결해준다. 2. 매일 BFS로 연합을 만들고 인구 이동을 처리해준다. 인구 이동 시뮬레이션을 진행해준다. 하루가 지날 때마다 BFS로 인접한 정점들을 연합으로 만든 뒤, 인구 이동을 처리해준다. BFS 과정에서 방문한 국가들을 배열에 담아두었다가 마지막에 배열을 순회하면서 평균 인구수.. 2022. 2. 12. 백준 1937번 욕심쟁이 판다 - 스위프트(Swift) 풀이 1. dp(row, col) = (row, col)에서 시작했을 때 이동할 수 있는 최대 칸수 2. dp(row, col) = max(1 + dp(상하좌우)) 1. dp(row, col) = (row,col)에서 시작했을 때 이동할 수 있는 최대 칸수 dp(row, col)을 위와 같이 정의할 것이다. 2. dp(row, col) = max(1 + dp(상하좌우)) 인접한 상하좌우 중 어떤 칸으로 이동했을 때 가장 많은 칸을 이동할 수 있는지 모두 따져본다. 만약 오른쪽 칸에 현재 칸보다 더 많은 대나무가 있다면 이동할 수 있고, 현재 칸에서 오른쪽으로 가는 방법을 선택했을 때 이동할 수 있는 최대 칸수는 1 + dp(row, col+1)이 된다. 이렇게 상하좌우 네 칸에 대해 모두 대나무가 더 많은지 .. 2022. 2. 11. 백준 14890번 경사로 - 스위프트(Swift) 풀이 + 그림 설명 1. 한 길 내에서 인접한 같은 높이의 칸들을 union 한다. 이때 각 집합의 크기를 기록해둔다. 2. 한 길 내의 모든 칸을 순회하면서 다음 칸으로 갈 수 있는지 체크한다. 2-1. 다음 칸과의 높이가 1 차이나고, 더 낮은 칸이 속한 집합의 크기가 L 이상이라면 경사로를 놓아서 갈 수 있다. 2-2. 다음 칸과 높이가 같다면 그냥 갈 수 있다. 2-3. 그 외의 경우에는 갈 수 없다. 1. 한 길 내에서 인접한 같은 높이의 칸들을 union 한다. 이때 각 집합의 크기를 기록해둔다. 인접한 같은 높이의 칸은 이동할 수 있다. 몇 개가 연속해서 같은 높이인지 쉽게 파악하기 위해 union 하면서 집합의 크기를 기록한다. 2. 한 길 내의 모든 칸을 순회하면서 다음 칸으로 갈 수 있는지 체크한다. 2-.. 2022. 2. 10. 백준 19538번 루머 - 스위프트(Swift) 풀이 1. 최초 유포자부터 시작해 BFS로 루머를 퍼트려나간다. 2. X번 사람이 새로 루머를 믿게 되면, X의 모든 주변인들에 대해 주변인카운트를 1 증가시켜준다. 3. 만약 주변인카운트가 주변인 수의 절반 이상이 되면 루머를 믿게 된 것이므로 큐에 넣는다(방문한다). 1. 최초 유포자부터 시작해 BFS로 루머를 퍼트려나간다. 매분 주변인에게 루머를 퍼트리는 상황은 너비우선탐색 상황과 같다. 최초 유포자들을 모두 큐에 넣은 상태로 BFS를 시작한다. 앞으로 큐에는 루머를 믿는 사람들만 넣을 것이다. 2. X번 사람이 새로 루머를 믿게 되면, X의 모든 주변인들에 대해 주변인카운트를 1 증가시켜준다. 주변인의 절반 이상이 루머를 믿을 때 루머를 믿게 되므로, 자신의 주변인 중 몇 명이 루머를 믿고 있는지를 기.. 2022. 2. 10. 백준 14888번 연산자 끼워넣기 - 스위프트(Swift) 풀이 1. 앞에서부터 차례로 연산자를 정한다. 2. 다음 연산자를 고를 때는 남은 연산자 중에 하나를 고른다. 3. N-1개의 연산자를 다 골라서 완성했으면 결과값을 가지고 최대, 최솟값을 갱신한다. 1. 앞에서부터 차례로 연산자를 정한다. N이 최대 11로 매우 작다. 연산자 개수는 최대 N-1 = 10개이므로, 10가지 종류의 연산자가 있다고 하더라도 모든 경우의 수가 10! 밖에 되지 않는다. 따라서 브루트 포스로 N-1개 연산자를 줄 세우는 모든 경우를 고려해주어도 시간 안에 통과가 가능하다. 앞에서부터 차례로 연산자를 정해주자. 2. 다음 연산자를 고를 때는 남은 연산자 중에 하나를 고른다. operators[i]를 남아있는 연산자 i의 개수, bruteForce(index, currentValue).. 2022. 2. 10. 이전 1 ··· 31 32 33 34 35 36 37 ··· 49 다음 반응형
