그냥 하는 노트와 메모장

* BOJ 3032 승리[분류 - 다이나믹 프로그래밍] 원형 다이나믹을 많이 풀어봤다면 비교적 쉽게 느껴질 문제입니다. [풀이] 1. 1부터 N까지 각각을 첫 번째 수로 보고 진행한다. 2. 고를 수 있는 수가 최대 두 개가 되는데, 이 때 어떤 것을 골라야 필승인지를 검사하는 로직을 추가한다. 즉, 상대가 무조건 지는 경우가 있는지 탐색한다. 현재 골라야하는 플레이어는 골라야하는 수의 구간으로 알 수 있으며 그 때까지 선영이가 선택한 홀수의 개수를 저장해두었다가 모든 수를 다 사용했을 때, 누가 승리하는지 판단하도록 구성해주면 된다. dp[l][r][c] = 선영이가 c개의 홀수를 얻었고, 현재 플레이어는 l번째 수 또는 r번째 수를 선택할 수 있을 때의 승리 가능성 #include #include c..

* BOJ 12103 짝합 수열, 7976 수열 [분류 - 다이나믹 프로그래밍] 1. [패턴] 0또는 1을 요소로 길이 k를 갖는 패턴 배열을 생성해보자. 대신 합이 짝수이어야 한다. 패턴의 의미는 해당 위치가 1이면 홀수 0이면 짝수를 의미한다. 2. [규칙성] 임의의 배열을 생성했다면 마지막 요소 이후의 것을 생각해보자. 만약 길이 k를 가지는 패턴이 처음에 0으로 시작한다면 그 다음 인덱스부터 k길이가 합이 짝수이기 위해서는 다음 요소(k+1번째)는 0일 수밖에 없다. 마찬가지로 1로 시작해도 그 다음 요소는 1일 수 밖에 없다. 결국 길이 k마다 처음에 정했던 패턴이 계속 나올 수 밖에 없고, 이 패턴 중에 주어진 배열 a를 패턴에 적용했을 때 가장 적은 비용으로 바꾸는 것을 찾으면 된다. 예시)..

* BOJ 15807 *빛*영*우*[분류 : 다이나믹 프로그래밍] [풀이] 좌표 (X, Y)에 대한 2차원 다이나믹을 생각해보자.dp[x][y] = (x, y) 좌표에 대한 빛의 세기 1. 영향력 당연히 y좌표가 낮은 곳에 설치된 조명들은 상대적으로 y좌표가 높은 곳에 있는 부분에 영향을 미칠 수 있다. 2. 기울기 조명에 대해 존재할 수 있는 기울기는 두 개밖에 없다. y=x와 y=-x. 3. [조명] 현재 좌표에 조명이 설치 되어 있다면 그 조명 수만큼 추가해준다. [같은 직선 위] 현재 좌표 (x, y)에 해당하는 dp[x][y]를 구하기 위해서는 (x, y)를 포함하고 기울기가 1이거나 -1인 것을 생각해보자. y값이 현재보다 작은 모든 조명에 대해 같은 기울기를 가지며 같은 직선 상에 있는 것을..

* BOJ 3948 홍준이의 친위대[분류 - 다이나믹 프로그래밍] [풀이] 만족하는 나열은 두 종류가 존재한다. 작큰작큰 또는 큰작큰작. 1. 상태를 dp[작큰인지 큰작인지][수열을 구성하는 인원수]로 둔다. 2. 현재 인원수 i명 계산할 때 인원수 i-1명에서 가장 키가 큰 인원을 넣는다고 생각하자. 이 가장 큰 인원을 기준으로 왼쪽에 설 인원, 오른쪽에 설 인원을 정해보자. 왼쪽에 있을 인원들의 수가 짝수라면 시작을 큰작으로 시작할 수 밖에 없다. 반면 오른쪽에 있는 인원들은 무조건 작큰으로 시작하면 된다. 여기서 왼쪽에 배치할 인원을 골라보자. i-1명중 j를 고르게 될텐데, 중요한 점은 어느 j명을 골라도 무조건 j명 배치가 가능하다는 점이다(모두 서로 다른 키를 가지고 있음). 따라서 i-1명 ..

* BOJ 2112 두 부분 문자열, BOJ 3244 두 부분 문자열2[분류 : 다이나믹 프로그래밍] 1. B문자열에 대한 모든 가능한 문자 26개에 대해 위치를 오름차순으로 저장하자. 어떤 문자가 특정 위치 b를 포함한 이후에 존재하는지 안하는지 판단하기 위함이다. 2. 다이나믹 상태 최대 공통 부분 수열(LCS)을 찾는 것처럼 생각해보자. 현재 A의 위치 a, 현재 B의 위치 b로 상태 (a, b)에서 문제에서 요구하는 문자열의 길이를 찾아보자. 1. A[a] 문자를 정답 문자열에 사용하지 않는다. 이 때는 a위치를 한 칸 이동한다. b는 움직이지 않는다. 여기서 b를 움직여버리면 구조상 B 부분 문자열을 모두 확인할 수 없게 된다. 2. A[a] 문자를 정답 문자열에 사용한다. 2-1. A[a]에 ..

