코딩스타트

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

2. 다이나믹프로그래밍을 이용한 풀이

다이나믹 프로그래밍으로 풀기 전에 이 문제의 점화식을 먼저 구해보면 간단히 n=2,n=3,n=4 만 비교해보면 n=2는 2가지 n=3일떄는 3가지 n=4 일때는 5가지라는 경우의 수가 나온다. 즉, 이 문제의 점화식은 2x4=2x3 + 2x2 라는 점화식이 나온다. ->memo[n]=( tiling(n-1)+tiling(n-2) )%10007 하지만 문제의 전제에서 값에 10007의 나머지 값을 구하므로 % 10007을 해준다.(마지막에 결과에만 하는 것이 아니라 모든 경우에 % 10007이 적용되어야 한다.) 여기서 n-2 라는 수가 있다는 것을 주목하면 2번째 전까지의 수의 배열을 확인한다. 즉, 0과 1 두가지의 수를 초기화 시켜놔야 한다. 그래야 tiling(2)를 호출할때 tiling(1)+tiling(0) 을 호출했을때 배열의 있는 값을 이용해 이후의 값을 구할 수 있다.

1. 다이나믹프로그래밍(dynamic programming) 초콜릿 자르기(백준 2163번)

2. 다이나믹프로그래밍을 이용한 문제풀이

이 문제의 예를 들면 초콜릿이 (1,N) 모양이라면 이 초콜릿을 자를 수 있는 최소한의 수는 N-1 이라는 경우의 수가 나온다. 즉, 1,N(1<=N<=300) 의 초콜릿의 자를 수 있는 최소한의 수를 초기값으로 memo 배열에 넣어준다. (다이나믹 프로그래밍은 큰 문제를 잘게 쪼개가다가 맨 마지막 가장 작은 문제의 값을 이용하여 인접한 배열에 수를 채워가 마지막 결과값을 구하는 것이다.) 만약 초콜릿이 (3,4) 라면 cutting(3,4) 라는 함수에 들어간다.(이전에 memo배열을 초기화해주는 함수를 실행시켜준다.) 그러면 이 함수는 memo[3][3]=cutting(2,3)+memo[1][3]+1 가 된다. 이 뜻은 (3,3) 초콜렛을 (2,3)과 (1,3) 으로 쪼개주는 것이다. 여기에서 (2,3) 과 (1,3) 을 쪼개는 경우의 수 1을 더해주는 것이다. 그다음 (2,3) 은 앞의 N값이 2 이므로 한번더 쪼개기 위해 재귀호출을 한다. 하지만 (1,3) 은 이미 위의 memo배열에 초기화를 시켜줬으므로 재귀호출이 아니라 바로 값을 리턴해주는 것이다.(초기화 값을 이용해 재귀호출을 하는 것이 아니라 바로 결과값을 구할수 있다. 그러므로 불필요한 계산을 중복으로 하지 않는다.) 이런식으로 N값이 1이 될때까지 재귀호출을 반복하면 결과적으로 memo(3,3)에 결과값이 들어가게 되고 그 값을 리턴하게 된다.

1. 백트래킹을 이용한 N-QUEEN 문제 (백준 9663번)

2.백트랙킹을 이용한 풀이

4X4 체스판에서의 예를 들어보면 처음에 nQueen(iArr,4,0) 이라는 함수를 호출한다. 이 함수의 뜻은 1번째 행에 퀸을 놓는다 라는 뜻이다. 함수 속에 들어가게 되면 1번째 행에는 퀸을 1,2,3,4 열에 퀸을 놓을 수 있다. 이것을 각각의 경우로 따지기 위해 for문의 인덱스를 0<=i<N 이라는 값으로 셋팅 해준것이다. 그리고 iArr[0]=0 이 들어가게 된다. 이 뜻은 1번째 행의 1번째 열에 퀸을 놓겠다 라는 뜻이다. 그런다음 조건문안에 promising(iArr,4,0) 이라는 함수를 호출하게 된다. 이 함수 안에 들어가게 되면 지금 행의 이전까지의 퀸을 놓은 경우에 따라 지금 놓은 퀸의 위치가 유효한가를 따져보는 함수이다. 하지만 row가 0이므로 이전의 놓은 값은 아무것도 없기에(i<0) for문 자체를 돌지 않으므로 return 값은 true가 되어 퀸을 놓을 수 있게 된다. 여기서 promising 함수안의 조건문을 보면 iArr[row]==iArr[i] || row-i==Math.abs(iArr[row]-iArr[i]) 이라는 조건이 있다.

이 조건은 퀸의 성질을 나타낸 것인데 퀸은 자신이 놓인 곳에서 행,열, 대각선 아무 곳이나 이동하여 공격 할수 있다라는 성질을 이용해 만약 이전에 놓였던

