본문 바로가기
반응형

Problem Solving/BOJ228

백준 1655번 가운데를 말해요 - C++(cpp) 풀이 1. 새 수가 들어오면, 이전 중간값보다 작거나 같다면 최대우선순위큐에, 크다면 최소우선순위큐에 넣는다. 2. 최대우선순위큐에 담긴 수의 개수를 절반으로 유지시킨다. 3. 최대우선순위큐의 top을 출력한다. 1. 새 수가 들어오면, 이전 중간값보다 작거나 같다면 최대우선순위큐에, 크다면 최소우선순위큐에 넣는다. 현재까지 입력받은 수들을 오름차순 정렬했을 때 왼쪽 절반을 최대 우선순위큐에, 오른쪽 절반을 최소 우선순위큐에 보관하는 방식을 사용할 것이다. 그리고 최대 우선순위큐(작은 수들이 담긴 큐)에 담긴 숫자의 수는 항상 전체 개수의 절반으로 유지할 것이다. 이렇게 되면 항상 최대 우선순위큐의 top이 중간값이 된다. 새로 들어온 수가 왼쪽 절반에 속한다면, 즉 중간값(최대 우선순위큐의 top)보다 작거.. 2022. 2. 14.
백준 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.
반응형

티스토리툴바