IT's me

다이나믹 프로그래밍(동적 계획법) 문제 - 2xn 타일링(백준)

동적 계획법의 가장 기본적인 문제가 아닌가 한다.

2xn 크기의 타일이 주어진다면 2x1, 1x2크기로 타일을 채울 수 있는 경우의 수를 모두 구하는 문제이다.

1. 2x1 크기 타일로 채우는 방법

2. 2x2(1x2 타일 두개)로 채우는 방법

위의 두가지 방법으로 분류하여 생각하면 쉽게 점화식을 찾을 수 있다.

동적 계획법의 기본 원리를 짚고 넘어가자면 차근차근 답을 찾아나가면서

그 답을 dp배열에 저장하고, 저장된 데이터를 통해 다음 답을 찾아나간다는 것이다.

n크기의 타일을 채울 수 있는 경우의 수는 

1. dp[n-1]의 경우의 수에 2x1 크기 타일을 하나씩 붙여주는 경우

2.  dp[n-2]의 경우의 수에 2x2 크기 타일을 하나씩 붙여주는 경우

dp[x]의 값에는 n이 x일 경우의 모든 경우의 수가 들어가 있다. 

따라서 dp[10]의 값을 찾는다 하면 

dp[9]에 2x1타일을 하나 붙여주는 경우 + dp[8]에 2x2타일을 하나 붙여주는 경우이다.

해당 인덱스의 dp에는 모든 경우의 수가 들어있다는 보장이 있기 떄문에

dp[n] = dp[n-1] + dp[n-2] 라는 점화식이 성립하게 된다.

다이나믹 프로그래밍 - 2xn 타일링(백준)

소스 코드

코드는 굉장히 짧지만 점화식을 생각해내는 시간이 꽤 오래 걸렸다.

Aerosmith - I don't want to miss a thing

퀸 다음으로 좋아하는 락 그룹 에어로스미스

그들 노래 중에서도 가장 좋아하는 노래 I don't want to miss a thing.

아마겟돈의 OST로도 유명한데, 영화의 이펙트도 상당히 강했고

이 노래와 함께 나온 엔딩장면이 아직도 잊혀지지가 않는다.

벌써 노장이 되어버린 에어로스미스..

폭발적인 에너지가 넘치던 전성기때와는 달리 요즘은 힘에 부치는 느낌..ㅠ

하지만 요즘 라이브 중에 전성기 때의 가창력을 보여주는 영상을 찾게 되었다.

어쿠스틱 버전이라 보컬 스티븐 타일러의 매력적인 목소리를 더욱 잘 감상할 수 있다.

BFS 알고리즘 문제 - 나이트의 이동 (백준)

전형적인 BFS문제이다. 체스판 위의 나이트를 이동시켜

목적지까지 도착하는 문제. 최단 거리를 찾아야 하기 때문에

DFS 알고리즘 보다는 BFS 알고리즘이 효율적일 것이다.

체스판의 범위에 있는지를 체크할 때 부등호 하나를 빼먹어서 틀린 이유를 찾느라 상당히 애를 먹었다.

항상 느끼는 거지만 문제를 꼼꼼히 잘 읽어야 겠다 ㅠ

나이트의 이동 (BFS 알고리즘 문졔)

시간이 12MS가 뜨는 사람은 도대체 어떻게 풀길래 그 시간이 나올 수 있는거지..

01. 변수 선언

02. BFS

03. 메인

BFS와 DFS는 어느정도 자신감이 붙었고, 이제 DP를 중심적으로 해야할 것 같다.

그리디 알고리즘도 간간히 풀어봐야겠다는 생각이 든다.