Intro to Algorithm
알고리즘: 문제를 어떤 식으로 푸는 것이 최선인가
Time Complexity
시간복잡도
시간 복잡도를 고려한다는 것은
입력값의 증가/감소함에 따라 시간이 얼마만큼 비례하여 증가/감소하는가?를 생각하는 것이다.
효율적인 알고리즘을 구현한다는 것은
입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성한다는 이야기
Big-O 표기법: 최악의 경우
그래프에서
가로축: 옮겨야하는 물건의 갯수
세로축: 물건을 나르는 능력
기울기: 클수록 (가파를수록) 느린 시간복잡도
socrative
- 두 알고리즘 A, B의 시간 복잡도가 각각 O(n), O(logn) 라면,
알고리즘 B가 알고리즘 A 보다 항상 빠르다. [X]
항상 빠른것은 아냐
나를 물건이 하나면 결과값이 모두같게 나와
즉, 같은 경우도 있으니 항상 빠른건 아니다.
n이 점점 커질수록 B가 더 빨라집니다.
input이 1개일경우 —> 둘 다 1
input이 2개일 경우 —> 1 / 2
input이 4개일 경우 —> 2 / 4
input이 8개일 경우 —> 3 / 8
- 알고리즘의 시간 복잡도를 나타낼 수 있는 표기법
Big-O는 최악의 경우, Big-Ω(omega)는 최선의 경우, Big-Θ(theta)는 그 둘의 평균
- for문의 시간복잡도는? O(n)
5개의 물건을 옮겨야한다.
1초에 한개씩 옮기고
10개가 있으면 10번을 나르게 된다.
n개가 있으면 n번이 나오겠지
일반적으로 for문은 O(n)의 시간복잡도를 갖고있습니다.
++ for 문 내의 코드가 arr의 길이만큼만 실행됩니다. arr의 길이를 n이라고 놓으면, O(n)이라고 쉽게 파악할 수 있습니다.
- 다음의 시간 복잡도를 가지는 알고리즘들이 있을 때, 가장 느린 것과 가장 빠른 것을 모두 고르면? (단, n ≥ 10,000)
가장 빠른 것: O(log n), 가장 느린 것: O(n!)
O(2^n)이 가장 느리다라고 생각했는데 O(n!)이 가장 느리다!ㅡ
nlogn
처음에는 일잘하는것 같더니 후에는 느린것
logn보다 느리고 n보다 느려
merge sort(합병정렬)는 나누고 합치기때문에 nlogn
2^n
느리다. 일시키면 하나더 가져오는 놈
1
지게차
n^2
2^n보다 빠르다.
빠른순서 1 log n n^2
n!
그래프를 보면 엄청 가파르다.= 가장 느려
10개 시키면 10개라는건 뭔가왜 일을해야하나이런식으로
깊게 들어가는 아이야 10개를 나를려면 끝이 보이지않아
logn
제곱을 표시하기 위한 수 O(1)다음으로 빠른놈
y= log2n
3= log28
2개-1초 4개-2초 16개-4초
- f(n) = 2^n
f(n) = n log n
f(n) = n x n-1 x n-2 ...x n-n-1
f(n) = log n
빠른순으로 나열 4-2-1-3
시간복잡도의 빠른 순서는
O(1) →O(logn) → O(n) → O(nlogn) → O(n^2) → O(n^3) → O(2^n) → O(n!)
- for (let i = 0; i <n; i++) {
for (let j = 0; j<n; j++) {
}
}
다음과 같은 코드의 시간 복잡도로 올바른 것은?
O(n^2)
n개의 i에 대해 각각 n개의 j를 가지고 로직을 수행하므로 O(n^2)의 시간 복잡도를 갖는다.
for문에 또 for문을 돌리게 되면 n^2
- let a = 0
let b = 0
for (i=1; i<n; i++)
a = a + 1
for (j=2; j<n; j++)
b = b + 1
다음 코드의 시간 복잡도는 Big-o 표기법중 O(n)이다.
n=3이라고 하면 i는 2번 연산한다.
i가 1부터니깐 n-1번 연산한다.
0부터시작하면 n번연산
j는 2부터 시작하기때문에 n-2번 연산한다.
수학적으로 2n-3이 되겠지 -> n
- 다음은 스택을 표현한 코드입니다. 나올 수 있는 시간 복잡도는
O(1), O(n)
스택에서 찾을 수 있는 시간 복잡도는
1. 스택에 새로운 요소를 넣거나 뺄 때 발생하는 O(1) (넣을 때와 뺄 때 가장 마지막 요소를 넣거나 뺍니다.)
2. 스택을 탐색하는 O(n) (스택 한 번 순회)
- let i = n
while (parseInt(i) > 0) {
i = i / 2;
}
다음과 같은 코드의 시간 복잡도를 올바르게 나타낸 것은?
O(log n)
N이 주어졌을 때 계속해서 1/2씩 줄어들기 때문에 연산 횟수는 log2(n)이고 Big-O 표기법으로 나타내면 O(log n)
- //k > 0
for (let i = 0; i < n; i++) {
i *= k;
}
다음과 같은 코드의 시간 복잡도를 올바르게 나타낸 것은?
O(log n)
i++때문에 예시에서 3으로, 7로 가는거네!
그래서 2,6,14라는 결과가 찍히는 것!
log base는 big O notation에서 중요하지 않기때문에 사실상 log n 이 정답
수학적으론 k배수만큼 i가 커지며 n에 도달하고 있기 때문에 log(k) n
log(base2) 8 === 3
log(base3) 27 === 3
i는 2씩 곱하게 되겟지
i=1 -> 2
i=2 -> 6
i=6 -> 14
Greedy Algorithm
그 순간순간마다 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식
탐욕 알고리즘 문제해결단계
1. 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택합니다.
2. 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사합니다.
3. 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번으로 돌아가 위의 과정을 반복합니다.
Dynamic Programming
모든 경우의 수를 따져본 후 이를 조합해 최적의 해법을 찾는 방식
