KoreanFoodie's Study

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 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..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)을 읽으며 유용한 내용을 정리해 보도록 하겠습니다. 모든 내용을 요약하는 것은 아니며, 대회에 포커싱을 맞춘 부분은 다루지 않을 수도 있습니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 수행 시간 어림짐작은 유용하지만, 엄밀하지는 않으니 최적화 시에는 여러 인자들을 함께 고려해 보자. 2. 알고리즘의 정당성 증명은 해당 알고리즘의 통찰을 이해함에 있어 중요하다. 3. 알고리즘의 정당성 증명 방법은 귀납법, 반복문 불변식, 귀류법, 비둘기집의 원리, 구성적 증명 등이 있다. *챕터 2 에서는 한 번 되짚어 볼 만한 내용을 일부 발췌해 정리해 보겠습니다. 수행 시간 어림짐작하기 일반적으로 우리는 Time..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 기본적으로는 이중 for-loop 으로 풀 수 있으나, DP 를 사용하면 시간을 조금 단축할 수 있다. 2. 소수점 오차에 유의하자. 록 페스티벌 (난이도: 하, 문제 ID : FESTIVAL) 사실 2중 for-loop 만 돌리면 쉽게 풀 수 있는 문제이긴 하다. 따라서 따로 설명을 길게 적지는 않고, 코드에 주석을 조금 달아 두었다! 😄 #include #include "stdlib.h" using namespace std; int N, L; int days[1000]; int dp[1000]; double ans; doub..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)을 읽으며 유용한 내용을 정리해 보도록 하겠습니다. 모든 내용을 요약하는 것은 아니며, 대회에 포커싱을 맞춘 부분은 다루지 않을 수도 있습니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 프로그래밍은 문제 해결이다. 2. 간결하고 모듈화된 코드를 짜라. 이는 버그를 줄여주고 디버깅 효율을 높여준다. 3. 자주 범하는 실수에 대한 유형을 알아두자. 프로그래밍은 문제 해결이다. 1장에서는 알고리즘에 대한 코딩에 대한 저자의 철학과, 앞으로 다룰 주제에 대한 간략한 맛보기(?)가 제공된다. 거기에 배운 지 오래되어 기억의 저편에 묻혀 있거나, 생각해보면 좋은 꿀팁들에 대해서도 조언을 아끼지 않는다. 이번 글..