1. 알고리즘의 목적
알고리즘 설계 능력은 코딩 뿐만 아니라 실생활에서도 문제를 인지하고 구조적으로 분석하여 합리적인 문제해결방안을 설계하는데 꼭 필요한 능력이다.
따라서 제대로 공부한다면 배우는게 많을 것이다....ㅎㅎ
2. 알고리즘이란?
알고리즘이란 어떤 'problem'을 해결하는 방법을 모호하지 않게 일련의 과정으로 명확하게 설명한 것을 의미한다.
프로그래밍에서 어떤 프로그램이 임의의 Input을 받아서 원하는 Output을 출력해준다고 했을 때, 그 프로그램의 구조 및 원리를 알고리즘에 의해 설계되었다고 한다. 그림을 보면 좀더 직관적으로 이해할 수 있을 것이다.
3. 알고리즘의 조건
1) Finiteness
유한한 과정 안에 결과가 도출되어야 한다.
2) Definiteness
각 스텝이 모호하지 않고 명확하게 정의되고 표현되어야 한다.
3) Clearly specified input
가능한 Input이 명확하게 정의되고 표현되어야 한다.
4) Clearly specified/expected output
가능한 임의의 Input에 대하여 항상 옪은 Output이 도출되어야 한다.
5) Effectiveness
각 스텝이 충분히 단순하고 효율적이어야 한다.
4. 문제 분석 및 알고리즘 설계 과정
1) Understand the problem
- 문제의 요구사항 및 제약조건 파악
- 이미 해결방식이 널리 알려진 알고리즘에 대한 문제인지 파악
- 기존의 알고리즘들로 해결이 안된다면 새로운 알고리즘 설계
- 사용가능한 컴퓨팅 파워(속도 및 메모리 공간) 체크
- 요구되는 컴퓨팅 파워를 예상하여 작업 환경 선택
2) Choose between 'Exact' vs 'Approximate' solving
-
애초에 정확한 답을 도출할 수 없는 문제인지 파악
(예를 들어, 루트 계산 혹은 비선형 방정식 풀이 등은 exact 불가능) -
exact도 가능은 하지만, 그럴 경우 굉장히 느려지는 경우인지 파악
(예를 들어, 굉장히 많은 양의 데이터를 활용할 경우, 너무 많은 경우의 수가 알고리즘 내에 존재할 경우) -
문제에 따라 exact보다 approximate 방식이 더 세련된 해결책인 경우도 있음
3) Choose 'Algorithm Design Technique'
어떤 방식(전략)으로 알고리즘을 설계할 것인지 선택한다. 동일한 문제라도 전략이 다를 경우, 다른 알고리즘이 설계될 수 있다.
- Brute force
- Decrease and conquer
- Divide and conquer
- Transform and conquer
- Greedy approach
- Dynamic programming
- Backtracking and branch-and-bound
- Space and time tradeoffs
위의 8가지 방식에 대하여 각각의 방식이 여러 가지 문제들에 어떻게 대응하여 알고리즘을 설계해나가는지 보도록 하자.
4) Design an algorithm and Data Structure
위에 존재하는 8가지의 방식이 모든 문제에 대하여 전부 적용될 수 있는 것은 아니다. 때로는 몇 개의 방식은 정말 적절하지 않을 정도로 문제와 맞지 않는 경우도 있다.
그렇기 때문에 일단, 문제에 대한 파악이 끝났다면 그 문제에 적절한 설계 방식을 택하여야 한다. (아니면 여러 방식을 결합할 수도 있다.)
그 뒤에는 이제 그 방식대로 문제를 해결하는 알고리즘을 설계해야한다.
이 때, 필요한 것이 바로 '적절한 자료구조의 선택' 이다. 적절한 자료구조는 우리가 설계한 알고리즘의 효율을 최대한으로 올려준다. 실제로 프로그래밍에서 '자료구조'와 '알고리즘'은 절대 분리할 수 없는 개념이다.
Algorithm + Data Structure => Program
- 자료구조의 종류
- List
- Stack
- Queue
- Priority Queue
- Heap
- Graph
- Tree
- Set and Multi_Set
- Dictionary
5) Specify the Algorithm
알고리즘을 표현하는 방식은 여러 방식이 있지만, 추천하는 방식은 의사코드(pseudocode)를 사용하여 표현하는 방식이다. 의사코드는 자연어보다 훨씬 명확하고 프로그래밍 언어보다는 가독성이 뛰어나기 때문에 설계한 알고리즘을 표현하기에 가장 적합한 방식이다.
6) Prove an Algorithm's Correctness
쉽게 말하면, 위에서 말한 알고리즘의 조건들을 모두 만족하는지 점검하는 과정이다.
좀더 자세히 말하면, 5가지 조건 중 1~4)까지의 조건들을 만족하는지 점검하는 과정이다.
7) Analyze the Algorithm
위에서 5가지 조건 중 4가지를 점검한 후 마지막 조건인 'Effectiveness'를 점검하는 과정이다. 이 조건은 두 가지로 나누어 점검하게 된다.
- Efficiency
- Time Efficiency(시간 효율성) = 시간 복잡도로 계산
- Space Efficiency(공간 효율성) = 공간 복잡도로 계산
- Simplicity
- 그저 simple is best.... 세상의 진리...
8) Code and test the Algorithm
설계한 알고리즘을 실제 프로그래밍 언어를 활용해 코드로 옮기고 compile & debug 과정을 통해 최종적으로 에러를 확인한다.
5. 대표적인 문제들의 유형
- Sorting (정렬)
- Searching (탐색)
- String Processing (문자열 처리)
- Graph Problems (그래프 문제)
- Combinatorial Problems (조합 문제)
- Geometric Problems (기하 문제)
- Numerical Problems (수치 문제)
