KoreanFoodie's Study

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 흠.. 이 정돈가? [종만북 문제] 두니발 박사의 탈옥 (문제 ID : NUMB3RS, 난이도 : 중) 여기까지 왔으면, 이제 DP 문제는 패턴이 학습되었을 것이다. 그냥... 아래처럼 풀면 된달까요(웃음). #include #include "stdlib.h" #include #include #include #include #include using namespace std; /*************************************************************************************..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 언뜻 불가능해 보이는 문제도, 문제의 조건을 잘 보면 부분 문제의 조합으로 분해해 볼 수 있다! [종만북 문제] 폴리오미노 (문제 ID : POLY, 난이도 : 중) 휴.. 맨 처음에는 무슨 문제인가 싶었지만, 결국 풀어내서 성취감이 있는 문제였다. 책에 있는 접근법을 조금 가져와 보자면... 위의 성질을 이용해서 점화식을 세우면 된다. 왜 이렇게 되냐면, 한 줄에 있는 블럭들은 서로 떨어져 있으면 안되고 붙어 있어야 하는 성질 때문이다! 😉 점화식은 대략 아래처럼 생겼다. 나 같은 경우, 처음에는 아래처럼 for-loop 으로..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 신비로운 동적 계획법의 세계... 세는 방법은 여러 가지일 수 있다. [종만북 문제] 비대칭 타일링 (문제 ID : ASYMTILING, 난이도 : 하) 사실 이 문제는 이전의 타일링 문제와 매우 비슷하다. 중요한 건 '대칭인 경우를 어떻게 뺼 것인가?' 인데, 잘 생각해 보면 길이가 홀수일 때와 짝수일 때를 나눠서 간단한 연산을 해 주면 된다는 것을 알 수 있다. 사실 그다지 깔끔하지는 않지만, 나는 아래 코드처럼 풀었다. #include #include "stdlib.h" #include #include #include #i..

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 시시해서 죽고 싶어졌다. [종만북 문제] 달팽이 (문제 ID : SNAIL, 난이도 : 하) 쉬운 DP 문제다. 점화식만 잘 세우면 되는데... 책에서는 아래처럼 만들더라. 나 같은 경우, 아래와 같이 풀었다. 점화식의 원리는 거의 동일하다! #include #include "stdlib.h" #include #include #include #include #include using namespace std; /******************************************************************..

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