자료구조와 함께 배우는 알고리즘 입문 1

in Study on PYTHON

  • 05-1
    1. 재귀 : 어떤 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의
    2. recursive definition 재귀적 정의가 성립해야 재귀를 사용할 수 있다
    3. 재귀 호출은 자기 자신과 똑같은 함수를 호출하는 것이다
    4. 재귀는 두 종류가 있다 1) 직접 재귀(direct) 2) 간접 재귀(indirect)
    5. 책에서는 재귀의 예시로 1) 팩토리얼 구하는 법 2) GCD(최대 공약수) 구할 때 유클리드 호제법 쓰는 법을 재귀로 설명
  • 05-02
    1. 재귀 알고리즘은 2가지 방법으로 분석한다. 1) 하양식 분석(top-down) 2) 상향식 분석(bottom-up)이다.
    2. 개인적인 생각으로는 가장 밑 단계부터 분석하는 상향식 분석(bottom-up)이 재귀에서는 좋은 것 같다
    3. 재귀 알고리즘을 비재귀적으로 표현 할 수 있다. 3-1) 꼬리 재귀 제거 : 동일한 의미를 가진 재귀가 아닌 다른 표현으로 대체하는 것 3-2) 재귀 자체를 제거 : 재귀는 자기 자신과 똑같은 함수를 호출하면서 임시로 값을 저장한다. 재귀의 이런 특성을 구현하는 것이 Stack 자료구조이다. stack을 활용해서 재귀를 제거할 수 있다.
  • 05-03
    1. 재귀 알고리즘으로 분석할 수 있는 하노이의 탑
    2. 규칙 : 가장 넓은 판 한 개와 나머지 덩어리로 묶는다 & 3개의 기둥을 시작,중간,목표 기둥으로 나눈다(숫자로 치면 1,2,3으로 분류) -> (나머지 덩어리를 시작 -> 중간으로 이동) -> (가장 넓은 판을 시작 -> 목표기둥으로 이동) -> (나머지 덩어리를 중간 -> 목표기둥으로 이동) 이걸 재귀적으로 반복하면 된다.
  • 05-4
    1. 재귀 알고리즘의 예시 2번째 8퀸 문제
    2. 배치 할 수 있는 배치 조합을 열거하는 작업 == 분기(branching) 작업이라 한다
    3. 큰 문제를 작은 문제로 분할하고, 작은 문제의 풀이법을 결합하여 전체 풀이법을 얻는 방식 == 분학 정복법(divide and conquer)이다 ==> 뭔가 규칙을 나눠서 재귀도 잘 돌리고 어떻게 하는거 같은데 이해가 잘 가지 않는다…8퀸은 잘 모르겠다.