실전 코딩 테스트-동적 계획법

본 자료와 관련 영상 컨텐츠는 저작권법 제25조 2항에 의해 보호를 받습니다. 본 컨텐츠 및 컨텐츠 일부 문구 등을 외부에 공개하거나, 요약해서 게시하지 말아주세요.

<b>by 패스트캠퍼스 및 강사 Dave Lee</b> (<a href='www.fun-coding.org'>잔재미코딩 블로그</a>)

코딩 테스트 학습 팁

알고리즘을 익힌 후, 해당 알고리즘과 관련된 문제만 연이어서 쭈욱 풀어보는 방식이 가장 좋습니다

처음 알고리즘을 익힐 때는 알고리즘을 익힐 때 풀이한 문제를 중심으로 하되,

필요하면 감을 가지기 위해 여기에 최대한 가장 쉬운 한 두 문제를 푸시고,

전체 알고리즘을 다 익힌 후, 가능하면

각 알고리즘별로 며칠동안 해당 알고리즘 관련 문제만 묶어서 연이어 풀어보세요!

실전 코딩 테스트 - 동적 계획법

1. 연습 문제: https://www.acmicpc.net/problem/11726

풀이 전략

• 점화식 찾기
  • 점화식이란, 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식을 의미
  • 예: dp[n] = dp[n - 1] + dp[n -2]

코드 작성 패턴

1. 빈 리스트 만들기
2. 초기값을 설정해주기
3. 점화식 기반으로 계산값 적용하기
4. 특정 입력값에 따른 계산값을 리스트에서 추출하기

1. 빈 리스트 만들기

dp = [0] * 1001

2. 초기값을 설정

dp[1] = 1
dp[2] = 2

3. 점화식 기반으로 계산값 적용하기

for index in range(3, 1001):
		dp[index] = dp[index - 1] + dp[index - 2]

구현 코드

dp = [0] * 1001
dp[1] = 1
dp[2] = 2
for index in range(3, 1001):    
		dp[index] = dp[index - 1] + dp[index - 2]
print (dp[2] % 10007)
print (dp[9] % 10007)

2
55

참고: 제출용 코드

본 강의는 해당 사이트를 기반으로 하는 강의는 아니므로, 예제 입력에 따른 예제 출력이 정상적으로 되는지, 구현에 집중합니다

n = int(input())
dp = [0] * 1001
dp[1] = 1
dp[2] = 2
for index in range(3, 1001):    
		dp[index] = dp[index - 1] + dp[index - 2]
print (dp[n] % 10007)

일반적인 동적 계획법 문제는

통상 코드 자체는 간결하므로,

가장 적은 경우의 수부터 계산을 해본 후, 패턴을 찾아, 식(점화식)을 세우는 것이 핵심!

2. 연습문제: https://www.acmicpc.net/problem/9461

• 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, …
• 규칙 찾아보기: dp[ i + 3 ] = dp [ i ] + dp [ i + 1 ]

dp = [0] * 101
dp[1] = 1
dp[2] = 1
dp[3] = 1
for index in range(0, 98):    
		dp[index + 3] = dp[index] + dp[index + 1]
print (dp[6])print (dp[12])

3
16

추가 참고 문제: 3. https://www.acmicpc.net/problem/1904

• N = 1(1) : 1
• N = 2(2) : 00 11
• N = 3(3) : 100 001 111
• N = 4(4) : 0000 1100 1001 0011 1111
• N = n : (n - 2)00 (n - 1)1

즉 dp[n] = dp[n - 2] + dp[n - 1]

n = 4
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2
for index in range(3, n + 1):    
		dp[index] = ( dp[index - 1] + dp[index - 2] ) % 15746
print(dp[n])

5

본 자료와 관련 영상 컨텐츠는 저작권법 제25조 2항에 의해 보호를 받습니다. 본 컨텐츠 및 컨텐츠 일부 문구 등을 외부에 공개하거나, 요약해서 게시하지 말아주세요.

<a href='www.fun-coding.org'>잔재미코딩(www.fun-coding.org) Dave Lee</a>