답은 알고리즘 뿐이야!

문제 출처 : www.acmicpc.net/problem/1525 풀이 : BFS 문제입니다. 메모리 제한이 24메가로 작습니다 그렇기에 9개의 칸을 0~8의 값인지 9차원 배열로 판단할 시에 메모리 초과가 뜨게 됩니다. 그렇기에 [3][3] 배열을 long long 형 변수에 매핑시켜 그 값을 중복 체크 하시면 됩니다.

문제 출처 : https://www.acmicpc.net/problem/16978 풀이 : 세그먼트 트리 문제입니다. K번째 1번 쿼리가 진행 되었을때의 A[i] ~ A[j] 구간합을 구하는 문제인데, 세그먼트 트리 자체에 K번째 까지의 진행사항을 저장하기에는 너무 많은 메모리를 요구하기 때문에 다른 방안을 찾아야 합니다. 그래서 우리는 쿼리를 모두 받아놓고 K번째 1번쿼리

문제 출처 : https://www.acmicpc.net/problem/2414 2414번: 게시판 구멍 막기 첫째 줄에 N, M(1 ≤ N, M ≤ 50)이 주어진다. 다음 N개의 줄에는 M개의 문자로 게시판의 모양이 주어진다. 각각의 문자는 붙어 있으며, 구멍이 없는 부분은 '.', 구멍이 있는 부분은 '*'으로 주어진다. www.acmicpc.net 풀이 : 네트워크 플로우 최대 유량 문제입니다. 구멍이 없는 부분에는 테이프를 붙이면 안되므로 행과 열에 대해 구멍이 연속적으로 있는 부분을 묶어서 인덱스를 만들어 주시고 구멍이 있는 부분의 좌표(y,x)에 대해 행과 열의 인덱스를 Capacity가 1로 이어 주시면 됩니다.

문제 출처 : https://www.acmicpc.net/problem/5651 5651번: 완전 중요한 간선 입력은 여러개의 테스트케이스로 이뤄진다. 첫째 줄에는 테스트케이스의 수 K (1

문제 출처 : https://www.acmicpc.net/problem/13505 문제 풀이 : Trie 문제입니다. 각 수를 비트로 쪼갠뒤 비트가 0인지 1인지에 대해 판단을 하여 높은 자리 수 부터 Trie를 구성하시면 됩니다. 아래는 예제 1번을 간략하게 Trie로 구성한 그림입니다. 위의 그림은 간략히 그린 것이고 실제로는 31자리 부터 시작해야 합니다. Trie를 구성했으면 이제 가장 큰 XOR 값을 구해야합니다. XOR값이 가장 크기 위해서는 이러한 생각을 할 수 있습니다. 어떠한 수에 대해 Trie 에서 제일 큰 자릿수 부터 반대 비트를 찾아 내려 간다면 그 수에 대해 가장 큰 XOR값을 가진 수를 찾을수 있다! 위의 그림에 색깔펜으로 그린 부분이 위의 로직을 1과 2에 대해 실행했을때의 결..

문제 출처 : https://www.acmicpc.net/problem/2449 문제 풀이 : DP 문제입니다. cache[L][R] : L번째 전구부터 R번째 전구까지 통일 시키는데 색을 바꾼 최소횟수 양쪽 구간의 색을 통일 시킬때 변수를 하나 두시고 양쪽 구간의 시작 색깔이 같다면 바꾸는 비용을 0으로, 다르다면 바꾸는 비용을 1로 계산하여 쌓아가시면 됩니다.

문제 출처 : https://www.acmicpc.net/problem/2207 풀이 : 2-SAT 문제입니다. i번째 라운드에서 원장선생님이 무엇을 냈는지를 나타내는 변수를 Xi라 할때, 원장선생님은 바위 또는 가위만 낼수 있으므로 바위를 ㄱXi, 가위를 Xi라 두고 절을 구성한 후 CNF 가 TRUE가 되면 "^_^", FALSE가 되면 "OTL"을 출력하면 되는 문제입니다.

문제 출처 : https://www.acmicpc.net/problem/4354 풀이 : KMP의 Fail 함수를 이용해서 해결하는 문제입니다. abababab 라는 문자열이 있다고 가정해봅시다. 문자열의 길이는 len이라고 표현 하겠습니다. 이 문자열은 ab가 4번 반복되는 문자열입니다. 이 문자열의 Fail 값을 계산한다면 abababab abababab 00123456 이 나옵니다. 이러한 사실에서 우리가 알 수 있는 사실은 반복되는 횟수가 1이 아닌 문자열은 무조건 반복되는 기준이 있는 문자열이기 때문에 최대로 반복되는 문자열을 처음 지나는 순간 그 다음은 Fail 값이 계속 Fail[n] = Fail[n-1] + 1의 형태로 흘러가게 됩니다. 다시 abababab의 Fail값을본다면 최대로 반복..

문제 출처 : https://www.acmicpc.net/problem/1031 풀이 : Maximum Flow 문제입니다. 아래의 조건에 따라 푸시면 됩니다. 1. A팀의 경기수 총합 != B팀의 경기수 총합 => -1 2. A팀의 경기수 총합 != Maximum Flow => -1 3. A팀의 경기수 총합 == Maximum Flow => 사전순 정렬 이문제의 핵심은 3번 사전순 정렬인데 사전순 정렬은 엣지 하나를 고르고 엣지와 동일한 시작점에서 동일한 끝점으로 갈수있는 다른 플로우가 있는지 찾은 후 있으면 엣지의 플로우를 지워주고 경로에 Flow를 흘려주시면 됩니다. 단 찾을때 정렬을 해야하기 때문에 시작점과 끝점의 범위에 주의해야합니다. 만약 인풋이 2 2 1 1 1 1 일때, 1->3, 2->4..

문제 출처 : https://www.acmicpc.net/problem/3640 풀이 : MCMF 문제입니다. 1 을 source, V 를 sink로 잡고 mcmf를 해주시면 되는데 조건중에 정점 중복이 없다라는 말이 있으므로 정점 분할을 하고 V번 정점에서 V ' 번 정점으로 가는 Capacity를 2로, S번 정점에서 S ' 번 정점으로 가는 Capacity를 충분히 준 후 MCMF를 돌리시면 됩니다. 아래는 2번째 인풋을 모델링 한 그림입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 ..