알고리즘 - 문제 해결 과정

문제 해결 과정

문제의 이해

• 주어진 문제를 정확히 이해
• 올바른 알고리즘은 “대부분의 입력”이 아니라 “모든 유효한 입력”에 대해 정확한 해답을 구할 수 있어야

  설계 방향 결정

• 순서적 알고리즘
• 병렬적 알고리즘
• 최적해, 근사해

근사해를 고려해야 하는 상황

• 정확한 해 자체를 구할 수 없는 문제 ex. 제곱근 문제
• 계산량이 너무 많아져서 현실적인 시간에 해결할 수 없는 문제
• 알고리즘의 중간 단계에서 근사해가 사용 ex. 분기한정 기법

알고리즘 설계

• 억지 기법: 문제의 정의를 가장 직접 사용하는 방법6
• 탐욕적(greedy) 기법: 단순하고 직관적인 방법으로 모든 경우를 고려해 보고 가장 좋은 답을 찾는 것이 아니라 어떤 결정을 해야 할 때마다 “그 순간에 최적” 이라고 생각되는 것을 선택하는 방법
• 분할 정복: 주어진 문제를 여러 개의 더 작은 문제로 반복적으로 분할하여 해결 가능한 충분히 작은 문제로 만든 다음 해결하는 전략
• 동적 계획법: 작은 문제를 해결한 결과를 ‘저장’하여 다음에 더 큰 문제를 해결할 때 사용하는 것이 분할정복과 가장 큰 차이
• 공간으로 시간을 버는 전략: 추가적인 공간을 사용하여 처리시간을 줄이는 전략
• 백트래킹과 분기한정 기법: 상태공간트리에서 해를 단계적으로 찾아가는 과정에서 현재의 해가 최종해가 될 수 없다고 판단되면 더는 탐색하지 않고 되돌아가서 다른 후보해를 탐색하는 방법

알고리즘의 정확성

• 실험적 분석: 다양한 입력을 이용해 알고리즘을 테스트하여 타당성을 보이는 방법
• 증명적인 분석: 수학적으로 타당성을 증명하는 방법, 수학적 귀납법 등이 이용

알고리즘 분석

• 시간 효율성, 공간 효율성

알고리즘의 구현

• C언어와 같은 컴파일 기반 언어 => 실행 효율
• 파이썬과 같은 인터프리터 언어 => 빠른 구현과 알고리즘의 동작 확인