오늘부터는 단순히 알고리즘 문제만 푸는게 아니라 알고리즘 강의 듣고 정리한 부분들에 대해서도 글을 쓸까 한다.
그래도 글을 쓰고 정리해두어야 뭔가 기억에 남는 것 같기도 하고...뭣보다 점점 가면서 이거 공부안하면 문제를 못 풀겠어서 결국 알고리즘 강의를 듣게 되었다ㅠ.ㅠ
1. What is stack?
스택(stack)에 대해서는 젠가를 예로 들면 딱 적절할 것 같다. 스택은 젠가가 아직 젠가 통에 담아져있는 것을 생각하면 된다. 이러한 상황에서 우리는 나무조각을 하나하나 빼내야 한다. 당연하게도 젠가는 통에 담아져있기 때문에 맨 아래 나무조각을 빼려면 맨 위 나무조각부터 하나하나 꺼내서 쌓아야한다. 스택은 이렇게 맨 아래 도착하기 위해 맨 위에 있는 것부터 튀어나오는 구조이다. 이를 전문 용어로 First in, Last out '가장 먼저 들어가서 가장 나중에 나오는 구조' 혹은 Last in, First out '가장 나중에 들어가서 가장 먼저 나오는 구조' 혹은 선입후출 구조 라고 한다. 사실 세가지 다 동일한 의미이다. 결국 중요한 것은 가장 처음 들어간게 가장 나중에 나오는 것 이라는 점이다.
public class Main{
public static void main(String[] args){
System.out.println("Hello World");
}
}위처럼 Hello World 라는 문장을 출력하는 코드가 있다. 이 코드를 스택을 구조로 생각해보면 Main() 매서드를 호출 -> Main 매서드 안 println() 매서드 호출 & 실행, println 이 호출 & 실행되는 동안 Main 매서드는 대기 상대가 된다 -> println 매서드가 끝난 후 다시 Main() 매서드가 실행 -> 이때 남은 문장이 없음으로 Main() 매서드가 종료되는 순서이다.
이를 그림으로 표현하자면 다음과 같다.
이 그림은 앞으로 엄~~청 많이 보게 될테니, 어떤식으로 굴러가는지는 확실히 기억해두는게 좋다.
2. What is 재귀함수?
재귀 함수란 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미한다. 다른 말로는 재귀 호출, 되부름이라고 부르기도 한다. 재귀 함수를 사용하는 가장 대표적인 문제가 바로 피보나치 수열과 관련된 수학 문제들이다.
피보나치에 대해서는 조금 이따 설명하기로 하고, 먼저 재귀 함수를 코드로 어떻게 구현하는가에 대해서 적어보겠다.
재귀 함수를 사용하는 코드는 사실 어렵지 않다. 다만 재귀 함수를 사용 시 스택을 활용할때 오히려 이해하기 어렵다고 생각한다. 구체적인 코드는 아래와 같다.
public class Algo_1 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Algo_1 T = new Algo_1();
T.DFS(3);
T.DFS_2(11);
}
public void DFS(int n) { // 재귀함수 : 자기 자신을 부르는 함수
if(n == 0) {
return; // void 에서는 함수 종료의 의미도 포함
}else {
// System.out.print(n+" "); // 3 2 1 출력
DFS(n-1);
System.out.print(n+" "); // 1 2 3 출력
// 출력문을 밑에다가 두면 1 2 3 이 출력되는 이유
// 재귀 함수는 스텍 프레임을 사용함 : 스텍프레임은 매개변수 지역변수 복귀주소를 갖음
// 즉 FIFO 가장 먼저 들어가서 가장 먼저 나오는 구조를 갖음
// 스텍 그림으로 표현하자면
// DFS(1); 가장 마지막으로 들어감, 20번째 라인까지하고 다시 T.DFS로 감.
// 이때 중요한게 n-1 = 0 이면 return 이고, 따라서 DFS(1) 부터 출력함
// DFS(2); 두번째로 들어감 20번째 라인까지만하고 다시 Main함수 T.DFS 로 감
// DFS(3); 가장 먼저 들어감 20번째 라인까지만하고 다시 Main함수 T.DFS로 감
// 순서로 생각하면 : DFS(3) 20번째 라인(복귀주소) -> DFS(2) 20번째 라인(복귀주소) -> DFS(1) 20번재 라인(복귀주소) -> DFS(0) return -> DFS(1) 출력 -> DFS(2) 출력 -> DFS(3) 출력
}
}
public void DFS_2(int k) { // 재귀함수 2진수 만들기
if(k==0) return;
else {
DFS_2(k/2); // k 를 2로 나누고 다시 자기 자신에게
System.out.print(k%2+" "); // k 를 2로 나눈 나머지 값 출력
}
}
}위 코드를 쭉 읽어보았을 때 사실 어? 하는 부분이 있을지언정 문장 자체에서 어려운 부분이 나오지는 없다. 왜냐하면 구조는 정말 정말 단순하기 때문이다. 예를 들어서 DFS 매서드 부분을 보자
public void DFS(int n) { // 재귀함수 : 자기 자신을 부르는 함수
if(n == 0) {
return; // void 에서는 함수 종료의 의미도 포함
}else {
System.out.print(n+" "); // 3 2 1 출력
DFS(n-1); // n !=0 인 상황에서는 n-1 후 다시 DFS 로 , 다시 나 자신을 호출, 재귀
}
}
출력 : 3 2 1해당 매서드는 n 이라는 정수를 받아 아래 내용을 출력하는 기능을 한다. 정확히는 n 이라는 정수를 받을 때 n = 0 이면 return 하여 종료시키고, n !=0 인 상황에서는 n-1 을 하여 다시 DFS 매서드로 보낸다.
그럼 맨 처음에 int n = 3 인 경우면 어떻게 될까? 이 상황에서 출력문이 DFS(n-1) 위에 있다면 3 부터 1까지 천천히 순서대로 출력 할 것이다. 우리가 자주 사용하던 것들과 크게 다를바가 없고 이 부분까지는 스택 구조가 사실상 사용되지 않는다.
이제 아래와 같은 코드가 있으면 어떻게 출력될까? 아래 코드는 이전과 다르게 1 2 3 순서대로 출력된다.
public void DFS(int n) { // 재귀함수 : 자기 자신을 부르는 함수
if(n == 0) {
return; // void 에서는 함수 종료의 의미도 포함
}else {
DFS(n-1);
System.out.print(n+" "); // 1 2 3 출력
// 출력문을 밑에다가 두면 1 2 3 이 출력되는 이유
// 재귀 함수는 스텍 프레임을 사용함 : 스텍프레임은 매개변수 지역변수 복귀주소를 갖음
// 즉 FIFO 가장 먼저 들어가서 가장 먼저 나오는 구조를 갖음
// 스텍 그림으로 표현하자면
// DFS(1); 가장 마지막으로 들어감, 20번째 라인까지하고 다시 T.DFS로 감.
// 이때 중요한게 n-1 = 0 이면 return 이고, 따라서 DFS(1) 부터 출력함
// DFS(2); 두번째로 들어감 20번째 라인까지만하고 다시 Main함수 T.DFS 로 감
// DFS(3); 가장 먼저 들어감 20번째 라인까지만하고 다시 Main함수 T.DFS로 감
// 순서로 생각하면 : DFS(3) 20번째 라인(복귀주소) -> DFS(2) 20번째 라인(복귀주소) -> DFS(1) 20번재 라인(복귀주소) -> DFS(0) return -> DFS(1) 출력 -> DFS(2) 출력 -> DFS(3) 출력
}
}
출력 : 1 2 3위 코드와 바로 전 코드의 차이점을 찾았는가? 바로 자신을 호출하는 부분이 출력하는 부분 보다 위에 있다는 점이다. 이렇게 될때 바로 stack 이 사용된다. 위 코드가 실행 되는 순서는 다음과 같다.
※ 아주 중요!!!
- 아래 순서는 제가 공부 할 때 강의를 들으면서 나름 열심히 이해하고 또 이해해서 그나마 쉽게 풀어써놓은 순서입니다. 다만 매번 이렇게 장황하게 쓰기는 너무 힘들어서...이렇게 자세하게 쓰는것은 여기까지만!
1) main 매서드가 실행되고 DFS(3) 일 때 DFS 함수가 호출된다. => 스택 0 에 저장
2) n == 0 이 아니기 때문에 else 부분으로 오며, 다시 DFS(n-1) , 즉 DFS(3-1) 이 호출된다. 이때 여기까지의 실행되었던 메모리 주소값이 스택에 일지정지된 상태로 저장된다. => 스택 1 에 저장
3) DFS(2) 인 상태로 DFS 매서드가 호출되며, n !=0 인 상태이기 때문에 else 부분으로 넘어가고 역시나 DFS(2-1) 이 호출된다. 당연히 여기까지의 실행되었던 메모리 주소값이 스택에 저장된다. => 스택 2 에 저장
4) DFS(1) 인 상태도 당연히!! 위와 똑같은 의미에서 실행 되었던 메모리 주소값이 스택에 저장되고 다음 DFS(1-1) 이 호출된다. => 스택 3 에 저장
5) 여기까지오면 DFS(0) 인 상태이다. 이때 n == 0 이기 때문에 DFS 매서드는 return 을 결과로 내놓고 매서드가 종료된다.
7) DFS(0) 이 종료된 뒤 바로 끝나는게 아니라 바로 이전 스택 3 으로 돌아간다. 스택 3에는 DFS( 1) 에서의 출력문만 남아있고, n =1 임으로 1 이 출력되고 스택 3은 종료된다.
8) 스택 3 이 종료된 후 바로 이전 스택 2로 돌아간다. 스택 2에는 DFS(2) 에서의 출력문만 남아있는 상태이고 n = 2 임으로 2 가 출력되고 스택2는 종료된다. 스택 1도 똑같이 수행된다.
9) 스택 0 으로 돌아와서는 DFS 매서드가 출력까지 끝냈으니 정상적으로 종료되었을 것이고 main 매서드에는 DFS 밖에 없으니 DFS 매서드 종료 후 main 매서드도 종료된다.
이 과정이 바로 스택이 활용되는 코드에서의 실행 과정이라고 할 수 있다. 헷갈리면 나처럼 그림을 그리면서 하면...조금 더 도움이 될 것이라고 본다.
3. 팩토리얼
그럼 앞서 공부하였던 스택과 재귀함수를 활용해서 팩토리얼 계산을 해보자.
팩토리얼(階乘, 문화어: 차례곱, 영어: factorial)은 수학에서 자연수의 계승 또는 그 수보다 작거나 같은 모든 양의 정수의 곱이다. n이 하나의 자연수일 때, 1에서 n까지의 모든 자연수의 곱을 n에 상대하여 이르는 말이다. 기호는 ! 을 쓰며 팩토리얼이라고 읽는다(출처 : 위키 백과)
5! 일 때
int result = 1;
for(int i=5; i>0; i--){
result = result*i;
}
이걸 이제 스택과 재귀 함수를 이용하면 아래처럼 코드로 구현 할 수 있다.
public static void main(String[] args) {
Algo_2 algo = new Algo_2();
System.out.println(algo.DFS_1(5));
}
// 팩토리얼
public int DFS_1(int n) {
if(n == 1) {
return 1; // n = 1 인 경우 그대로 1 return
}else {
return n*DFS_1(n-1);
// 예를들어 n = 5 인 경우 5 * DFS(5-1) 이 return
// n = 4 이면 DFS(3) return
// 스텍으로 생각해보자면 1층 부터
// DFS(5) -> DFS(4) -> DFS(3) -> DFS(2) -> DFS(1)
// 출력은 반대로 DFS(1) -> DFS(2) -> DFS(3) -> DFS(4) -> DFS(5)
}
}여기서도 사실 중요한 것은 DFS_1 매서드이다. 매서드 아래 코드를 보면 알겠지만 n = 1 이면 return 으로 1 을 보내고, 아닌 경우 n * DFS_1(n-1) 을 통해 자신을 부르도록 되어있다.
이 코드가 실행되는 순서는 다음과 같다.
1) n = 5 일 때 5 * DFS_1(5-1) 이며, DFS(5-1) 즉 DFS(4) 호출
2) n = 4 일 때 5 * 4 * DFS_1(3) 호출
4) 위 과정 그대로 DFS(1) 까지 호출, 최종적으로 n =1 일 때 스택에 쌓아둔 실행 과정은 5 * 4 * 3 * 2 * DFS(1) 이 된다. 이때 DFS(1) 은 그대로 1 을 return 후 종료.
5) DFS(1) = 1 인 상태로 매서드가 한번 끝났고, 스택에 저장되어있던 것들이 하나 하나 꺼내지면서 계산된다.
6) 즉 스택이 쌓이는 순서는 DFS(5) -> DFS(4) -> DFS(3) -> DFS(2) -> DFS(1) 이며, 출력되는 순서는 이와 반대가 되어야함으로(가장 마지막에 쌓인 것이 가장 먼저 출력되기 때문) 출력은 반대로 DFS(1) -> DFS(2) -> DFS(3) -> DFS(4) -> DFS(5) 가 된다.
4. 피보나치 수
피보나치...나는 개인적으로 이 친구를 처음 알았던게 바로 정보처리기사 필기 시험이다. 왜 처음 본게 아니라 처음 알았던 게 정처리 필기 시험인가 하면...그 전까지는 피보나치 문제가 나오면 코드는 보고 짤 줄 알아도, 이게 '피보나치' 라는 이름을 갖고 있는줄은 몰랐기 때문이다.
왜 이런 이야기까지 하냐고 하면, 이 피보나치의 수 혹은 피보나치 수열이라고 불리는 이 친구는 정말 엄~청 뭔가 코드를 짤 때 보면 엄~청 많이 사용되고, 활용되기 때문이다.
그럼 피보나치 수가 무엇이냐? 피보나치 수는 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다(출처 : 위키백과)
사실 이 친구도 팩토리얼과 마찬가지로 for 문으로 충분히! 짤 수 있고, 오히려 for 문을 사용하는게 훨씬 쉽다. 다만 여러 코딩테스트에서 피보나치와 관련되는 문제들이 많이 나오기 때문에 스택을 이용해 구현하는 것도 공부해두면 좋다고 생각한다.
피보나치 수를 구현하는 코드는 아래와 같다.
public class Algo_2 {
public static void main(String[] args) {
Algo_2 algo = new Algo_2();
int n = 5;
int result =0;
System.out.println(algo.DFS_2(n)); // 단순히 하나의 항만 출력할 때
// 항을 순서대로 출력할때
for(int i=1; i<=n; i++) {
System.out.print(algo.DFS_2(i)+" ");
}
// n 번째 항까지의 값을 모두 더하는 경우
for(int i=1; i<=n; i++) {
result += algo.DFS_2(n);
}
System.out.println("result = "+result);
}
// 피보나치함수 : 첫번째와 두번째 수는 1
// 여기서 n 은 n 번째 항이라고 생각하면 편함
public int DFS_2(int n) {
if(n == 1) {
return 1;
}else if(n == 2) {
return 1;
}else {
return DFS_2(n-2)+DFS_2(n-1);
}
}피보나치도 가장 중요한 부분인 DFS_2 매서드만 보도록 하겠다. 피보나치는 일종의 수열, 코드에서는 배열과 비슷하게 생각하면 훨씬 편하다. 즉, 첫번째 항과 두번째 항이 1인 수열 이라면 1번째 인덱스의 값과 2번째 인덱스의 값이 1인 배열 이라고 생각한다. 이렇게 생각한 후 아래 순서에 따라서 코드가 실행된다.
1) DFS(5) 일 때 DFS_2(5) = DFS_2(5-2)+DFS_2(5-1) 이 호출된다. => DFS_2(5) = DFS_2(3)+DFS_2(4) 이렇게 되면 DFS_2 가 동시에 2개가 호출되는데 하나씩 먼저 계산된다고 생각하면 편하다. 즉 DFS_2(3) 과 DFS_2(4) 가 동시에 파파팟! 하고 되는게 아니라 DFS_2(3) 먼저 그 다음 DFS_2(4) 이런 느낌으로!!
2) DFS(4) 일 때 DFS_2(4) = DFS_2(4-2)+DFS_2(4-1) 이 호출된다. => DFS_2(2)+DFS_2(3)
3) 대충 눈치 챘겠지만 이러한 과정이 DFS(1) 까지 쭉 반복된다. 그리고 스택에 저장 되었던, 일시 정지되었던 부분부터 다시 실행된다. 이 과정이 끝날때까지 반복되는 것이다. 스택이 몇 개 쌓이는지는 알아서 생각해봐주세요ㅋㅋㅋ
그런데 단순히 이렇게만 하면 물론 실행은 되는데 n = 45 혹은 n = 100 쯤 가면 효율이 엄청나게 나빠진다. 왜냐하면 이 코드는 매번 다시 계산하고 또 하고 또 하기 때문이다. 뭔 말이냐 하면 DFS_2(5) 일 때도 그랬지만 DFS_2(4) 만 구해지면 사실 DFS_2(3) 은 이미 구해져 있는 것과 마찬가지이다. 사실 이것은 정말 당연한 이야기인데, DFS_2(4) 를 구하려면 DFS_2(4) = DFS_2(3)+DFS_2(2) 이기 때문에 DFS(4) 를 찾을때는 DFS_2(3) 가 이미 나와있는 것이다.
이 부분은 사람이 계산하는 방법을 생각하면 편하다. 사람이 피보나치 함수를 계산하는 방식 - 이전 값을 기록해두고 구하기 -을 그대로 사용한다고 생각하면 된다. 뭔 말이냐하면 사람이 f(5) 인 피보나치 함수를 계산 할 때 보통 표를 그리면서 계산할꺼고 f(1) , f(2) f(3) 기록해가면서 f(5) 까지 계산할 것이다. 이렇게 하면 f(5) 일 때 기존에 계산 기록되었던 f(3) f(4) 를 더하기만 하면 f(5) 값을 쉽게 구할 수 있으니까(물론 암산으로 하는 사람도 있겠지만 그런 논외는 논외이다)
근데 지금까지의 방법(위쪽 코드)는 이런게 아니라 f(5) 면 이전에 계산해두었던 것들을 사용하지 않고 다시 f(4)가 얼마인지 f(3)이 얼마인지 —- 하면서 값을 구하고 f(5) 까지 계산하는 식이라 당연히!! 오래 걸릴 수 밖에 없었다. n = 45 쯤가면 계산하는데 무려 10초 이상 걸린다.
그러면 이렇게 이미 값이 나와있는 것을 컴퓨터에서 활용하고 싶을 때 코드로 어떻게 만들 수 있을까? 답은 메모이제이션을 사용하는 것이다. 즉 이미 계산된 값을 어딘가에 저장해두고 컴퓨터보고 이를 활용하라고 시키는 것이다.
class Test{
static int[] fibo; // 배열의 모든 값은 0 으로 초기화
public int DFS_2(int n) {
if(fibo[n]>0) {
// 여기 if 문을 하나 추가하는것으로 인해 엄청나게 속도가 단축된다.
// 원리는 간단한데 위에서 설정한 fibo 배열은 기본적으로 모든 항(인덱스)에 0 으로 초기화된다.
// 이때 이미 한번 구해진 항의 값은 당연히! 0보다 클꺼고,
// 따라서 fibo[n] > 0 이면 즉, fibo 배열에서 n 번째 항이 0보다 크면 해당 값을 이용해서 계산하라는 의미이다.
return fibo[n];
}
else if(n == 1) {
fibo[n] = 1;
return 1;
}else if(n == 2) {
fibo[n] = 1;
return 1;
}else {
return fibo[n] = DFS_2(n-2)+DFS_2(n-1);
}
}
}n = 5 일 때 위 코드가 동작하는 방식은 아래와 같다.
- 코드가 실행됨과 동시에 static 으로 설정된 fibo 배열이 메모리에 올라온다. 이때 n = 1 일 때 fibo[1] = 1 이 들어가고 마찬가지로 n = 2 일 때 fibo[2]= 1 이 저장된다.
1) 위 상태에서 fibo[5] = fibo[3] + fibo[4] 가 되며 각자 DFS_2(4) DFS_2(3) 을 호출한다. => 스택 1
2) DFS_2(3) 은 DFS_2(2) + DFS_1(1) 이다. 이때 컴퓨터에는 다시 DFS_2(1) 과 DFS_2(2) 를 호출한다. => 스택 2
3) DFS_2(2) 일 때 해당 매서드 안에서 컴퓨터는 fibo[2] 값을 찾으며, fibo[2] = 1 임을 알게된다. 마찬가지로 DFS_2(1) 도 fibo[1] = 1 임을 확인한다. 동시에 DFS_2(1) =1 , DFS_2(2) = 1 임을 알게된다(매서드에 return 1 이 있음으로)
4) 다시 스택 2로 돌아와서 DFS_2(3) 은 DFS_2(2) + DFS_1(1) 는 결국 DFS_2(3) = 2 이고 fibo[3] = 2 가 저장된다. => 스택2 종료
5) 다시 스택 1로 돌아와서 DFS_2(3) 은 값이 뭔지 알았으니 다음인 DFS_2(4) = DFS_2(3)+DFS_2(2) 를 호출한다. => 스택 2
6) DFS_2(4) 를 돌 때 DFS_2(4) = fibo[3] + fibo[2] 이고, DFS_2 매서드 안에서 확인한 결과 fibo[3] 과 fibo[2] 값은 0 보다 크다. 이 때문에 fibo[n] 을 return 하고, DFS_2(4) = 2 + 1 이 되어 DFS_2(4) = 3 , fibo[4] = 3 이 저장된다. => 스택 2 종료
7) 다시 스택 1로 돌아와서 컴퓨터는 DFS_2(5) = fibo[3] + fibo[4] 를 확인한다. 동시에 매서드안에서 fibo[n] 이 0보다 큰지 검사하고 fibo[3] 과 fibo[4] 모두 0 보다 큰 값을 갖음으로 DFS_2(5) = 2 + 3 를 계산하여 저장한다. 따라서 DFS_2(5) = 5, fibo[5] = 5 가 된다. => 스택 1 종료
뭔가 살짝 복잡한 것 같지만, 컴퓨터 상에서는 메모리 낭비도 이전 코드보다 훨씬 적고, 뭣보다 속도도 약 2배정도 빠르다. 왜냐하면 이미 계산한 것들은 fibo 배열에 저장해두고 다음 계산하는 것은 이전에 계산해두었던 fibo 배열에서 불러와서 사용하면 되니까.
사실 이 부분이 참 어려운 부분이 것 같다. 나도 솔직히 글을 쓰면서 이게 맞는지 아닌지...한참 고민하면서 작성하고 있다. 아마 앞으로 내가 공부하면서 이 글을 볼꺼고 그때마다 고치게 될 것이라고 생각한다.
나처럼 혼자서 자바를 공부하는 분들에게 조금이나마, 아주 조금이나마 이해를 도울 수 있었으면 한다.
'Java - 알고리즘' 카테고리의 다른 글
| 자바 알고리즘 - 큐(Queue), BFS(너비 우선 탐색), 최단 횟수 찾기 (0) | 2021.11.11 |
|---|---|
| 자바 알고리즘 - 이진트리 순회, DFS (0) | 2021.11.11 |
| 백준 Java - 문자열 단계(1) : 11720번, 10809번 , 2675번, 1157번 (0) | 2021.11.02 |
| 백준 Java - 4단계 1차원 배열 활용하기(3) : 8958번, 4344번 (0) | 2021.10.25 |
| 백준 Java - 4단계 1차원 배열 활용하기(2) : 3052번, 1546번 (0) | 2021.10.20 |
댓글