KoreanFoodie's Study

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 평범한 DP 문제로, for-loop 혹은 재귀함수로 풀 수 있다. [종만북 문제] 삼각형 위의 최대 경로 (문제 ID : TRIANGLEPATH, 난이도 : 하) 일단 for-loop 으로 푼 버전을 보자. #include #include "stdlib.h" #include #include using namespace std; int N; int tri[100][100]; int cache[100][100]; void sol() { cache[0][0] = tri[0][0]; for (int i = 1; i < N; ++i) ..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. DP 문제는 중복 계산되는 것이 무엇인지 체크하는 것이 중요하다. [종만북 문제] 와일드카드 (문제 ID : WILDCARD, 난이도 : 중) 일단 DP 를 이용해서 한 번 풀어보았다. 부끄럽지만 나는 처음에 이렇게 풀었다 : #include #include "stdlib.h" #include #include #include #include using namespace std; /************************************************************************************..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. DP 문제를 풀 떄는, 먼저 완전 탐색으로 풀 수 있는지 체크를 해 보고, 메모이재이션이 가능한지를 파악하는 것도 좋은 접근 방법이다. [종만북 문제] 외발 뛰기 (문제 ID : JUMPGAME, 난이도 : 하) 바로.. 예제 코드로 들어가 보자. #include #include "stdlib.h" #include #include #include using namespace std; /*********************************************************************************..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 무식하게 풀면, 시간 복잡도가 O(N^2) 가 되어 시간초과가 발생한다. 2. 카라츠바의 알고리즘을 사용해 보자! [종만북 문제] 팬미팅 (문제 ID : FANMEETING, 난이도 : 상) 팬미팅 문제는 종만북에서 처음으로 나오는 '상' 난이도의 문제이다. 하지만 걱정하지 마라. 손은 눈보다 빠르니까... 근데 사실 손이 빠른 건 별로 도움이 안된다. 어쨌든, 이 문제는 '무식하게' 푼다고 하면 O(N^2) 로 풀어볼 수도 있을 것이다. 예시 코드는 아래와 같다(시간초과 함에 유의). #include #include "stdl..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 분할 조건을 잘 따져보자. [종만북 문제] 울타리 잘라내기 (문제 ID : FENCE, 난이도 : 중) 이 문제는 아래처럼 무식하게 풀면 O(N^2) 에 풀 수는 있지만, 시간초과가 난다. 😅 이를 해결하기 위해, 우리는 분할 정복을 사용할 것이다. (c) 가 조금 까다로워 보일 수 있는데... 핵심은, 걸쳤을 경우 해당 판자를 반드시 포함한다는 것이다! 즉, (a) 에서부터 시작한다고 가정하자. 판자의 왼쪽과 오른쪽 중, 우리는 더 높이가 큰 것을 택한다. 고로 (b) 에서 오른쪽이 선택된다. 다시 (b) 에서는 왼쪽과 오른쪽..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 단순하게 생각해라 [종만북 문제] 쿼드 트리 뒤집기 (문제 ID : QUADTREE, 난이도 : 하) 음.. 쿼드 트리는 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 하나이다. 쿼드 트리는 주어진 공간을 항상 4개로 분할하여 재귀적으로 저장하는데, 이번에는 검은색/흰색밖에 없는 그림을 압축한 예제를 풀어 볼 것이다. 😎 일단 단순히 재귀적으로만 풀면, 아래와 같이 풀어볼 수도 있다(책에 나온 버전은 그 다음에 소개할 것임). #include #include "stdlib.h" #include u..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 완전 탐색 문제이긴 하지만, 문제를 살짝 변형해서 생각하면 좋다. [종만북 문제] Synchronizing Clocks, 시계 맞추기 (문제 ID : CLOCKSYNC, 난이도 : 중) 이 문제는 .. 여전히 완전탐색으로 풀 수 있다. 다만, 사실 잘 보면 스위치를 누르는 순서는 상관이 없다는 것을 눈치챌 수 있다. 따라서, 스위치 10개를 최대 3번씩 눌러가면서 답을 찾아나가면 된다. 최대 상한은 4^10 이 될 것이다! 😉 #include #include "stdlib.h" #include using namespace std..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 완전탐색으로 블록을 덮어보자. 잘. [종만북 문제] 게임판 덮기 (문제 ID : BOARDCOVER, 난이도 : 하) 일단, 해당 문제는 사실 블록을 어떻게 덮을지만 결정하면 대략적으로 풀이를 만들어 볼 수 있다. 책에서는 위와 같이 덮는 방법 4개를 제시한다. 우리는 이 모델을 바탕으로 배열을 만들어 덮는 가짓수를 순회하도록 만들 것이다. #include #include "stdlib.h" #include using namespace std; int M, N; int board[20][20]; int ans; int blank..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 재귀 + 완전 탐색으로 풀 수 있다. [종만북 문제] 소풍 (문제 ID : PICNIC, 난이도 : 하) 이번 문제도 일단, 완전 탐색으로 풀 수 있는 문제이긴 하다. 거기에 약간의 재귀가 필요한데... 일단 소스 코드부터 첨부해 보겠다. #include #include "stdlib.h" #include using namespace std; int N; vector pairs; int ans; void makeGroup(vector& visit, int cur, int len) { if (len == N) { ans += 1;..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 기본적으로 완전 탐색으로도, 예제로 주어진 케이스는 해결 가능하다. 하지만 제출하면 Timeout 이 발생한다. 2. Timeout 해결을 위해서는... [종만북 문제] 보글 게임 (문제 ID : BOGGLE, 난이도 : 하) 기본적으로 완전 탐색으로 코드를 짜 보자. 무식하게 탐색한다면, 인접한 각 탐색 마다 인접한 8 개의 문자를 확인해야 하므로, 시간 복잡도는 O(8^N) 이 될 것이다. #include #include "stdlib.h" #include #include using namespace std; char boa..