퀸들의 위치에서 행,열,대각선 위치와 지금 놓은 퀸의 위치가 같다면 false를 리턴하라는 조건문이다. 이렇게 row를 하나씩 증가시켜가며 퀸을 놓는 것이다.

만약 promising이 false라면 다음 퀸을 놓지 않고 for문으로 다시 돌아가 i를 1 증가시켜 다음 위치에 퀸을 놓았을때를 비교 한다.(백트랙킹) 만약 해당 열에

어느곳에도 놓을수 없다면 이전 퀸으로 돌아가 이전 퀸의 위치를 i+1로 변경해서 다시 퀸을 놓는 경우의 수를 따져보는 것이다.(백트랙킹)

입력:

8

출력:

92

1.백트랙킹- 로또문제(백준6603번)

2. 백트랙킹을 이용한 풀이

예를 들어 입력 값으로 1 2 3 4 5 6 7 이 들어왔다고 가정해보자. 그러면 반복문 안에서 count=1 되면서 dfsForRecursive(0,1+" "); 함수 안에 들어가게 된다. 그런 다음에 count가 6이 아니므로 for문으로 들어가게 된다. 이제 dfsForRecursive함수 안에는 iArr[0](v=0) 보다는 큰수의 인덱스로 함수에 들어가게 된다. 이런 식으로 쭉쭉 가다보면 처음으로 StringBuffer에 들어가는 수는 1 2 3 4 5 6 이라는 값이 된다. 그러면 else 밑에 count가 -1되고 함수가 리턴이 된다. 이 함수는 for문 안에서 호출한 dfsForRecursive(5,1 2 3 4 5 +iArr[5]+" ") 이다. 이 함수가 리턴이 된다면 for문의 다음 인덱스 i=6 값으로 함수의 매개변수로 들어간다. dfsForRecursive(6,1 2 3 4 5 +iArr[6]+" ") 이값도 count가 6이 됬음으로 StringBuffer에 append 시켜주고 함수가 끝나게 된다. 그렇다면 더 이상 돌 for의 인덱스가 없으므로 이전의 함수 dfsForRecursive(4,1 2 3 4 +iArr[4]+" ") 함수가 끝나게 되고 다음 dfsForRecursive(5, 1 2 3 4 +iArr[5]+" ")를 호출하게 되는 것이다. 이런 식으로 main 함수 안의 for문이 끝날때까지 반복되게 된다. 그런데 여기서 주의 해야할 점은 dfsForRecursive 함수 안의 for문의 시작인덱스가 v+1이라는 것이다. 왜 자신보다 큰 값을 들어오게 하는 것일까? 이것의 예를 들자면 예를 들어서 값이

1 2 3 4 5 6 , 1 2 3 4 5 7 이라는 결과로 함수가 끝났다고 생각하자 그 다음은 1 2 3 4 6 ? 로 시작을 하게 될 것이다. 여기서 v+1이라는 값이 발휘 한다. 만약 1 2 3 4 6 5 라는 값이 들어오게 되면? 이 문제는 중복을 허락하지 않음으로 바로 위의 1 2 3 4 5 6 이라는 값과 중복이 되버린다. 그래서 v+1을 함으로써 이전에 나왔던 결과값과 중복이 되지 않게 하는 것이다.

입력:

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

출력:

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

재귀를 이용한 하노이탑(백준1914번문제)

재귀를 이용한 하노이탑 문제풀이

여기서 문제는 N값이 20 이하 일때만 원반을 옮기는 과정을 출력하지만 20보다 클 경우에는 원반의 옮긴 수만 출력하면 된다. 여기서 옮긴 횟수를 함수 안에서 재귀호출 할때마다 카운트를 1씩 증가시키는 것으로 코드를 짜게되면 아마 시간 초과가 발생할 것이다.  왜냐면 조건에서의 가장 큰수 100을 입력하면 1267650600228229401496703205375라는 원반을 옮긴 횟수가 나오는데 보통 1억번에 1초정도 걸리는데 이것은 어마어마한 시간이 걸릴 것이므로 횟수는 카운트를 1씩 증가시키는 것이 아니라 점화식을 이용하여 횟수를 구한다.

즉, 원반을 옮기는 횟수는 2^N-1번이다.  N값이 100이라 가정했을 때는, 이 값은 long 데이터 타입도 수용하지 못할 값이므로 자바의 BigInteger 클래스를 이용해 횟수를 저장한다. 내부적으로 String을 가지므로 무한히 큰 값도 수용이 가능하다.

