그냥 하는 노트와 메모장

BOJ 9015 정사각형 [분류 - 기하, 해싱] [풀이 - 정답] 주어진 좌표의 수는 N개이고 사각형을 만들기 위해서 O(N^4)이 먼저 떠오르지만 시간초과를 면치못하니 보다 효율적인 구현이 필요하다. 정사각형을 만들기 위해서 일단 임의의 두 점을 잡고 다른 두 점을 찾는 방식을 생각해보자. 이 때 임의의 두 점이 이루는 선분은 사각형의 한 변이 되는데, 이러면 만들 수 있는 사각형은 반드시 두 개다. 한 방향만 선택하여 보도록하자. 일단 임의의 두 점을 선택하자. 이 과정은 O(N^2)이다. 이 두 점이 이루는 선분은 만들고자하는 정사각형의 한 변이 된다. 이 두 점을 포함하는 가장 작은 직사각형을 만들면 아래처럼 빨간 영역의 직사각형을 만들 수 있다. 이 빨간색 영역을 90도씩 회전하면 영역 내에 ..

BOJ 10538 빅피처 [분류 - 아호코라식] 풀이) 2차원 문자열 매칭이다. 주어진 hp x wp 크기를 가지는 그림의 행을 패턴으로 보자. 그러면 총 hp개의 패턴이 존재한다. 이 hp개의 패턴을 아호코라식 트라이 A에 저장하자. 각 패턴을 넣을 때 마지막 노드엔 패턴 끝이라는 정보를 행 인덱스로 저장하자. 여기서 이 노드에 행 인덱스가 여러 개 있을 수 있다; 그림에서 i번째 행과 j번째 행이 같다는 소리다. 이건 Union-Find로 합쳐주자. 이후에 '걸작'을 순회하자. '걸작'의 행들을 각각 탐색 대상 문자열로 보자. 행을 순회할 때마다 방문 노드를 A의 루트로 되돌리며, 매칭되는 패턴을 찾는다. i번째 행 j번째 열을 순회할 때 A에서 어떤 패턴을 찾았다면 이 정보를 2차원 배열 row_d..

BOJ 2638 - 치즈 [분류 - BFS] [풀이1] 빈 공간이 보장되는 (0, 0)부터 계속 BFS를 돌면서 4방향에 대해 2방향 이상에 공기에 노출되는 경우에 대해서 삭제한다. 그러다가 모두 지워지는 시점을 출력한다. [풀이2] 빈 공간 (0, 0)부터 시작해서 공기가 될 부분, 즉 치즈가 사라질 부분을 또다른 큐에 넣도록 한다. 그러면 그 위치부터 공기가 시작되는 부분이기 때문에 [풀이1]에서 사용한 (0, 0)에서 다시 돌릴 필요가 없어지는 것이다. 두 개의 큐를 사용하여 공기인 부분은 진행하고 치즈인데 2방향 이상이 공기에 맞닿은 부분이 있다면 다른 큐에 넣어두는 것이다. 이 방식은 따로 명명할 방법이 없어 나는 토글 큐(toggle queue)라고 부르긴 한다. #include #includ..

BOJ 1053 - 팰린드롬 공장 [분류 - 다이나믹 프로그래밍] [풀이] 4번 연산이 엄청 까다로워 보인다. 하지만 딱 한 번만 사용할 수 있으니 이에 대해 전처리를 진행해보자 1. 4번 연산을 사용하지 않는다. 2. 4번 연산을 사용한다(swap(s[i], s[j]), i != j). 나머지 연산에 대해서 생각해보자. 최소 연산수를 만족하기 위해서 삽입을 하거나, 삭제를 하거나, 특정 문자로 교환하는 행위는 반드시 팰린드롬을 만들기 위해 이득이 되어야한다. 다시 말하면 연산을 진행했을 때, 결과 팰린드롬의 일부가 반드시 되어야한다. 양끝부터 시작해서 팰린드롬 연산을 진행한다. 이 과정은 위의 4번 연산을 쓸 때와 안 쓸 때에 모두 계산이 필요하다. dp[l][r] = 구간 [l, r]에 대해 팰린드롬..

BOJ 2618 - 경찰차 [분류 - 다이나믹 프로그래밍] [풀이] 경찰차 1이 있는 (1, 1)을 1번 사건, 경찰차 2가 있는 (N, N)을 2번 사건, 그리고 나머지 N개의 사건을 3, 4, ..., N+2번 사건이라고 하자. 각 경찰차가 마지막 사건을 처리한 위치가 각각 a, b라고 하면 그 다음 사건을 처리할 때 그 사건의 번호는 max(a, b) + 1이 된다(순차적으로 진행해야 하므로). dp[a][b] = 경찰차 1이 a를 해결했고, 경찰차 2가 b를 해결했을 때 남은 모든 사건을 해결하기 위한 이동 최소 이제 문제는 꽤 간단해진다. 당연하게도 그 다음 사건 w(w = max(a, b) + 1)번 사건을 해결하기 위해서는 경찰차 1에 할당할 것인지 경찰차 2에 할당할 것인지 두 가지밖에 없..

