DFS 4방향 8방향 배열 탐색

DFS를 구현할 때 배열을 4방향 또는 8방향 탐색을 해야하는 경우가 많이 있다.

이때 보통 다음과 같이 if문을 이용해서 구현을 하는데

if(MAP[y+1][x] == 1) {
    ...
}
if(MAP[y][x+1] == 1) {
    ...
}
.
.
.


이렇게 하면 코드량도 많고 가독성도 떨어지기 때문에

실제 알고리즘 시험시에 상당히 불편하다.

많이 알려져 있는 방법이지만

4방향 또는 8방향을 배열값으로 저장해서 루프를 돌리면 코드가 매우 간단해 진다.

예제 코드는 다음과 같다.

알고리즘 다이나믹프로그래밍 동전 문제 2

흔히 DP라고 하는 다이나믹프로그래밍 문제중에

가장 기본적인 문제가 동전 문제이다.

만들어야 할 금액과 동전의 종류가 주어졌을 때  

동전들을 최소의 개수로 조합해서 금액을 만들면 되는 문제이다.

예를들어 만들어야 하는 금액이 15원이고

주어진 동전의 종류가 1원, 5원, 12원이면(동전은 여러번 사용해도 된다.)

15원을 만들 수 있는 동전의 최소의 개수는 3이다. (5원+5원+5원)

이 문제를 푸는 핵심은 다음과 같다.

1. 다이나믹 테이블 D[]를 필요한 동전의 개수를 저장하는 배열로 선언

    예) D[15] = 15원을 만드는 데 필요한 동전의 개수

2. 다이나믹 테이블 D[]는

    만들어야 할 금액에서 추가할 동전의 금액을 뺐을 때

    예를 들어 15원-5원은 10원이므로

    10원을 만드는 데 필요한 동전의 개수에 한개를 더한 값

    15원을 만드는 데 필요한 동전의 개수를 비교하여 

    최소값을 택하는 방식으로 다이나믹 테이블을 만들어간다.

   다이나믹 테이블이 만들어지는 방식을 간단히 정리해 보면 다음과 같다.

   D[5], D[5-1]+1

   D[5], D[5-5]+1 ==> D[5]는 초기에 MAX값으로 설정되어 있으므로 D[5-5]+1=D[0]+1=0+1=1이 최소값

   D[10], D[10-1]+1

   D[10], D[10-5]+1 ==> D[10-5]+1=D[5]+1=1+1=2

   D[10], D[10-12]+1

위의 내용을 코드로 작성해 보면 다음과 같다.

알고리즘 다이나믹프로그래밍 동전 문제 1

다이나믹프로그래밍을 공부하기 좋은 기본적인 문제가 동전 문제이다.

지난번 포스팅에는 목표 금액을 만들기 위한 최소의 동전의 개수를 구하는 방법에 대해 정리해보았다.

이번 포스팅에서는 목표 금액을 만들 수 있는 모든 경우의 수를 구하는 방법에 대해서 정리해보려고 한다.

다이나믹프로그래밍은 다이나믹테이블을 만들면 쉽게 점화식을 유도해낼 수가 있다.
이번 문제의 다이나믹테이블은 다음과 같다.

	0	1	2	3	4	5	6	7	8	9	10	<- 목표 금액
1	1	1	1	1	1	1	1	1	1	1	1	<- 1원으로 목표 금액을 만들 수 있는 경우의 수
1,2	1	1	2	2	3	3	4	4	5	5	6	<- 1원, 2원으로 목표 금액을 만들 수 있는 경우의 수
1,2,5	1	1	2	2	3	4	5	6	7	8	10	<- 1원, 2원, 5원으로 목표 금액을 만들 수 있는 경우의 수

[알고리즘] 탐색

알고리즘 공부를 하다 보면 기본적으로 알아야 하는 것이 바로 탐색이다.

탐색에는 2가지가 있다.

- 선형 탐색
- 비선형 탐색

선형 탐색은 다음 탐색 대상이 하나인 것이다.

비선형 탐색은 다음 탐색 대상이 여러개인 것이다.

선형 탐색은 주로 배열이나 연결 리스트를 이용하여

순차 탐색 또는 이분 탐색으로 해결이 된다.

비선형 탐색은

배열을 이용한 인접 행렬이나 연결리스트를 이용한 인접리스트로 해결이 된다.

[알고리즘] LIS(Longest Increasing Subsequence) 최장증가수열 #1

요즘 LIS 알고리즘을 공부하고 있다.

나이들어 알고리즘을 공부하려니 머리가 따라가질 않는다...ㅜㅜ

대학원생 시절 하필 알고리즘 과목이 영어 강의였던게 한으로 남는다.

LIS는 Longest increasing subsequence의 약자이다.

우리말로는 최장증가수열이라고 한다.

이렇게 말로는 이해가 안되고

예를 들어 다음과 같은 수열이 있을때

{3,1,2,4}

최장증가수열은 

{1,2,4} 가 된다.

이렇게 주어진 수열에서 점진적으로 숫자가 커지는 수열을 최장증가수열이라고 한다.

이걸 사람이 눈으로 구하는 것은 매우 쉽다.

아마 그냥 딱 보면 나올 것이다.

하지만 수열이 길어진다면 쉽지 않을 것이다.

그래서 우린 프로그래밍을 해야한다.

주어진 수열에서 최장증가수열을 구하는 알고리즘은

n^2과 nlogn 방식이 있다.