* BOJ 5580 빙고 게임[분류 : 다이나믹 프로그래밍] [풀이] 똑같은 빙고라는 의미는 어떤 수열을 나열하여 빙고에 체크할 때 의미가 같으면 안된다는 소리. 따라서 행과 열을 뒤집은 빙고판은 의미적으로 같게 된다. 결국 문제는 집합 {A| 1

* BOJ 3026 V[분류 : 다이나믹/ 가지치기] [풀이] 컷팅이 중요한 문제. 1. X가 10^5보다 크거나 같은 경우 A=1, B=10^11인 최악의 경우에서 X의 배수를 구할 때 10^6의 연산수가 필요해요. 이 경우엔 충분히 브루트포스로 계산이 가능합니다. 2. X가 10^5보다 작은 경우 최악의 경우를 생각해봅시다. X = 1, A = 1, B = 10^11이라면 브루트포스로 최대 10^11번을 계산해야하기 때문에 시간초과가 날 것임이 자명합니다. [다이나믹] 자리수로 생각해봅시다. 수가 최대 10^11이므로 12자리가 자리수 최대가 됩니다. 관찰포인트는 인접한 자리수 간의 관계입니다. X=151이고 현재 10^3의 자리수를 구해야한다고 해봅시다. 이 때 1의 자리, 10의 자리 그리고 10..

BOJ 2957 - 이진 탐색 트리 (BST) [ 분류 - BST ] 역시 이진 탐색 트리을 포함하여 자료구조 자체를 물어보는 문제는 증명 문제로 이어지는 것이 운명인가보다.. 당연하게도 삽입이 O(N)인 구조이기 때문에 O(N^2)으로 데이터를 확인하는 것은 시간초과로 이어질 수 밖에 없다. 명제) 삽입할 노드를 x라고할 때, 이 x는 직전원소(predecessor) 또는 직후원소(successor) 중 하나의 자식으로 가도록 되어 있다. 증명) 직전원소를 P, 직후원소를 S라고 지칭하자. 아래 상황을 고려해보자. 1. P와 S가 루트의 같은 서브트리에 있는 경우 x가 다른 서브트리에 삽입되려는 경우 P.key < x < S.key 이기 때문에 반드시 x도 같은 서브트리에 있어야만 성립 2. P와 S가..

BOJ 9522 - 직선 게임[ 분류 : 이분 매칭(Bipartite matching), Greedy, Game theory ] 문제가 다소 독특하여 포스팅하고자 한다. 나는 증가경로를 이용하여 접근해봤다. 문제를 보면 알겠지만, 한 점에 대해 x축 또는 y축에 그을 수 있으므로, 총 2개의 직선을 그을 수 있다. 그렇다면 처음에 게임을 시작하는 상근이는 시작할 점과 축을 정하고, 그 이후에 여기에 종속되어 번갈아 가며 이전 직선 위의 점을 선택해야 한다. 즉, 상근이는 점뿐만 아니라 축도 정할 수 있다. 축이 정해진 시점에서 x축과 y축이 번갈아가며 등장하는 구조가 될 수밖에 없다(1). 또 x와 y에 대해 이분 그래프를 구성할 수 있다. x축에 평행하는 서로 다른 두 개의 직선은 절대로 겹칠 수 없고..

[Network flow, MCMF] Graph modeling practices 네트워크 플로우 및 MCMF에서는 그래프 모델링이 큰 비중을 차지합니다. 모델링을 하고나서 플로우 흘리는 개념은 고정되어 있으나, 그 문제가 그래프인지 또 그래프임을 알더라도 모델링을 하지 못하면 풀기 못하는 경우가 허다합니다. 이 게시물은 그래프 모델링에 있어, 신기하거나 재밌게 느꼈던 문제 및 제가 어떻게 그래프 모델링 했는지 소개하고자 합니다. 물론! 다른 풀이가 있을 수 있으니 참고바래요 :) ※ 이분 그래프에 대한 내용은 포함되지 않았습니다. 호프 크로프트 또는 이분 매칭 문제를 찾으시는 분은 다른 게시물을 찾아보시길 바래요. ※ 소스코드는 일부러 첨부하지 않았습니다. 제 소스가 궁금하신 분들은 댓글 남겨주시면 쪽..

