Joonas' Note

[이전 블로그의 글] 각 노드에서 리프 노드까지의 거리가 (왼쪽으로 가든지, 오른쪽으로 가든지) 같도록 조정하는 것이므로 재귀를 생각할 수 있다. 이를 해결할 작은 문제로 재귀의 중간 과정부터 생각했다. 왼쪽과 오른쪽의 길이가 달라져서 조정이 필요한 상황은 "왼쪽 != 오른쪽" 이다. 이를 조정하는 작업은 더 작은 쪽에 가중치를 증가시키는 것이다. 가중치는 보정을 위해 추가하는 것이므로, 맞추고자 하는 차이만큼 증가시키면 된다. 코드 보기

링크 1: https://uva.onlinejudge.org/...problem=1859 링크 2: BOJ 2133 - 타일채우기(https://www.acmicpc.net/problem/2133) 문제 타일 시리즈 중에 하나로, 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 문제이다. 풀이 3×n 크기의 벽을 채우는 경우의 수를 \(f(n)\)이라고 하자. 다음은 전개될 수 있는 모든 모양이다. 모양이 반복되는 경우까지만 적었다. .... x... .... f(n) = .... g(n) = .... or .... .... .... x... A..... AA.... A..... or ...... ...... ...... A..... ACC... ACC... ACC... A..... -> A....

링크: https://www.acmicpc.net/problem/17142 문제 연구소에 이미 존재하는 바이러스들 중 \(m~(2\le m \le 10)\)개를 활성 상태로 바꾸어 바이러스를 퍼뜨리는 문제이다. 그 때, 연구소의 모든 빈칸에 바이러스가 퍼지게 하는 최소 시간을 구해야 한다. 풀이 연구소에 존재하는 바이러스 들 중 \(m\)개를 골라야한다. DFS 같은 방법으로 고를 수 있지만, next_permutation을 사용하면 간단하다. 4개 중 2개를 고르는 조합은 0011 → 0101 → 0110 → 1001 → 1010 → 1100 순으로 진행된다. 이런 특징을 사용하여 매번 적당히 \(m\)개를 선택하여 플러드 필(Flood Fill, BFS)을 한다. 모든 빈칸을 방문한다면 그 때의 탐색..

링크: https://www.acmicpc.net/problem/17140 문제 R 연산을 기준으로 구현하고, C 연산은 행/열만 바꿔서 똑같이 진행하면 된다. 한 행을 읽고 map과 같은 적당한 자료구조에 (수, 등장한 횟수)의 형태로 저장한다. 삽입과 조회, 수정 모두 \(O(logN)\) 만큼 걸린다. 정렬 기준은 1. 등장한 횟수가 적은 순, 2. 수의 크기가 작은 순이다. 정렬을 위해 map에 저장된 내용을 추출한다. 반복자 등으로 자료구조를 순회하면서 (수, 등장한 횟수)를 배열로 바꿔 정렬하고, 정렬된 순서로 새로운 행에 덮어씌운다. 바로 덮어씌워도 상관없으나, 이전 행보다 길이가 짧아지는 경우에 주의해야한다. (ex. [3, 1, 1, 1, 1, 1] → [3, 1, 1, 5, 0, 0] ..

링크: https://www.acmicpc.net/problem/14852문제타일 시리즈 중 하나인데, 2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 먼저 왼쪽부터 타일을 채워가면서 생기는 모양에 따라 부분 문제를 만들어나간다. 아래와 같은 모양을 각각 \(f(n), g(n)\)이라고 정의해보자. \(g(n)\)은 첫 번째 열 중에서 한 칸만 채워진 경우이다.두 모양이 채워질 수 있는 Base case를 이렇게 정의하자. \(f(0)\)은 모든 타일을 채웠다는 뜻으로 1개로 센다. \(g(0)\)은 불가능한 모양이므로 0이다. 먼저 \(g(n)\)은 아래와 같이 세 가지 모양으로 전개될 수 있다.첫 번째 열의 빈칸에 1×1짜리 타일을 하나 채우면 \(f(..

