그냥 하는 노트와 메모장

[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.처럼 서로 종속적이기 때문에 종속의 의미 지니게끔 접근하는 것이다. 주어진..

* CS Academy Round #9 - Array Removal[ 분류 - DSU ] 이 문제의 특성은 다음과 같다. 1. 지워야하는 순서가 정해져 있다. 2. 순서가 정해져 있는 만큼, k 번째 수를 지웠을 때 큰 수 S_k와 k+1번째 수를 지웠을 때 큰 수 S_k+1는 서로 종속적이다. 3. 수를 제거해나가며 큰 수를 출력해야 한다. 먼저 Greedy하게 접근해보자. S_k와 S_k+1를 비교해보자면 S_k >= S_k+1이 성립함을 직관적으로 알 수 있다. 또한 2.번에 의해 서로 종속적이기 때문에, "순서를 거꾸로" 생각하자. 거꾸로 생각하면, 초기에 없는 데이터에서 하나씩 생성됨을 알 수 있다. 따라서 이를 DSU로 합치는 방식을 택하며, 지금 합친 것과 지금까지의 최대값을 비교해나가며 답..

* 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번 이동하는 최대..

* Algospot - 정렬 게임(SORTGAME, ) [ 분류 - BFS ] 간단한데, 이상하게 자꾸 시간초과가 뜨는 문제다. * 접근 방법 1. 길이가 x인 수열을 한 번 이상의 연산을 수행했을 때, 정렬 결과로 나올 수 있는 경우의 수는 x!이다. 2. 내부에서 연산을 수행하는 속도는 약 O(x)다. 따라서 1.의 결과로 보면 속도는 최대 8!*8이다. 3. 하지만 이를 들어오는 쿼리마다 수행할 수는 없으므로 "미리" 저장을 해놓고 들어오는 입력에 따라 O(C lg(x!*x)) 시간으로 찾을 수 있도록 한다. 4. 최대가 8이므로 길이 8짜리만 구하고, 나머지 길이에 대해서는 남는 부분을 오름차순으로 채우고 찾으면 된다. - 코드 #include #include #include #include #i..

* Algospot - 어린이날 (CHILDRENDAY, https://algospot.com/judge/problem/read/CHILDRENDAY) [ 분류 - BFS/ Mathematics ] 접근 방식이 다소 까다롭다. N명 중 M이 하나씩 더 받기 위해선 N%ans = M이며 이 나머지에 대해 사이클이 존재함을 알아야 한다. 또한 이를 증명하는 페르마의 소정리에 대해 알고 있어야 한다. * 접근 방법 1. 찾고자 하는 ans에 대해 N%ans = M이기 위해선 기저(시작 지점)은 숫자(한자리 수)부터 시작한다. 여기에 하나씩 이어붙이며 진행하는 BFS를 구성한다. 2. 나머지이기 때문에 후보를 [0, N]으로 줄일 순 없다. 적어도 하나 이상의 장남감을 줘야하기 때문에 [0, 2*N]가 후보가 ..

* 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차원 배열로 두고 접근할 ..

* BOJ 1765 - The Gangs (닭싸움 팀 정하기, https://www.acmicpc.net/problem/1765) [ 분류 - BFS, DFS/ DSU/ Hashing ] 이분 그래프가 여러개 생길 수 있는 구조를 생각하자. 조건에 따르면 특정 Component A에 대해 A의 적은 단 하나 밖에 존재하지 않는다. 따라서 자신의 적을 저장할 자료구조(Hashing)와 친구를 저장할 자료구조(인접 행렬 및 리스트/ DSU)를 정해야 한다. * 풀이 친구를 저장할 때는 인접 행렬 및 리스트로 저장하는 것은 꽤 간단하다. 하지만 적을 저장할 때는 어떻게 해야 할까? 이분 그래프이기 때문에 적을 단 하나만 저장한다. 이를 루트로 두고, 들어오는 데이터에 따라 자신의 적을 읽어들여, 적과 적을 이..

* BOJ 3964 - 팩토리얼과 거듭제곱 (https://www.acmicpc.net/problem/3964) [분류 - Mathematics/ GCD/ Sieve of eratosthenes ] 으음.. 생각해야할 부분이 굉장히 많은 문제다. 사실 어떻게 풀어야하겠다는 접근 자체는 다소 간단하다. 하지만 이 과정에서 발생할 수 있는 Overflow를 까다롭게 다뤄야 풀 수 있다. * 접근 방식 1. n!이 k^i에 나누어 떨어지기 위해서는 k^i = GCD(n!, k^i)이어야 한다. 2. 최대 공약수의 후보를 산출하기 위해서 k^i는 lg(k)의 시간이 걸리는 반면 n!은 lg(n!)이 걸린다. k^i가 lg(k)인 이유는 i제곱꼴은 k의 약수의 승수에 i를 곱하면 되기 때문. 따라서 후보를 추출하..

* BOJ 1103 - 게임 (https://www.acmicpc.net/problem/1103) [ 분류 - DFS/ Dynamic programming ] 여러분이 이 문제가 그래프임을 알았다고 가정하고 정리해보자. 1. 동전은 (0,0) 에서 시작한다. 2. 동전이 있는 지점에 있는 숫자만큼 상하좌우로 이동할 수 있다. 3. 구멍 H에 들어가거나 보드 밖으로 나가는 것도 동전을 움직이는 것으로 간주한다. 따라서 (0,0)부터 시작해서 상하좌우로 움직일 수 있는 곳의 최대치로 이동한다. 이는 memoization으로 구현할 수 있다. 하지만 무한번 움직일 수도 있는데, 바로 사이클이 생기는 경우다. 사이클이 하나라도 생긴다면 그 안에서 계속 움직일 수 있기 때문에 -1을 출력해줘야 한다. 따라서 me..

* BOJ 2981 - 검문 (https://www.acmicpc.net/problem/2981) [ 분류 - GCD ] 수학 개념이 필요한 문제다. 주어지는 N개의 수를 정렬한 수열의 결과를 a1, a2, ..., an 이라 하자. 임의의 정수 M으로 나눴을 때 수열의 나머지를 m라고 할 때, 수식을 아래처럼 나타낼 수 있다. 이에 대해 근접한 원소끼리 차이를 정리해보면, ... 서로 다른 두 원소 차이에 대해 "약수"로 M이 들어가 있는 것을 확인할 수 있다. 따라서 이 차이에 대해 최대공약수를 구하여 그것의 약수를 모두 출력하면 된다. - 코드 #include #include #include using namespace std; int gcd(int p, int q) { if (q == 0) ret..

[ 분류 - GCD ] 재밌는 문제다. 이 문제는 팩토리얼과의 GCD를 구하는 문제다. GCD에 요소가 될 수 있는 후보를 먼저 생각해보자. n!은 우선 냅두고.. k를 생각하자. n!은 너무 값이 클 수 있기 때문이다. 그렇다면 GCD 후보는 k의 약수로 요약할 수 있다. 또한 k를 소인수 분해하여 정리하면 아래와 같이 표현할 수 있다. 따라서 후보는 1부터 n을 곱했을 때, 그 값에서 소수 p1부터 px까지로 포함된 최대의 수로 나타낼 수 있다. 즉, 로 표현할 수 있다. 따라서 를 아래 수식처럼 표현할 수 있다. 접근법을 알았으니, 이제 n!에 대해 gx 값을 구하는 방법을 알아보자. 간단하게 나누기로 특정 소수의 px의 승수를 쉽게 알아낼 수 있다. 만약 px=2이라면 아래처럼 표현할 수 있다. ..

* BOJ 11097 도시계획 (https://www.acmicpc.net/problem/11097) [ 분류 - SCC(Strongly connected components) ] 다소 까다로운 문제? 였다. 반면 접근 방식이 매우 여러가지라 아래 해설도 그 중 하나라고 봐주시면 되시겠당 :) 문제가 물어보는 것은 플로이드의 결과라고 생각할 수 있는 인접 행렬이 주어졌을 때, 이를 구성할 수 있는 가장 적은 도로를 쓰는 도로망을 구성하는 것이다. 그리고 일방통행 도로이기 때문에 방향 그래프인 것을 알 수 있다. 이 문제를 "최대한 도로를 지우는" 과정으로 볼 수 있다. 인접 행렬에서 지울 수 있는 도로를 모두 지워야 최소 크기의 도로망을 구성할 수 있기 때문이다. 임의의 정점에 대해서 생각해보자. 정점 ..