* XOR 그룹 [ 분류 - DSU ] CS Academy Round #9의 Array Removal이라는 문제를 먼저 푸는 것을 권장합니다. 1. 수가 작은 것 부터 제거해나가므로, 지우는 순서는 정해져 있다. 2. k번째 수를 제거했을 때의 XOR 그룹의 합 최대값과 k+1번째 수를 제거했을 때의 XOR 그룹의 합 최대값은 서로 종속적이다. 3. 지우는 과정에서 나오는 XOR 그룹의 합 최대가 되는 값을 출력한다. 삭제하는 순서대로 답을 도출해내기란 쉽지 않다. 따라서 문제 접근 방식을 조금 다르게 해야하는데, 삭제하는 과정 자체에 의미가 없다는 것을 깨닫는 것부터 시작한다. 무슨 소리나면, 1.처럼 순서는 정해져 있으며, 2.처럼 서로 종속적이기 때문에 종속의 의미 지니게끔 접근하는 것이다. 주어진..

* BOJ 2549 - 루빅의 사각형 [ 분류 - BFS(Bidirectional search)/ Backtracking ] 푸는 방법이 다소 다양해서 포스팅하고자 한다. 주어진 문제에서 보면 최대 7번까지만 움직여도 충분히 해결가능한 입력만 주어진다고 한다. 그렇다면 주어진 입력과 목표 4x4배열을 E와 S라고 하자. 그러면 E가 최대 3~4번, S가 최대 3~4번을 움직이면 그 안에 겹치는 교차지점이 반드시 생긴다. 특정 지점 4x4 배열 k에 대해 움직일 수 있는 가지수는 (4+4)*3이 된다. 즉 24 가지수가 나올 수 있는데, S또는 E에서 최대 7번을 움직이기 때문에 24^7의 경우의 수가 나오는데 이 값은 너무나 크다. 시간초과가 자명하다. 따라서 S,E가 교차지점까지 3~4번 이동하는 최대..

* BOJ 3987 - VOYAGER (보이저 1호, https://www.acmicpc.net/problem/3987) [ 분류 없음 ] 지정된 좌표에서 시작해서 상하좌우 방향으로 진행할 때, 가장 많은 칸을 밟을 수 있는 것이 답이 된다. 이전 포스팅과 비슷한 문제이긴 하다. 방향이 좌표당 4개가 있기 때문에 해당 방향으로 또 방문한다면 이를 사이클로 보자. 사이클이 존재한다면 무한히 반복할 수 있기 때문에 Voyager를 출력해야 한다. 단, 그 무한히 반복할 수 있을 때의 처음 방향을 출력해야 한다. 가령 오른쪽으로 시작했을 때 반복이 된다면 아래처럼 출력한다. RVoyager - 코드 #include #include int main() { char board[500][501], dirp[]="U..

* BOJ 6084 - Laserphones (레이저 통신) [ 분류 - BFS ] 이 문제는 비슷한 문제가 있긴하다. 어떤걸 먼저 풀어도 상관은 없다. (거울설치 - https://www.acmicpc.net/problem/2151) 문제에서 요구하는 것은 C에서 C로, 레이저를 쏠 때 필요한 거울의 수다. 단 90도 로만 반사된다. 가령 d방향으로 레이저가 진행하고 있다고 가정해보자. 그렇다면 현재 바라보는 방향을 기준으로 직진, 좌우 밖에 갈 수 없다(180를 반사, 즉 오던 방향으로 쏠 순 없음). ↑ → / → ＼ ↓ → → → * 접근 방법 1. 두 개의 C 중 하나를 Source로 두고, 4 방향으로 레이저를 쏘는 것으로 시작한다. (시작할 때는 어느 방향이라도 가능하기 때문. 2. 막상 발..

* BOJ 5213 - TOTEM (과외맨) [ 분류 - BFS,DFS / 기타 최단경로 알고리즘 ] 주어진 문자들을 어떻게 노드로 정의할 것이며, 어떻게 자료구조를 설정할 것인지 물어보는 문제. 단순 최단경로 알고리즘을 사용한다면 별다를 문제는 없다. 문제에서는 타일은 두 개의 숫자로 이루어진다. 두 개의 숫자는 각자 '칸'을 의미하며 최대가 6이다. 인접한 타일과 같은 숫자로 접점이 있다면 두 타일은 이어져 있다고 볼 수 있다. * 접근 방식 1. 각 타일은 2개의 칸이고, 각 칸의 최대가 6이므로 두자리 수 하나로 퉁칠 수 있다. 2. 입력으로 주어지는 순서는 맨위 좌측 타일부터 맨 아래 우측 타일까지를 주어주므로 indexing 절차가 필요함을 알 수 있다. 즉, 단순 2차원 배열로 두고 접근할 ..