알고리즘 자료구조 - 5

5장
 - 재귀알고리즘
    : 자기자신을 사용하여 자신을 정의할때 재귀적(recursive)이라 한다
 - 재귀함수 : 자기와 동일한 함수를 호출하는 함수
 - 재귀알고리즘을 사용하는 경우: 풀어야할 문제, 계산할 함수, 처리할 데이터구조가 재귀로 정의되는 경우


1)
순차곱셈(factorial)
 - n!
 - if(n>0) n * 함수(n-1)
 - else return 1;


2)
직접재귀: 자신과 동일한 구조의 함수를 직접 호출하는 경우
간접재귀: 다른 함수를 호출하고 해당함수가 자신과 동일한 구조의 함수를 호출하는 경우


3)
유클리드 호제법 : 
 - 두 정수가 주어졌을 때 최대 공약수를 구하는 알고리즘
 - 두 정수가 주어질 경우 큰 값을 작은 값으로 나누었을 때 나누어 떨어지는 작은 값이 최대 공약수
 - 만일 나누어 떨어지지 않으면, 작은 값과 큰%작 값으로 나누고 나누어 떨어지면 두 정수중 작은 값이 최대 공약수
 - 위의 과정을 반복

4)
순수하게(genuinely) 재귀적
 - 함수 내에서 재귀호출을 여러번 수행하는 함수

하향식(top-down) 분석
 - 위에서 아래로 분석. 실행되는 순서대로 나열

상향식(bottom up) 분석
 - 함수가 종료되는 말단부터(혹은 가장 작은 수부터) 위로 쌓아올리며 분석하는 방법


5)
재귀 알고리즘의 비재귀적 표현: 재귀호출을 사용하지 않고 구현하는 방법
 - 꼬리재귀 제거
    : 함수의 말단부에서 재귀함수 호출 시 이는 함수의 처음으로 돌아가는 것과 동일하다.(ex: goto문, continue 등을 사용하여 처음으로 되돌아간다)
 - 재귀의 제거
    : 함수 중간에서 재귀함수 호출시, 동일하게 처음으로 되돌아가려고 해도 현재(혹은 미래)에 실행하고 있는 상태 값을 가지고 있어야 한다.
      따라서 스택을 사용하여 현재의 함수 값(매개변수 등)을 잠시 저장하고 재귀를 수행하고, 이를 반복 수행한다(스택이 다 비워지게되면 끝이 난다)

6)
분할 해결법(divide and conquer) : 문제를 해결하기 위해 문제를 세분화 하고 세분화된 작은 문제의 풀이를 결합해 전체문제를 풀이하는 기법

하노이의 탑
 - 3개의 기둥을 에서, 작은 원반이 큰 원반보다 위에 있도록 유지하며 하나의 기둥에 있는 원반들은 다른 기둥으로 전부 이동시키는 문제

 - 푸는법
    : 시작기둥, 중간기둥, 목표기둥으로 정의
    : 제일 아래 원반(제일 큰 원반)을 시작기둥에서 목표기둥으로 옮기기 위해서는 나머지 원반이 중간기둥으로 이동해야함
    : 그 다음 크기의 원반을 시작기둥에서 목표기둥으로 옮기기 위해서는 나머지 원반이 중간기둥으로 이동해야함
    : 제일 마지막 원반(제일 작은 원반)의 경우 바로 첫번째 기둥으로 옮기면 됨

 - 함수
    : 함수명(원반개수, 시작기둥, 목표기둥)
        재귀호출: 나머지 원반을 시작기둥에서 중간기둥으로
          -> 이때 중간기둥은 목표기둥이 된다
        제일 큰 원반(남은 원반)을 시작기둥에서 목표기둥으로
        재귀호출: 나머지 원반을 중간기둥에서 목표기둥으로
          -> 이때 중간기둥은 목표기둥이 된다
     -> 재귀호출을 반복하기 때문에 함수의 매개변수인 시작기둥과 목표기둥이 계속 바뀌게 되기 때문에
        중간기둥을 구하는 방법이 중요하다.
        ** 기둥을 1, 2, 3으로 명명한다면, 기둥번호의 합이 6이고, 중간기둥은 6-시작기둥-목표기둥 값을 가지게 된다.
        
        
7)
8퀸문제
 - 8x8 체스판에 8개의 퀸을 서로 공격할 수 없도록 배치하는 문제

 - 풀이
     퀸을 배치시키는 경우의 수는 64*63*62*61*60*59*58*57이다(8*8체스판에 1개씩 두면 경우의 수가 64부터 57이다)
     하지만 '서로 공격할 수 없도록' 이라는 조건을 만족시키기 위해
       1. 각 열에는 퀸이 1개씩만 존재한다 -> 8*8*8*8*8*8*8*8의 경우의 수를 가지게 되며, 각 열에 퀸이 배치되었는지 확인하는 배열필요(요소는 퀸이 위치한 열의 위치, 값은 퀸이 위치한 행의 위치를 나타낸다)
         -> 각 열에 퀸을 배치하기 위해 재귀호출을 사용하며, 첫 퀸을 다음행에 배치하기위해 반복문을 사용한다.
       2. 각 행에는 퀸이 1개씩만 존재한다 -> 1의 배열과 함께 퀸을 배치 전, 해당 행에 퀸을 배치했는지 확인하는 배열필요(퀸의 위치에 대한 출력은 1.의 배열로 한다)
         -> 재귀호출 전 해당 행에 퀸이 위치했다 기록 후, 재귀호출이 끝나면(즉 모든 재귀호출이 되었으니) 각 행에 위치한 퀸의 정보를 초기화하기 위해 해당 배열을 클리어한다(이후 반복문을 통해 첫 퀸의 위치를 변경한 다음 경우의 수로 넘어간다)
       3. 각 대각선에는 퀸이 1개씩만 존재한다 -> 2.의 배열들에서 추가적으로 대각선에 퀸을 배치했는지 확인하는 배열이(우상-좌하, 좌상-우하, 2개) 필요하다
         -> 3.에서는 대각선을 위해 행열좌표조합을 i+j, 7+i-j(혹은 7-i+j)를 사용하며, 2.의 경우와 마찬가지로 재귀호출 전 기록, 재귀호출 후 클리어 한다.
     이런식으로 각 경우의 수를 나열하며 조합을 만드는 방식을 가지 뻗기(branching)라고 한다

 ** 위와 같은 풀이로 정상적으로 완료할 경우, 8퀸문제는 92가지의 조합으로 출력된다.