[알고리즘 기초] 09_SW 문제해결 응용_2 / Python

[알고리즘 기초] 09_SW 문제해결 응용_2\n/ Python

[알고리즘 기초] 09_SW 문제해결 응용_2 / Python

1. 완전 검색 & 그리디

1.1 반복과 재귀

반복(Iteration)과 재귀(Recursion)

• 반복과 재귀는 유사한 작업을 수행할 수 있다.
• 반복은 수행하는 작업이 완료 될때까지 계속 반복
  • 루프(for, while 구조)
• 재귀는 주어는 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 하나의 방법
  • 하나의 큰 문제를 해결할 수 잇는 (해결하기 쉬운) 더 작은 문제로 쪼개고 그 결과들을 결합한다.
  • 재귀 함수로 구현

 

반복 구조

• 초기화
  • 반복되는 명령문을 실행하기 전에 조건 검사에 사용할 변수의 초기값 설정
• 조건검사
• 반복할 명령문 실행
• 업데이트
  • 무한루프가 되지 않게 조건이 거짓이 되게 한다

 

재귀적 알고리즘

• 재귀적 정의는 두 부분으로 나뉜다.
• 하나 또는 그 이상의 기본 경우
  • 집합에 포함되어 있는 원소로 induction을 생성하기 위한 seed 역할
• 하나 또는 그 이상의 유도된 경우
  • 새로운 집합의 원소를 생성하기 위해 결합되어지는 방법

 

재귀 함수

• 함수 내부에서 직접 혹은 간접적으로 자기자신을 호출하는 함수
• 일반적으로 재귀적 정의를 이용해서 재귀 함수를 구현한다.
• 따라서, 기본부분과 유도파트로 구성된다.
• 재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 쉽다.
• 함수 호출은 프로그램 메모리 구조에서 스택을 사용한다. 따라서 재귀 호출은 반복적인 스택의 사용을 의미하며 메모리 및 속도에서 성능저하가 발생한다.

 

반복 또는 재귀

• 해결할 문제를 고려해서 반복이나 재귀의 방법을 선택
• 재귀는 문제 해결을 위한 알고리즘 설계가 간단하고 자연스럽다.
  • 추상 자료형의 알고리즘은 재귀적 구현이 가단하고 자연스러운 경우가 많다.
• 일반적으로, 재귀적 알고리즘은 반복 알고리즘보다 더 많은 메모리와 연산을 필요로 한다.
• 입력값 n이 커질수록 재귀 알고리즘은 반복에 비해 비효율적일 수 있다.

 

1.2 완전검색 기법

완전검색으로 시작하라

• 모든 겨웅의 수를 생성하고 테스트하기 때문에 수행속도는 느리지만. 해답을 찾아내지 못할 확률이 작다.
  • 완적 검색은 입력의 크기를 작게 해서 간편하고 빠르게 답을 구하는 프로그램을 작성한다.
• 이를 기반으로 그리디 기법이나 동적 계획법을 이용해서 효율적인 알고리즘을 찾을 수 있다.
• 검정 등에서 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직하다.

 

1.3 조합적 문제

순열

• 서로 다른 것들 중 몇개를 뽑아서 한줄로 나열하는 것
• 서로 다른 n개중 r개를 택하는 순열은 아래와 같이 표현한다.
  • nPr
• 그리고 nPr은 다음과 같은 식이 성립한다.nPr = n * (n-1) * (n-2) * ... * (n-r+1)
• nPn = n!이라고 표기하며 factorial이라 부른다.
• 다수의 알고리즘 문제들은 순서화된 요소들의 집합에서 최선의 방법을 찾는 것과 관련있다.
  • 예) TSP
• N 개의 요소들에 대해서 n! 개의 순열들이 존재한다.
  • 12! = 479,001,600
  • n > 12인 경우, 시간 복잡도 폭발적으로 up!!

 

순열 생성 방법

• 사전적 순서
  • {1, 2, 3}, n = 3 인 경우 다음과 같이 생성된다.
  • [1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]
• 최소 변경을 통한 방법
  • 각각의 순열들은 이전의 상태에서 단지 두 개의 요소들 교환을 통해 생성
  • ['1' 2 '3'] -> ['3' '2' 1] -> [2 '3' '1'] -> ['2' '1' 3] -> ['3' '1' 2] -> [1 3 2]
• 재귀 호출을 통한 순열 생성

 

부분 집합

• 집합에 포함된 원소들을 선택하는 것이다.
• 다수의 중요 알고리즘들이 원소들의 그륩에서 최적의 부분 집합을 찾는 것이다.
  • ex) 배낭 짐 싸기
• N개의 원소를 포함한 집합
  • 자기 자신과 고집합 포함한 모든 부분집합의 개수는 2^n개
  • 원소의 수가 증가하면 부분집합의 개수는 지수적으로 증가

 

부분집합 생성방법

• 바이너리 카운팅을 통한 사전적 순서
  • 부분집합을 생성하기 위한 가장 자연스러운 방법이다.
  • 바이너리 카운팅은 사전적 순서로 생성하기 위한 가장 간단한 방법이다.