KoreanFoodie's Study

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 간단한 DP 문제지만.. 재귀로도 풀어보자. [종만북 문제] 삼각형 위의 최대 경로 수 세기 (문제 ID : TRIPATHCNT, 난이도 : 중) 이번 문제도, 간단하게 DP 로 풀 수 있다. 예를 들어 다음과 같다. #include #include "stdlib.h" #include #include #include #include using namespace std; /*****************************************************************************************..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 간단한 DP 문제다. [종만북 문제] 타일링 (문제 ID : TILING2, 난이도 : 하) 간단한 DP 문제다. #include #include "stdlib.h" #include #include #include #include using namespace std; /****************************************************************************************************/ int N; int cache[101]; void preCalc() { for (..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 최적 부분 문제를 찾는 것은 간혹, 매우 쉽지 않은 일이다... 무식하게 푸는 전법부터 시작하면 큰코가 다칠 수 있다. 근데 나 코 낮은데.. 어쨌든 다쳤다. [종만북 문제] Quantization (문제 ID : QUANTIZE, 난이도 : 중) 이 문제는 아이디어가 필요하다. 단순히 수열을 정렬한 다음에, 숫자를 최솟값에서 최댓값까지 넣는 방식으로는 풀 수 없기 때문이다. 그런데 이렇게 묶어보면 어떨까? 이렇게 묶어 놓고 보면, 인접한 숫자끼리 적절히 묶고, 최소 오차를 내는 수를 찾는 문제로 변형할 수 있다! 그럼 아래와 ..

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