‘프로그래머가 알아야 할 알고리즘 40’(임란 아마드 지음, 길벗 출판사) 을 통해 알고리듬 기초 이론을 공부. 복습하고나서, 공부한 내용을 내 언어로 바꾸어 기록한다.
알고리듬(Algorithm)
정의
특정 입력을 받아서, 가장 효율적 방식으로 출력 도출하는. 논리흐름.
또는
문제에 대한 수학적 해결책.
알고리듬 로직 표현하는 방법
1. 의사코드
구조화된 방식으로 알고리듬 로직을 표현한다.
2. 스니펫
프로그래밍 언어로 표현한 알고리듬.
3. 실행계획
각 작업 별로 알고리듬을 쪼개서 그 로직 표현한다.
각 작업 블록을 ‘스테이지’라고 한다.
스니펫 만으로는 알고리듬 로직 표현이 어려울 때(알고리듬이 매우 복잡한 경우) 주로 사용한다.
알고리듬 분류
1) 문제 특성에 따른 알고리듬 분류
1. 데이터 집약적 알고리듬
대규모 데이터 처리하는 알고리듬.
2. 연산 집약적 알고리듬
대규모 연산 수행하는 알고리듬.
3. 연산/데이터 집약적 알고리듬
대규모 데이터에 적용되며, 대규모 연산 수행하는 알고리듬
2) 출력 결과에 따른 알고리듬 분류
1. 결정론적 알고리듬
특정한 입력에 대해 항상 같은 출력 결과 제공하는 알고리듬.
2. 비결정론적 알고리듬
난수가 개입되어, 특정한 입력에 대해 항상 다른 결과 나올 수 있는 알고리듬.
3) 복잡도 낮추기 위해 정확도 희생 여부에 따른 분류
1. 최적 알고리듬
정확도 희생 안 한다. 문제에 대한 정확한 해결책 찾아내는 알고리듬.
2. 근사 알고리듬
복잡도 줄이기 위해 정확도 다소 희생한 알고리듬.
알고리듬 성능 분석하기
알고리듬 복잡도(알고리듬 성능 측정 지표)
- 알고리듬 공간복잡도 분석: 알고리듬 실행이 얼마만큼 메모리 필요로 하는가.
- 알고리듬 시간복잡도 분석: 알고리듬 실행에 얼마만큼 시간이 소요되는가.
알고리듬 복잡도 줄이기(알고리듬 성능 향상하기)
알고리듬 복잡도를 줄이기 위해서는 정확도를 희생해야 한다.
알고리듬 성능 $\Rightarrow$ 복잡도 와 정확도 사이 줄다리기.
알고리듬 설계
정의
주어진 자원과 제약조건 내에서, 문제의 기능적. 비기능적 요구사항 최대로 충족시킬 방법 찾기.
1) 사전과정
문제의 기능적, 비기능적 요구사항 파악하기.
문제의 기능적, 비기능적 요구사항
- 문제의 기능적 요구사항: 문제의 입력과 출력 파악하기.
- 문제의 비기능적 요구사항: 알고리듬 성능, 보안 기대치 파악하기.
2) 과정 중 고려해야 할 특성들
- 알고리듬 정확성: 특정한 입력에 대해 ‘정확한’ 출력 내놔야 한다.
- 알고리듬 최적성: 현재 알고리듬이 최적 알고리듬인가 판단.
- 알고리듬 확장성: 이 알고리듬을 더 큰 데이터셋에도 적용할 수 있는가.
알고리듬 검증
1. 알고리듬 정확성 검증에 필요한 거
- 특정 입력에 대한 ‘정답’ 값.
- 알고리듬 정확성 측정 지표
2. 알고리듬 최적성 검증에 필요한 거
- 문제의 복잡도 파악하기
3. 알고리듬 확장성 검증에 필요한 거
- 데이터 크기와 알고리듬 공간. 시간복잡도 사이 관계 파악하기
데이터 크기 증가 $\Rightarrow$ 알고리듬 공간복잡도 크게 증가: 알고리듬 확장성 떨어진다.
데이터 크기 증가 $\Rightarrow$ 알고리듬 시간복잡도 크게 증가: 알고리듬 확장성 떨어진다.
vice versa.