구름을 채우다

문제 보기이 문제는 백준에 알고리즘 분류가 따로 되어있지 않지만 나는 BFS로 푼 문제이다.상어가 먹을 물고기를 찾기 위해서 BFS를 사용하였고, 상어가 어디로 이동할 지 결정하는 방법은 다음과 같다.먹을 물고기를 정하기 위해서 나는 우선순위 큐(Priority Queue)를 사용했다.문제를 풀기 위한 로직은 다음과 같다. 1. 현재의 상어위치로부터 BFS를 시작한다. (17~20번째 줄)2. BFS를 진행하면서, 상어가 지나갈 수 있으면 현재까지의 거리, 행과 열을 큐에 넣고, 먹을 수 있는 물고기가 있으면 우선순위 큐에 우선순위를 현재까지의 거리, 행, 열 순으로 삽입한다. (30~36번째 줄)3-1. 우선순위 큐가 비어있으면(=먹을 수 없는 물고기가 없으면) 종료한다. (38~40번째 줄)3-2. ..

문제 보기백준에 이 문제는 따로 알고리즘 분류가 없지만, 나는 BFS로 푼 문제이다. 두 나라의 인구가 이동하는 조건은 다음과 같다.위에 해당하는 단계들이 1번의 인구이동이다.여기서 실수할 수 있는 부분이 있다.나는 문제를 풀 때, 한 개의 연합국에서 인구이동이 끝날 때 1번의 인구이동이라고 카운트를 세었지만, 정답은 주어진 맵에서 가능한 모든 연합국들의 인구이동이 끝나는 것이 1번의 인구이동이었다.따라서 문제를 해결하기 위한 로직은 다음과 같다. 1. 주어진 맵의 각 위치마다 BFS를 진행한다. 이 때, 한 번의 인구이동동안 연합국에 해당하는지 확인하기 위한 집합 변수(unions)를 둔다. (11번째 줄)2. 연합국이 아닌 모든 나라들에 대해서 BFS를 진행한다. (12~33번째 줄)3. 한 번의 B..

문제 보기이 문제는 시뮬레이션 문제이다.처음에 이 문제에서 요구하는 바가 무엇인지 이해를 하지 못했다.. 그러나 문제를 이해하고 나니 구현은 매우 쉬웠다.드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있다. 1. 시작 점2. 시작 방향3. 세대 (Generation) 다음 세대로 넘어갈 때마다 변화하는 드래곤 커브는 문제의 설명을 보면 이해할 수 있다.드래곤 커브의 진행방향은 다음과 같이 정의되어 있다.드래곤 커브의 방향을 살펴보면 다음과 같은 규칙이 있다.0세대: 01세대: 01 -------------- 0 12세대: 0121 ----------- 01 213세대: 01212321 ------ 0121 2321 위의 규칙을 보면, 다음 세대의 드래곤 커브는 현재 세대의 드래곤 커브에서 거꾸로 ..