BOJ 1600 - 말이 되고픈 원숭이 [분류 - BFS] [풀이] 말처럼 뛰는 동작은 k를 정확히 1만큼을 올리기 때문에 k+1과 k는 인접해있다. 따라서 k+1번째에 특정 좌표 (y, x)에 도달했다면 그 값이 곧 최소 동작이 된다. vi[k][y][x] - y행 x열에 k번만 말처럼 뛰어서 도달할 수 있는 동작 수의 최소값 BFS 특성상 진행하려는 방향에 대해 정확히 1만큼 증가시키고 vi[k+1][y][x]에 도달할 수 있는 위치가 (y1, x1), (y2, x2)일 때, 1. vi[k][y1][x1] > vi[k][y2][x2] BFS 큐에 들어가는 좌표는 (y2, x2)가 더 우선순위를 가진다. 2. vi[k][y1][x1] = 0) for (j = 0; j < n[i]; j++) { int ..

BOJ 8902 색상의 길이 [분류 : 그리디, 다이나믹 프로그래밍] [풀이] 하나의 색에 대해서만 생각해보자. 합쳐질 차선에 배치할 때 그 색상 중 가장 왼쪽에 올 수 있는 1차선의 후보와 2차선의 후보를 가려내보자. 순서상 같은 차선에서 같은 색상을 가지는 인덱스 i 3 a=5, F[0][a] -> 6 dp[a][b]=현재 1차선에서 a번째 후보와 2차선에서 b번째 후보를 사용할 수 있을 때 만족하는 최소 거리 (거리를 계산해야하는 색의 수) 나는 후보를 하나씩 사용하면서 거리를 계산했다. 현재 후보군 위치가 (a, b)이므로 이 이전에 사용한 데이터를 가지고 현재 어떤 색상을 쓰고 있는지(이하 usedCnt) 또 그 색상을 모두 배치 했는지(이하 doneCnt)을 알 수 있다. 각 색마다 가장 왼쪽..

BOJ 1226 국회 [분류 - 다이나믹 프로그래밍, 그리디] [풀이] 당을 하나씩 추가하면서 전체의 절반을 초과하는 경우를 봐야한다. $$a_i=의석수$$ $$total=\sum_{i=1}^{n} a_i$$ $$ half=\lfloor{total/2}\rfloor $$ [접근] 0부터 half까지 순회하면서 현재 좌석수를 더해줌으로 절반을 초과하는지 확인하면된다. [그리디] 단, 좌석수 기준 비오름차순으로 정렬한 데이터를 가지고 추가해야한다. 조건에서 보면 현재 좌석 수를 x로 구성했을 때 x를 만들기 위해 연합된 당들 각각 하나를 빼면 좌석수가 절반 이하이어야만 한다. 현재 당의 좌석수가 ci라고 할때 현재 당을 제외한 나머지 당으로 half를 구성했다고 치자. 그러면 half + ci도 정답 후보가..

BOJ 1128 피보나치 냅색 [분류 - 브루트포스, 수학] 어렵다ㅏㅏ [풀이] [표현식] 제켄도르프의 정리(https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem)에 의하면 1보다 크거나 같은 자연수는 모든 계수는 0또는 1이고 인접한 피보나치 수에 대한 계수 ei × ei-1 = 0인 피보나치 수열로 표기할 수 있다. 또 이 수열은 유일(unique)하다. [전파] 가변량 ei를 i번째 피보나치 수에 대응되는 물건을 몇 개 쓸 수 있는지를 나타낸다고 정의하자. 주어진 무게 C에 대해 ei = 1인 가장 큰 피보나치 수 Fi에 대해 생각해보자. Fi 무게를 가지는 물건을 가방에 넣지 않으면 이 계수 ei는 이전 피보나치 Fi-1, Fi-2에 전파된다. 따라서 ei..

BOJ 18892 가장 긴 증가하는 부분 수열 ks [분류 : 다이나믹 프로그래밍] [풀이] [시작과 끝] 시작과 끝점이 K에 따라 달라질 수 있다. 모든 경우를 생각하기 귀찮으니 시작과 끝을 고정시키기 위해서 0번째에 충분히 작은 값(-10^9)을, N+1번째엔 충분히 큰 값(10^9)을 넣어주고 LIS를 구하자. 배열 A중에 0번째보다 작거나 N+1번째보다 큰 값은 존재할 수 없기 때문에 이 상태로 LIS를 돌려도 똑같은 답을 구해낼 수 있다. [추적] 0번째부터 시작해서 K번째 LIS를 찾아간다. 대신 사전순으로 처리해야하기 때문에 갈 수 있는 인덱스 구간을 정렬해주자. set을 이용하면 삭제도 편하고 정렬도 알아서 해주니 편하다. 정렬된 데이터에 대해 i번째에 접근했다고 하자. 그러면 세 가지 경..

BOJ 3217 malloc [분류 : 구현 / 세그먼트 트리] 최대 변수의 개수는 1000개, 또 메모리 할당 범위는 100 second >= _sz) break; cur++, nxt++; } if (nxt == allocated.end()) continue; else addr[var] = allocated.insert(nxt, { cur->second, cur->second + _sz }); } else { var = string(cmd).substr(cmd[0] == 'p' ? 6 : 5, 4); auto it = addr.find(var); if (cmd[0] == 'p') printf("%d\n", it == addr.end() ? 0 : it->second->first); else { if (..

BOJ 2507 공주 구하기 [분류 : 다이나믹 프로그래밍] [풀이] [O(N^3) 메모리] 가장 간단하게 p번째 섬을 출발 경로 또는 귀환 경로에 포함할지를 판단하는 dp를 생각할 수 있다. 하지만 이는 메모리 O(N^3)를 잡아 먹기 때문에 불가능하다. [접근 아이디어] 이런 왕복문제의 경우 시작점에서 도착점으로 가는 경로를 생각하자. 즉, 시작점은 항상 하나고, 도착점도 항상 하나로 두고 그 상태에서 서로 다른 경로를 구하면 그것이 곧 갔다가 오는 경로를 모드 셈해주는 것과 같다. [도달 검사] 첫 번째 섬을 제외한 나머지 섬은 반드시 한 번만 밟을 수 있기 때문에 왕복을 위해선 서로 다른 경로 두 개를 구성할 수 있는 경우의 수로 문제를 변형할 수 있다. 단, 한 경로는 현재 섬에서 현재 섬보다 ..

BOJ 4457 상근이의 자물쇠 [분류 : 다이나믹 프로그래밍] 독특한 문제 [풀이] [경우의 수] 트리를 구성할 때 트리 자체의 높이 h를 고정했다고 보자. 그러면 그 높이 h에서 n개의 노드를 배치해야 한다. h를 만드려면 현재 루트가 되는 노드를 제외한 두 서브 트리 중 하나가 반드시 높이 h-1를 가져야한다. 또 조건에서 두 서브 트리의 높이 차이는 1이하이어야 하므로 경우의 수는 세가지가 나온다. 왼쪽 서브 트리의 높이가 h-1, 오른쪽 서브 트리 높이가 h-1 왼쪽 서브 트리의 높이가 h-1, 오른쪽 서브 트리 높이가 h-2 왼쪽 서브 트리의 높이가 h-2, 오른쪽 서브 트리 높이가 h-1 [기저 사례] 기저 사례로는 h가 -1일 때 남은 노드의 수 n이 0이어야만 경우의 수로 포함시키도록 한..

BOJ 13433 기하 문제 [분류 : 브루트포스] [풀이] [순열] 기본적으로 N!을 생각할 수 있다. 단순히 원을 차례대로 나열하는 방법의 수로 생각하면 되겠다. (C++에선 next_permutation 사용) [유효성 검사] 원의 반지름 r1, r2, r3에 대해 r1 > r2, r3 > r2인 경우에 순서가 r1, r2, r3란 배치라면 유효성을 검사할 필요가 있다. 바로 이전 원 옆에 붙히지 못할 경우가 있단 의미다. [거리 계산] 바로 옆에 붙힐 수 없다면 x축 어디에 놓을 수 있는지 생각하기 전에 먼저 유효성 실패했을 때를 생각해보면 된다. 유효성 실패는 곧 아래 수식일 경우를 말한다. $$sqrt(x^2 + (r_{i} - r_{j})^2) \lt r_{i} + r_{j}$$ 결국 바로 ..

BOJ 12909 그래프 만들기 [분류 : 다이나믹 프로그래밍] [풀이] [노드의 수] 현재 노드 u에서 자식 노드를 추가하는 행위는 전체 사용할 수 노드 수가 줄어든다. 단 그 자식 노드를 루트로 하는 서브 트리의 크기(노드의 수)를 결정해줘야 한다. 당연한 소리지만 현재 N을 사용할 수 있다면 서브 트리의 크기는 최대 N-1다. [상태] 서브트리의 크기가 x라고 하자. 그러면 현재 노드 u에서 추가적으로 사용할 수 있는 노드 수는 N - x가 된다. 자식을 이미 하나 추가했으니 차수는 하나 증가한다. 결국 상태는 (노드 수, 차수)로 볼 수 있다. 노드의 수는 계속 줄어들 수 밖에 없으므로 이 상태를 유지하며 부분 문제를 해결, 부분 구조를 사용해주시면 되겠다. 더보기 #include #include..