코딩스타트

재귀란?

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;

}

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

재귀를 이용한 하노이탑(백준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을 증가시켜주면된다.

서비스 추상화란?

서비스 추상화란 Spring framework는 물론 객체지향 프로그래밍에서 아주 중요한 개념이다. 간단히 이야기하면 개발환경, 혹은 어떠한 비즈니스 로직을 위한 로우레벨의 기술에 구애 받지 않게 하기위해서, 그리고 책임을 분리 시키기 위한 추상화 개념이다. 예를 들어서 PlatformTransactionManager 같은 경우가 서비스 추상화의 대표적인 예이다. 트랜잭션을 관리한다는 것은 크게 보면 디비의 트랜잭션을 관리한다는 말이다. 그렇다면? 과연 디비라는 것은 종류가 하나인 것인가? 아니다. JDBC,하이버네이트 등등 아주 많은 디비의 종류가 있다. 그렇다면 각자의 디비의 트랜잭션을 관리하기 위해 각각다른 트랜잭션 코드가 필요하다면? 만약 디비가 바뀌게 된다면 그에 따라 트랜잭션 관리 코드 또한 바뀌어야 할것이다. 여기서 중요한 개념이 서비스 추상화 개념이다. 트랜잭션을 관리하기 위한 최상위 인터페이스인 PlatformTransactionManager를 선언하고 각 디비에 대한 transactionManager 클래스를 DI해주면? 트랜잭션 관련 코드는 통일되는 동시에 디비가 바뀐다면 DI설정 XML파일만 교체해주면 된다. 디비가 바뀌게 되더라도 트랜잭션 관련코드의 변경은 하나도 없는것이다. 이것이 서비스 추상화의 장점인 것이다.

Spring Transaction(트랜잭션) 범위 설정하기

1.예외 상황(트랜잭션 범위설정이전)

예를 들어 이런 코드가 있다고 가정해보자. 여기서 보면 user3이라는 객체의 인스턴스변수를 설정해줄때, user3.setId() 메소드 부분에 user1과 같은 id가 들어가서 duplicationkey라는 예외가 발생하여 user3은 DB에 정상적으로 데이터가 삽입되지 않을 것이다. 여기서 transaction manager를 사용한다고 가정했을 때,

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

1. 최소신장 트리란?

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

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

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

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

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

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

백준-1753번 최단거리

시작정점으로부터 모든 정점까지의 최단거리를 구하는 문제이다. 이 문제는 BFS와 비슷한 다익스트라 알고리즘으로 풀 수 있는 문제이다. 다익스트라 알고리즘은 방향이있는 가중치 그래프에서 어떤 정점에서 다른 정점까지의 최단 거리를 구할 수 있는 알고리즘이다.(음수간선을 포함하는 그래프는 다익스트라 알고리즘으로 풀 수 없다.)

위의 그림과 같은 과정으로 다익스트라 알고리즘이 구동됩니다. ( 코드에서는 방문여부에 관한 check배열은 선언하지 않았음 굳이 없어도 돌아감)

BFS와 비슷하게 큐를 이용하지만 그냥 큐가 아니라 우선순위 큐를 이용하여 구현한다.