답은 알고리즘 뿐이야!

문제 출처 : https://www.acmicpc.net/problem/2342 문제 풀이 : DP문제입니다. cache[idx][l][r] : idx번째 지시사항이고 왼발이 l번째칸 오른발이 r번째 칸에 있을때의 사용된 최소힘 이라고 두고 cache를 쌓으시면 됩니다. 칸별로 이동시 드는 힘은 dir[5][5] 배열을 선언하여 편하게 처리하도록 합시다.

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

문제 출처 : https://www.acmicpc.net/problem/14725 풀이 : 문자열로 트리를 구성하는 문제입니다. 문제에서 주어지는 인풋 대로 트리를 채워나가시되 이진 트리가 아닌 N진 트리로 구성하시면 됩니다. 저는 정렬을 하기 위해 처음부터 사전순으로 비교하여 현재 인덱스의 스트링이 사전순으로 뒤에있으면 그 자리에 삽입하고 나머지를 뒤로 푸쉬해주는 방식으로 하였습니다.

문제 출처 : 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 ..

문제 출처 : https://www.acmicpc.net/problem/2367 풀이 : 네트워크 플로우 (Maximum Flow) 문제입니다. 파티에 N명의 사람이 오고 D개의 음식을 준비해야하는데 한 사람당 음식을 K개 준비할 수 있고 같은 음식은 1개만 준비할 수 있습니다. 따라서 다음과 같이 모델링 할 수 있습니다. 1. Source에서 사람으로 K만큼의 Capacity를 가진 Edge를 연결 2. 사람에서 각 사람당 준비할 수 있는 음식으로 1만큼의 Capacity를 가진 Edge를 연결 (한개의 음식은 한사람당 하나만 들고갈수 있으므로) 3. 각 음식에서 Sink로 가져올 수 있는 갯수만큼의 Capacity를 가진 Edge를 연결 예제의 경우를 네트워크 플로우로 모델링 하면 아래와 같은 모형이..

문제 출처 : https://www.acmicpc.net/problem/13511 풀이 : LCA 문제 입니다. 첫번째 쿼리를 처리하기 위해선 아래와 같이 LCA를 구하기 위해 전처리를 할때 cost 값도 같은 점화식으로 구해주시면 되고, for (int i = 1; depth[ni] > 1 > b >> c; if (a == 1) cout

1. 신청하게된 계기 살짝 공부하다가 현타가 온 시기여서 적당히 프로젝트만 하고 있었는데, 졸업반 친구가 이런 특강도 있다고 가서 들어보는게 어떻겠냐고 권해줘서 존재를 알게 되었다. 기초 자료구조나 알고리즘은 탄탄하다고 생각하고 있었기 때문에 중~고급 알고리즘으로 지식의 폭을 확장 시킬 수 있는 좋은 기회라고 생각하여 고민도 하지 않고 바로 신청하였다. 2. 입과테스트 나는 이미 SW 역량테스트 A+형을 보유중이였기 때문에 입과테스트는 따로 치루지 않았고, 바로 신청한 차수에 입과하게 되었다. 3. 배우는 내용 원래 저번 특강까지는 기하도 있고 자구나 알고리즘 기초 같은건 대충 하고 넘어갔다던데 이번 특강에서는 그부분을 좀더 잘? 가르쳐 주기 위해 기하를 빼고 이 시간을 늘렸다고 한다. ( 기하 못배우는..

문제 출처 : https://www.acmicpc.net/problem/15671 풀이 : 문제 조건이 시키는대로 짜면 되는 문제입니다. (시뮬레이션...? 구현...?) 문제에 주어진 인풋대로 하면 무조건 정상적인 게임으로 성립이 됩니다. 조건 1. 처음 상태는 {{W,B},{B,W}}이다. 2. 돌은 반드시 포위하여 뒤집을 수 있는 곳에 놓아야 한다. 3. 돌을 뒤집을 수 없으면 상대 차례로 넘어간다. 2번 조건이 제일 중요한 조건으로 돌을 놓은 곳부터 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 2..