KoreanFoodie's Study

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 원주율 같은거 좀 외우고 다니지 말자; [종만북 문제] 원주율 외우기 (문제 ID : PI, 난이도 : 하) 문제 자체는 어렵지 않다! 그냥 점화식만 잘 세우면 되는데... 일단 코드를 보자. #include #include "stdlib.h" #include #include #include using namespace std; int N; vector arr; vector cache; int diff(int i, int j) { if (i > j) return 0; if (j >= N) return 10; if ((j - i ..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 점화식을 잘 세워보자. [종만북 문제] 합친 LIS (문제 ID : JLIS, 난이도 : 하) 이것도 LIS 와 비슷한 로직을 적용하면 된다. 일단, jlis 함수를 다음과 같이 정의할 것이다. jlis(indexA, indexB) = A[indexA] 와 B[indexB] 에서 시작하는 합친 증가 부분수열의 최대 길이 순서를 딱히 지정하지는 않았으니 A[indexA] 와B[indexB] 중 작은 쪽이 앞에 온다고 가정하자. 그럼 점화식을 아래와 같이 세울 수 있다. 그럼 위의 점화식을 실제로 구현해 보자! 😊 #include ..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 먼저 완전 탐색부터 시작해보자. 그 후, 전체 답의 점수를 반환하는 것이 아니라 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꾸자. 2. 재귀 호출에서 이전의 선택과 관련된 정보는 최대한 줄이자. 그럼으로써, 우리는 최대한 중복되는 문제를 많이 만들어낼 수 있다. [종만북 문제] 최대 증가 부분 수열 (문제 ID : LIS, 난이도 : 하) 일단, 아래와 같이 간단하게 for-loop 으로 풀어볼 수 있다. #include #include "stdlib.h" #include #include using n..

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