코딩스타트

1.다이나믹 프로그래밍 - 다리 놓기 (백준 1010번)

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

1)조합을 이용한 문제풀이

첫번째 풀이는 조합을 이용한 풀이입니다. 예제 입력에서 29개의 다리 중에서 13개의 다리를 겹치지 않고 놓을 경우의 수는 67863913개입니다. 겹치지 않는다? 단순히 그냥 29개의 다리중에 13개의 다리를 뽑는 경우의 수를 구하면 됩니다. 굳이 겹치는 경우를 고려하지 않아도 되는 것입니다. 13C29(13콤비네이션29) 의 값을 구해주는 로직만 짜주면 답은 쉽게 나오게 됩니다.

2)DP를 이용한 풀이

예를 들어 서쪽에는 3개의 사이트 동쪽에는 5개의 사이트가 있다고 가정한다면 bridge(3,5) 메소드를 호출하게 된다. 여기서 반복문이 뜻하는 바는 i==4부터 i==2까지 값을 감소시키며 bridge 함수를 호출시키는 것이다. 이것은? i==4라면 서쪽의 첫번째 사이트가 동쪽의 1번 사이트와 다리가 연결되어 남은 2개의 서쪽사이트와 4개의 동쪽사이트로 연결할 수 있는 다리의 경우를 구하면 되는 것이고, i==3이면 서쪽의 1번 사이트가 동쪽의 2번사이트와 연결되어 남은 2개의 서쪽사이트와 동쪽의 2번 밑의 3,4,5 3개의 사이트와 연결될 경우의 수를 구한다. 이렇게 쭉쭉가다가 서쪽과 동쪽의 남은 사이트 수가 같을 때까지 반복한다. 이런 것이 서쪽 사이트가 하나씩 줄어 가며 반복되는 것이다. 그리고 마지막 서쪽사이트가 함수에 들어 오게 된다면 초기화된 값을 바탕으로 memo[n][m]의 값을 구하게 되는 것이다. 

1.다이나믹 프로그래밍 - 계단 오르기 (백준 2579번)

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

이 문제 풀이의 핵심은 각 계단을 마지막 계단으로 보는 것입니다. 예를 들어 가장 마지막 계단을 오르는 경우의 수는 이전 계단을 밟는 경우와 전전계단을 밟는 경우 총 2가지입니다. 여기에서 이전 계단을 밟는 경우에서 upStair(n-3) 재귀호출까지 더해주는 이유는 3번 연속된 계단을 밟을 수 없기 때문입니다. 이 두가지 경우 중에서 큰수를 Math 클래스의 max 메소드를 이용해서 구합니다. 그래서 이 두가지의 경우로 재귀호출을 통해 다시 함수에 들어가게 되면 그 계단을 다시 마지막 계단으로 보고 다시 위의 두 가지 경우로 나뉘어서 재귀 호출을 반복하게 됩니다. 이 과정을 반복하다가 초기화된 값까지 다다르게 되면 모든 값이 메모된 값을 이용하여 총합을 구할 수 있게 됩니다. 여기에서 2번째 계단을 밟은 가장 큰 경우의 수는 1번째 계단을 밟는 경우이므로 stairArr[1]+stairArr[2] 를 통해 초기화를 해줍니다.

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

스프링에서 어노테이션을 이용한 DI 방법

1.@Autowired,@Resource,@Qualfier 어노테이션

위에서 보듯 어노테이션을 이용한 DI방법은 여러가지가 있지만 대표적으로 2가지를 설명하자면 @Autowired , @Resource 를 이용한 DI 주입 방법을 들수있다. @Autowired는 해당 변수의 인터페이스 타입으로 등록된 빈들에서 찾아서 DI를 주입해주는 방법이다. 만약 UserService 라는 인터페이스를 구현한 클래스가 2개 이상 빈으로 등록되어있다면 이름의 충돌이 발생해 제대로 DI가 되지 않는 경우가 있다.(에러가 뜬다. 하지만 에러를 발생하지 않게 하려면 @Autowired(require=false) 로주면 에러는 발생하지 않는다.) 변수의 타입으로 판별 할수 없다면 변수명을 이용하여 DI를 한다고 하지만 그 마저 마땅치 않으면 예외가 발생 할 수가 있다. 그래서 사용하는 어노테이션이 @Resource 어노테이션이다. @Resource(name="~") name이라는 속성안에 등록된 빈의 이름을 지정한다면 같은 타입의 인터페이스를 구현한 클래스들이 여러개 등록되어 있더라도 정확히 이름으로 골라서 등록이 가능하다. 하지만 만약 클래스를 @Service,@Component 등의 어노테이션으로 빈등록을 했다면? 방법이 있다. 예를 들어 UserServiceImpl 라는 UserService 인터페이스 구현클래스를 어노테이션으로 빈등록을 했다면 그 빈은 자동으로 userServiceImpl 라는 이름으로 빈등록이 된다. (앞글자를 소문자로) 그래서 내부적으로 지정된 userServiceImpl 라는 이름을 @Resource의 name 속성에 넣어주면 된다. @Autowired로 빈을 결정 지을 수 없을때, 밑에 @Qualifier("~")를 붙여서 특정빈을 선택한다.

2. DI 이전에 필요한 스프링설정

위의 어노테이션들을 사용하여 DI를 주입하기 위해서는 각각 어노테이션을 인식하기 위한 스프링 설정이 필요하다.

재귀란?

static void dfsForRecursive(int v,String str) {

if(count==6) {

sb.append(str+"\n");

}else {

for(int i=v+1;i<K;i++) {

++count;

dfsForRecursive(i, str+iArr[i]+" ");

}

}

--count;

}

재귀란 위의 코드를 보듯이 자신의 메소드 안에서 자기자신을 호출하는 것을 말한다. 여기서 중요한 개념은 자신의 메소드에서 자기자신을 호출하게 되면 메모리 스택영역에 자기자신을 호출한 메소드가 복사되어서 들어가는 것이다.(맨 처음의 원본이 그대로 들어가는 것이 아니다.) 그 말은 즉, 자기자신을 호출할때 바뀌게 되는 매개변수의 값은 다시 같은 변수의 이름으로 들어가더라도 원본의 매개변수의 값에 영향을 주지 않는다.(메소드의 매개변수는 전역변수가 아니라 지역변수이기 때문이다.) 즉, 스택에 그대로 복사를 하게 되는 것이므로 원본에 영향을 미치지 않는 것이다. 본인도 이 개념이 확실히 잡히지 않아서 재귀, 백트랙킹 문제를 풀때 쉽지 않았기에 이 개념을 머리 속에 잘 담아두면 재귀호출을 이용하는 문제의 로직을 짤때 훨씬더 수월 할 것이다.