알고리즘
알고리즘 : 문제를 해결하기 위한 자세한 방법
좋은 알고리즘이란?
1.
문제를 해결하는 것
2.
문제를 더 잘 해결하는 것
선형 탐색과 이진 탐색
O(n), O(log2n)
정렬
오름차순 정렬, 내림차순 정렬
가장 기본적인 개념, 모르면 안 된다!!
선택 정렬(selection sort)
•
가장 작은 값을 찾아서 0번에 놓고
•
두 번재로 작은 값을 찾아서 1번에 놓고
•
세 번째로 작은 값을 찾아서 2번에 놓고
각 위치에 어떤 값이 들어갈지 찾는 것
그렇기 때문에 고려해야하는 전체 값을 줄여나가는 방향으로 알고리즘을 설계
삽입 정렬(insertion sort)
각 값이 어떤 위치로 가야할지 찾는 것이다.
그렇기 때문에 포함되는 위치를 늘려가는 방향으로 알고리즘을 설계
신경써야할 것
시간과 공간 (시간>공간)
시간 : 속도가 빨라야 한다
공간: 컴퓨터의 저장공간
시간복잡도
프로그램이 돌아가는 시간으로 판단하는건 적합하지 않다.
시간 복잡도 → 데이터가 많아질수록 걸리는 시간이 얼마낙 급격하게 많아지는 비교하는 개념
점근 표기법 (Big - O Notation) : 절대적인 시간이 아닌 성장성
O(1) → 리스트의 길이에 따라 영향을 받지 않는다
O(n) → 리스트의 길이에 비례하여 영향
O(n^2) → 리스트의 길이의 제곱에 비례하여 영향
O(n^3) → 리스트의 길이의 세제곱에 비례하여 영향
선형 → 최소: O(1) 최악: O(n)
이진 → 최소: O(1) 최악: O(logn)
재귀함수
•
같은 형태의 더 작은 문제를 풀고 → 부분 문제 or subproblem
•
부분 문제의 답을 이용해서 기존 문제를 푸는 것
반복문으로 풀 수 있는 건 재귀함수로 풀 수 있다.
재귀적인 거는 반복문으로도 풀 수 있다.
재귀함수의 단점?
→ 함수의 내부적인 동작방식: 프로그램이 끝나는 위치를 기억해야한다. 이 부분을 콜 스택이라 하는데, 콜 스택이 너무 많이 쌓이면 프로그램이 중단된다. 콜 스택이 너무 많이 발생하면 스택 오버플로우를 내놓는다.
반복문으로 풀면 엄청 지저분한데, 재귀함수로 풀면 엄청 깔끔해지는 것들
재귀적으로 너무 많이 호출한다면 반복문으로 하는게 더 좋다.
알고리즘 패러다임
Brute Force
무차별 대입 공격 : Brute - Force Attack
비효율적이다. 인풋이 클수록 비효율성이 커진다.
직관적이고 명확하다. 답을 확실하게 찾을 수 있다.
인풋이 크지 않는다면 brute force를 사용할 수도 있다.
효율적인 알고리즘의 첫 시작은 brute force이다. 여기가 발전의 시작
Divide and Conquer
분할 정복
문제 → 답을 바로 알아내기에는 문제가 크다. 나눠서 풀어보자.
각 부분 문제를 풀고, 각 솔루션에 대해서 큰 문제의 답을 알아내면 된다.
Divide → Conquer → Combine
f(x) → Divide (x = x1, x2 ) → Conquer(f(x1), f(x2)) → Combine
Example
1.
1~100까지 더하는 문제
1~50, 51~100 → 유형은 같은데 크기만 작아진 것
2.
Merge Sort
Divide: 리스트를 반으로 나눈다.
Conquer: 왼쪽 리스트와 오른쪽 리스트를 각각 정렬
Combine: 정렬된 두 리스트를 하나의 정렬된 리스트로 합병
3. Quicksort
Divide: pivot을 기준으로 왼쪽에는 pivot보다 작은 것을 놔두고, 오른쪽에는 pivot보다 큰 것을 놔둔다.
Conquer: 왼쪽 오른쪽을 각각 정렬한다.
Combine: 딱히 할게 없다.
Dynamic Programming
부분 문제들의 최적의 답을 이용하여 기존 문제의 최적 답을 구할 수 있다.
중복되는 부분 문제 → 해결하는게 Dynamic Programming
merge sort ⇒ 중복되는 부분 문제가 없다.
어떤 문제의 최적 부분 구조가 있다 → 부분 문제들의 최적의 답을 이용해서 기존 문제를 풀 수 있다.
최적 부분 구조 → 중복되는 부분 문제들이 있으면 → Dynamic programming을 이용해서 풀 수 있다.
한 번 계산한 결과를 재활용하는 방식
구현 방식 : Memoization , tabulation
Memoization ⇒ 중복되는 계산은 계산 후, 메모
하향식 접근 → Top Down approach
재귀를 기반으로 코드를 작성
tabulation ⇒ fib(6)을 구하기 위해서 fib(1)부터 구해서 상향식 접근.
단순히 반복문을 사용해서 리스트를 채워나간다.
Memoization vs Tabulation
메모이제이션 → 재귀함수
Tabulation → 반복문을 사용
memoization → 재귀호출이 너무 많이 일어나면, 과부하가 걸려서 오류가 날 수 있다.
Tabulation → 반복문을 사용하기 때문에 그럴 위험이 없다.
Tabulation → n번째 값을 계산하기 위해서 중간에 필요없는 것들까지 모든걸 구한다.
Memoization → 위에서부터 필요한 계산이 뭔지 요구를 하는 거라서, 필요없는 계산은 안해도 된다.
피보나치 수열 → Tabulation : 시간 복잡도(O(n)) 공간 복잡도(O(n))
리스트 대신, current와 previous를 저장한다. 가장 최근값 두개를 사용
current = current + previous
previous = current 이런 식으로
⇒ 사용하는 메모리는 고정되어있기 때문에 공간복잡도 O(1)
Greedy Algorithm
당장 눈 앞에 보이는 최적의 선택을 하는 방식
장점: 간단하고 빠르다
단점: 최적의 답이 보장되지 않는다.
언제 사용하냐 ⇒ 문제를 해결하는 다른 알고리즘이 너무 느려서 사용이 불가할 때. 애초에 최적의 답이 필요 없을 때 사용한다.
제일 좋은 상황: Greedy Algorithm으로 최적의 답을 찾는 것
언제 최적의 답을 보장해주느냐?
두 가지를 찾으면 된다.
1.
최적 부분 구조를 찾자.
2.
탐욕적 선택 속성
a.
각 단계에서의 탐욕스런 선택이 최종 답을 구하기 위한 최적의 선택이다.
Ex: 최소한의 동전을 거슬러 주는 방식