알고리즘 문제 해결 전략1 study 정리

[1]. 문제 해결 시작하기


[2] 알고리즘 분석


[3] 알고리즘 설계 패러다임
6. 무식하게 풀기
6.2. 중첩 반복문 대체하기(Recursive)

7. 분할 정복
주어진 문제를 둘 이상의 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산

8. 동적 계획법 - Memoization (캐쉬에 저장)
처음 주어진 무제를 더 작은 문제들로 나눈뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 냄
답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함으로서 속도 향상을 꾀할 수 있음
*Memoization 함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법

10. Greedy method
재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 같음
하지만, 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만들 선택
1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우
2. 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어려울 때 근사해를 찾는 것으로 타협함

11. 조합 탐색( combinatorial search)
- 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아내는 알고리즘
(1) 가지치기(pruning) - 탐색 과정에서 최적해로 연결될 가능성이 없는 부분들을 잘라냄

12. 최적화 문제 결정 문제로 바꿔 풀기
최적화 문제를 결정 문제(decision problem)로 바꾼 뒤, 이것을 이분법을 이용해 해결
결정 문제란 예 혹은 아니오 형태의 답만이 나오는 문제

[4] 유명한 알고리즘들
13. 수치 해석
직접 풀기 힘든 수학 문제를 근사적으로 푸는 알고리즘과 이들의 수치적 안정성, 오차의 범위등을 연구하는 전산학의 한 분야

13.2 이분법(bisection method)
주어진 범위 내에서 어떤 함수의 값이 0이 되는 지점을 수치적으로 찾아내는 기법

14 정수론
14.2 소수
주어진 수가 소수인지 확인하는 것

14.2 소인수 분해
- 한 합성수를 소수들의 곱으로 표현하는 방법
- 에라토스테네스의 체

15. 계산 기하(computational geometry) ( 하는 일과 관련이 있으니 꼭 다시 볼 것!!!!)
점, 선, 다각형과 원 등 각종 기하학적 도형을 다루는 알고리즘을 계산
- 대회에서는 대부분 2차원 기하학
(1) 벡터의 구현
(2) 점과 직선, 선분의 표현
(3) 벡터의 내적과 외적
15.3. 교차와 거리, 면적