원반을 옮기는 과정의 함수를 설명하자면 예를들어 3개의 원반을 1번탑에서 3번탑으로 옮긴다면 hanoi(3,'1','2','3') 함수를 호출하게 된다. 그러면 함수 내부에서 재귀호출을 통해서 문제를 쪼개는 과정에 들어간다. 3개의 원반을 1번탑에서 3번탑으로 옮기는 것이라면 우선 더 작은 문제로 1번,2번 원반을 2번탑으로 옮긴후에 그다음 3번원반을 3번탑에 옮기고 그리고 1번,2번의 원반을 다시 2번탑에서 3번탑으로 옮기는 것 이렇게 문제를 작은 단위로 쪼개는 것이다. 이것이 총 3번의 과정으로 1번 n-1개의 원반을 보조탑(2번탑으로 옮기는과정)으로 옮기는 과정은 hanoi(2,from,to,aux) 함수에서 해결하고 그다음 3번원반을 1번탑에서 3번탑으로 옮기는 과정은 system.out.println(from+" "+to); 라는 출력문으로 그리고 마지막으로 보조탑에 있던 1번,2번 원반을 3번탑으로 옮기는 과정은 hanoi(2,aux,from,to) 함수에서 해결하게 된다. 그리고 각 함수 내에서 문제를 더 작은 단위로 쪼개고 쪼갠다. 예를 들어 1,2번 원반을 보조탑으로 옮기는 hanoi(2,from,to,aux) 함수에서 다시 문제를 1번원반을 보조탑인 3번탑으로 옮기는 과정(hanoi(1,1,2,3)과 2번원반을 2번탑으로 옮기는 과정(system.out.println(from+" "+to) 그리고 마지막으로 보조탑에 있던 1번원반을 목적탑인 2번탑으로 옮기는과정(hanoi(1,3,1,2))으로 마무리 되는 것이다. 

즉,

 hanoi(N-1,from,to,aux);

System.out.println(from+" "+to);

hanoi(N-1,aux,from,to);

이 과정이 n의 수가 1이 될때까지 계속 각 n값에 대하여 반복하게 되는 것이다.

재귀함수-백준1074번 Z문제

풀이-재귀호출을 이용한 알고리즘풀이

이 문제를 보면 딱 떠오르는 것이있다. Z방향으로 배열을 순회하는 것이다. 그 말은 즉슨 배열을 1사분면->2사분면->3사분면->4사분면 순서로 방문을 하는 것이다. 여기서 이용되는 재귀호출의 기능은 예를들어 8x8의 배열이라면 재귀호출을 통해 4x4배열로 줄여주는 역할을 한다.(이말을 재귀호출을 통해서 큰 문제를 작은 문제로 쪼개나가는 과정이라고 생각하면 된다.) 1/4씩 배열의 크기를 줄여가며 방문한 횟수를 카운트해주는 것이다. 예를 들어 8x8의 배열의 2사분면이라면? 8x8배열에서 이미 1사분면을 지나왔으므로 (64/4)*(해당분면-1=1)의 배열만큼 방문해서 2사분면을 온것이므로 방문횟수에 (64/4)*1만큼의 수를 증가시켜주고 8x8의 2사분면인 4x4배열로 재귀를 통해 문제의 크기를 줄여준다. 그 다음의 위치가 4x4의 배열에서 몇 사분면이냐라는 것을 다시 따져서 위처럼 횟수를 증가시켜준다. 그리고 배열을 줄여가다 마지막으로 2x2의 배열이 되었을때 1사분면일때는 횟수를 0, 2사분면은 횟수를 1, .....4사분면은 횟수를 3을 증가시켜주면된다.

이 문제같은 경우는 최소신장트리를 구하는 알고리즘이다. 최소신장트리를 구하는 알고리즘은 크게 프림알고리즘과 크루스칼알고리즘 두가지가 있다. 여기서 조금더 구현하기가 수월한 프림알고리즘을 이용하여 최소신장트리를 구현할것이다.

1. 최소신장 트리란?

최소 신장트리란 주어진 그래프에서 모든 정점을 연결하며 그 비용이 최소인 간선만 연결된 트리를 말한다.

2.프림 알고리즘(그림으로 설명하는 것이 편할 것같아 그림으로 ㅅ

다익스트라 알고리즘과 비슷한 로직을 가집니다. 다만 큐에서 최소값을 빼주며 방문한 정점들을 체크를 해주어서 이미 체크된 정점 같은 경우는 결과값에 포함시키지않는다. 

이전에 게시했던 최단 거리문제가 코드가 동일하다. 단지 출력하는 부분의 코드만 살짝 수정해주면된다. 즉, 최소비용문제 또한 다익스트라 알고리즘으로 풀수 있다.

백준-1916번 최소비용 구하기

출발도시에서 도착도시까지의 최소비용을 구하는 것이므로 출력부분을 도착도시의 거리를 출력해주면된다. 왜냐하면 다익스트라 알고리즘은 시작정점으로부터 모든 정점까지의 최소비용들이 모두 distance배열에 들어가기때문에 단순히 앞의 최단경로 문제 코드에서 출력부분만 수정해주면 된다. 다익스트라 알고리즘 구동방식은 최단거리문제 설명에 그림으로 설명되어있다.