문제 보기이 문제는 브루트 포스 문제이다. n의 범위가 50이하이고, 선택해야하는 치킨집의 갯수가 13이하이므로, 브루트포스임을 유추할 수 있다.나는 처음에 문제를 제대로 이해하지 못해서 BFS 문제라고 생각했다. 하지만 모든 경우의 수를 따져봐야 하기때문에, 브루트포스임을 나중에 깨달았다.문제에서 주어지는 정의는 다음과 같다. 치킨거리: 집과 가장 가까운 치킨집까지의 거리도시의 치킨거리: 모든 집의 치킨거리의 합 최대 M개의 치킨집을 고르고, 최솟값이 되는 도시의 치킨거리를 구해야한다.따라서 주어진 모든 치킨집에서 m개를 선택하는 조합(Combination)을 사용해야한다.문제를 해결하기 위한 로직은 다음과 같다. 1. 주어진 치킨집에서 M개의 치킨집을 선택할 수 있는 모든 경우의 수를 조사한다. (조..

문제 보기이 문제는 브루트 포스 문제이다.완전탐색을 위해서 DFS를 재귀적으로 구현하였다.문제를 풀기위한 로직은 다음과 같다. 사다리를 놓을 수 있는 경우의 수 0, 1, 2, 3에 대하여, 그 갯수만큼 사다리를 놓을 때의 모든 경우의 수를 순서대로 탐색한다. (44~46번째 줄)만약 answer의 값이 변경되었다면(= sys.maxsize가 아닐 때), 필요한 사다리의 갯수를 찾았다고 간주하고 정답을 출력한다. (47~51번째 줄)사다리를 놓을 수 있는 모든 위치를 탐색하면서, 사다리를 놓을 모든 경우의 수를 DFS로 탐색한다. (32~41번째 줄)DFS를 재귀적으로 실행하면서 정해놓은 갯수만큼 사다리를 놓았다면, 사다리 게임을 시작하고, i번째 사다리에서 시작해서 i번째 사다리에서 모두 끝나는지 검사..

문제 보기이 문제는 브루트 포스 문제이다. 다음과 같은 감시카메라로 감시를 할 때, 주어진 맵에서 최소의 사각지대를 구해야한다.감시카메라의 종류는 다음과 같다.각 종류의 감시카메라가 90도마다 회전할 때의 최소 사각지대를 구해야한다.다음 그림을 보면 이해할 수 있다.위 그림을 설명하자면, CCTV 리스트에 있는 모든 카메라들에 대해서 4번씩 회전시키고, solution()함수를 재귀적으로 실행시킨다. 이때의 매개변수는 현재 CCTV 리스트와 그 index이다. 1. 리스트 내의 index가 0인 1번 CCTV의 모든 회전에 대해서 재귀적으로 탐색을 한다. (그림에서는 1번 CCTV를 4번 회전시킨다.)2. 1번 CCTV의 각 회전에 대해서 리스트 내의 index가 1인 2번 CCTV의 모든 회전에 대해서..

문제 보기이 문제는 시뮬레이션 문제이다.톱니바퀴의 초기상태와 회전 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구해야한다. 나는 이 문제를 보자마자 나는 비트마스크를 써야겠다고 생각했다.톱니의 상태를 2진수로 만들고, 이를 시계방향, 반시계방향으로 회전시키는 함수를 만들었다. (10~25번째 줄)12시 방향의 비트를 MSB로 두었고, MSB 바로 왼쪽의 비트를 LSB로 두었다. 10101111 -> 01011111 각 명령마다 톱니바퀴를 선택하고 돌릴 때, solution 함수를 통해 톱니바퀴를 양쪽으로 탐색한다.비트마스크를 사용해서 문제를 풀 때, 여기서 주의해야할 점이 있다. 1. 오른쪽으로 탐색할 때오른쪽 톱니바퀴를 회전시킬지 결정할 때, 오른쪽 톱니바퀴의 2번째 비트와, 왼쪽 톱니바퀴의 6번째 비..

문제 보기이 문제는 시뮬레이션 문제이다.문제를 풀다보니 코드가 점점 더러워지는 느낌이다.. 문제에서 주어지는 조건은 다음과 같다.이 조건들을 잘 따지면 정답을 구할 수 있다. (말은 쉽지만 이 문제 푸는데 아주 오래 걸렸다...) 이 문제를 푸는데 사용한 로직은 다음과 같다.1. 같은 높이의 블럭이 나오면 갯수를 센다. (13~14번째 줄)2. 다음 블럭의 높이가 2 이상 차이나면 조건을 위반하므로 flag를 False로 바꾼다. (29~31번째 줄)3-1. 다음 블럭이 높을때, count와 경사로의 길이를 비교한다. count가 더 작으면 경사로를 놓을 수 없다는 의미이고, count가 경사로의 길이보다 같거나 더 크면 경사로를 놓을 수 있다는 의미이다. 그러므로 경사로를 놓고 count를 1로 초기화..

문제 보기이 문제는 브루트 포스 문제이다.두 팀의 능력치의 경우의 수를 모두 따져서 그 차이가 최소가 되는 것을 찾아야 한다.먼저 각 팀을 정확히 절반으로 나누는 과정은 DFS로 구현하였다. 문제를 해결하는 단계는 다음과 같다.1. n 명의 선수들을 2개 팀으로 나누어서 배치한다. (DFS 적용)2. 각 팀에서 선수 2 명을 선택하여, 팀에 더해지는 능력치를 구하고, 팀의 총 능력치에 더한다. (조합)3. 두 팀의 능력치 차이의 최소값을 구한다. 다른 사람들의 풀이를 보아하니, itertools의 combination 함수를 사용한 것을 보았다.다음에는 나도 itertools를 사용해서 문제를 풀어봐야겠다. 123456789101112131415161718192021222324252627282930313..

문제 보기이 문제는 브루트 포스 문제이다.N개의 수로 이루어진 수열에서, 각 숫자 사이에 사칙연산자 +, -, *, / 를 집어넣어서 최대, 최소값을 구하는 문제이다.Iterative한 방법은 실력이 부족해서 구현하지 못했다.. 이 문제를 풀면서 깨달은 점은, 파이썬에서 음수의 나눗셈을 할 때 신경을 써야한다는 것이다.123print(-3 / 4)print(int(-3 / 4))print(-3 // 4)cs이 값들의 결과값은 다음과 같다.문제를 풀면서 파이썬에서 나누기연산은 부호에 관계없이 모두 floor division을 한다는 것을 알았다. 따라서 문제에서 요구하는 올바른 몫을 구하기 위해서는 결과값에서 int형으로 캐스팅해서 몫을 구해야한다. 1234567891011121314151617181920..