링크: https://www.acmicpc.net/problem/9375문제해빈이가 가진 의상들의 이름과 종류가 주어지면, 가능한 모든 경우의 수는 몇 개인지 묻는 문제입니다.문제에서 같은 이름을 가진 의상은 존재하지 않으므로 이름은 중요하지 않고 해당 종류만 구분하면 됩니다.가지고 있는 모자가 2개라면 모자만으로 가능한 경우는 3가지입니다. 첫 번째를 쓰거나, 두 번째를 쓰거나, 아무것도 쓰지 않거나 이렇게 총 3가지입니다. 어떤 종류를 \(n\)개 가지고 있다면 선택 가능한 수는 \(n+1\)개이고, 나올 수 있는 모든 가짓수는 각 종류마다 가능한 경우를 모두 곱한 값입니다.위 그림의 경우에는 \(3 \times 4 \times 2~=~24\) 이지만, 문제에서 알몸이 아닌 상태 즉 모두 선택하지 않..

링크: https://programmers.co.kr/learn/courses/18/lessons/1878문제코딩 테스트의 데모 문제, 연습 문제로 많이 등장하는 문제입니다.직사각형을 나타내는 네 개의 꼭짓점 중 세 개의 좌표가 주어졌을 때, 나머지 한 좌표를 구하는 문제죠.좌표의 범위에 따라 해결 방식이 다를 수 있습니다. 여기서는 좌표의 범위가 10억까지인 프로그래머스 문제의 풀이를 다룹니다. (백준에서는 1000 이하의 정수)네 점의 x좌표들은 모두 2번씩 등장합니다. 마찬가지로 y좌표들도 2번씩 등장해야하죠. 그럼 x, y 좌표들 중 1번만 등장한 녀석들이 문제의 정답입니다.이것을 카운팅하는 것이 곧 문제를 해결하는 것인데, 좌표가 10억까지 주어지는 경우라면 해시(Hash)와 같은 적당한 자료구..

링크: https://www.acmicpc.net/problem/1405문제동서남북 각 방향으로 이동할 확률이 주어지고, 로봇이 동선을 겹치지 않게 n번 움직일 확률을 구하는 문제이다.(0, 0)부터 출발한다고 생각하면 동서남북 경계의 끝은 (14, 0), (-14, 0), (0, 14), (0, -14) 일텐데 음수를 없애기위해 출발점을 (15, 15)로 설정하면 편하다.좌표값을 들고 다니는 이유는 동선이 겹쳐서는 안되기 때문에, 다시 말해 이미 방문한 위치는 다시 방문하지 않도록 하기 위해서이다.어떤 한 위치에서 생각했을 때, 동쪽으로 이동한다면 동쪽에서 나오는 모든 확률은 (그 위치에서 발생하는 확률 * 동쪽으로 이동할 확률)이 된다. 이걸 동서남북 모든 방향과 모든 위치마다 반복한다면 정답을 구할..

링크: https://www.acmicpc.net/problem/2096문제어떤 칸을 선택하면 선택 가능한 다음 칸이 정해지는 점에서 9465번 - 스티커와 굉장히 유사합니다. 사실 동일한 풀이로 해결되지만 다른 점이 있습니다.이 문제는 메모리의 제한이 4MB로 엄청 작다는 겁니다.적은 메모리 제한때문에 스티커 문제처럼 dp[3][N] 과 같은 배열을 선언할 수도 없고 재귀 함수까지도 염려해야하는 상황입니다. 그럼 어떻게 해결해야할까요?풀이어떤 r번째 줄에서 어떤 칸을 선택한다면, 이는 다음 줄인 r+1번째 줄에 영향이 갑니다. 어떤 칸을 선택할 때, 항상 2개의 줄만 확인하면 된다는 점으로 메모리를 줄일 수 있습니다. 왜냐하면 1번째 줄은 2번째 줄에 영향을 주고 2번째 줄은 3번째 줄에 영향을 주지만..

링크: https://www.acmicpc.net/problem/16964풀이문제의 가장 큰 힌트는 입력된 그래프의 모양이 트리라는 점이다. 즉, 사이클이 없다. 올바른 DFS 방문 순서가 되기 위해서는 자식이 부모보다 먼저 나오는 경우가 있어서는 안된다.이 특징을 살리면, 어떤 순서 \(i\)번째에 등장하는 노드 \(x\)의 깊이는 어떤 순서 \(i\)+\(x\)의 서브트리의 크기까지는 전부 그 노드의 자식이라는 점이다. 위 그림처럼 입력이 주어졌다고 해보자.여러 DFS 방문 순서가 가능하겠지만, 그 중 하나인 [1, 3, 5, 8, 6, 4, 7, 9, 2]의 순서를 예로 들자면 어떤 \(i\)번째 순서에 있는 노드 \(x\)는 자신의 서브트리의 크기만큼 다음 순서가 자신의 형제 노드이다.2번째 순서..