구름을 채우다

문제 보기 이 문제는 해쉬 문제이다. 문제를 해결하기 위해 2가지의 dictionary 자료형 변수가 필요하다. 첫 번째는 각 장르별 재생 횟수를 위해, 두 번째는 각 노래별 재생 횟수를 위해서이다. 문제를 푼 로직은 다음과 같다. 각 장르별 총 재생 횟수를 구한다. (10~13번째 줄) 모든 노래에 대해 장르별로 해쉬 맵을 구성한다. (14~17번째 줄) 총 재생 횟수가 많은 순서대로 장르의 순서를 구한다. (19~20번째 줄) 재생 횟수가 많은 순서대로 각 장르에 속한 노래들의 순서를 구한다. (21~23번째 줄) 3번에서 구한 장르의 순서대로, 그 장르에 속한 노래들을 4번에서 구한 순서에서 첫 번째와 두 번째 노래를 베스트 앨범에 추가한다. (노래가 1곡이면 1곡만 추가한다.) (25~32번째 줄..

문제 보기 이 문제는 해쉬 문제이다. (그런데 정작 해쉬는 잘 안 쓰인 것 같다..) 처음엔 간단해 보였는데 경우의 수를 잘 못해서 한참 헤맸다.. 문제를 푼 로직은 다음과 같다. 먼저 옷의 각 종류에 대해서 옷의 개수를 센다. (옷의 이름은 중요하지 않다. 개수만 알면 된다.) (7~11번째 줄) 만약 옷의 종류가 한 가지라면 옷의 개수만큼 반환한다. (스파이는 최소 1개 이상의 옷을 입어야하기 때문) (13~16번째 줄) 만약 옷의 종류가 한 가지 이상이라면, (종류 1의 개수 + 1) * (종류 2의 개수 + 1) * ... - 1을 반환한다. (옷의 종류에서 1을 더하는 이유는 해당 종류의 옷을 안 입을 수 있기 때문이고, 마지막에 - 1을 하는 이유는 스파이는 최소 1개 이상의 옷을 입어야 하므..

문제 보기 이 문제는 해쉬 문제이다. 그런데 접두사라는 특징이 보여서 지금까지 한 번도 해본 적 없는 트라이로 풀어보았다. 문제를 푼 로직은 다음과 같다. 전화번호부에 있는 전화번호들을 정렬한다. (26번째 줄) 정렬이 끝나면 길이가 짧은 문자열부터 차례대로 나열되는데, 이 때 트라이에 삽입하면서 확장시켜나간다. 트라이에 삽입할 때, 문자열의 마지막 노드에 end라는 불리언 변수를 True로 설정한다. (21번째 줄) 만약 어떤 문자열을 트라이에 삽입할 때, end가 True인 노드를 만난다면 이전에 같은 문자열이 삽입되었다는 뜻이므로 False를 반환한다. (18~20번째, 29~30번째 줄) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..

문제 보기 이 문제는 해쉬 문제이다. (매우 간단했다..) 문제를 푼 로직은 다음과 같다. 마라톤에 참가한 선수들에 대해서 dictionary를 생성하고, 이름의 개수를 센다. (4~10번째 줄) 마라톤을 완료한 각 선수들의 이름에 대해 갯수를 깎는다. (12~14번째 줄) 문제의 조건에서 마라톤을 완주하지 못한 선수는 1명이라고 명시되어있으므로, 1개 남은 이름을 찾는다. (16~19번째 줄) 난 이렇게 풀었지만 다른 사람의 풀이를 보니 collections 모듈의 Counter 함수를 사용한 것을 보았다. (정말 간단하다...) Counter 함수는 dictionary를 반환한다. 또한, dictionary 타입끼리는 덧셈, 뺄셈, 교집합과 합집합 연산이 가능하다는 것을 알았다. 1 2 3 4 5 6..

문제 보기이 문제는 백준에 알고리즘 분류가 따로 되어있지 않지만 나는 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의 모든 회전에 대해서..