이머시브 과정 3주차 첫째날이다.
오늘부터 Algorithm 파트를 배우게 되었다.
이번 파트도 저번에 배운 자료구조와 같이 어려울 거라고 예상을 했지만 역시나 예상대로 였다 ... 블로깅을 하면서 오늘 배운 내용을 정리하고 다시 되새겨 보자 !
🔥Today Lesson🔥
- Time Complexity
- Greedy Algorithm
- Dynamic Programming
Time Complexity 🐳
시간복잡도란?
특정 알고리즘이 어떤 문제를 해결하는데 까지 걸리는 시간을 의미한다. 같은 결과를 가져오는 문제를 어떻게 작성하느냐에 따라 걸리는 시간이 길어질수도 있고 짧아질수도 있다. 효율적인 알고리즘을 구성하기 위해서는 시간복잡도를 따져가며 작성하는것이 좋다.
Big-O
시간복잡도를 표기하는 방법중에 가장 많이 쓰이는 것이 Big-O 표기법이다. 시간 복잡도에는 여러 개념이 있지만 그 중 가장 중요한것은 '아무리 오래 걸려도 이 시간 안에는 끝날 것'의 개념이 중요하다 한마디로 시간복잡도를 고려 할때 최선의 경우만 생각하는 것이 아닌 최악의 경우를 대비하는 것이 중요하기에 Big-O 표기법이 쓰인다.
Big-O 표기법의 종류
1. O(1): 입력값의 크기와는 상관없이 언제나 일정한 시간이 걸리는 표기법이다.
2. O(n): 입력값의 크기에 비례해 시간이 증가하는 표기법 이다. 예를들어 10배가 걸리는 입력값을 했을시 시간도 10배가 증가하는 것을 의미한다.
3. O(log n): 입력값의 크기가 커지더라도 속도에 영향을 받지 않고 실행 시간이 지날수록 처리해야 하는 양의 절반이 줄어들고 실행시간은 증가하지만 속도는 감소하는 것을 의미한다.
O(log n)표기법은 O(1) 다음으로 빠른 표기법이다.
4. O(n^2): 입력값이 증가함에 따라 그 시간이 제곱수 만큼 증가하는 표기법이다.
5. O(2^n): Big-O 표기법중 가장 느린 표기법으로 구현한 알고리즘의 시간 복잡도가 O(2^n)이라면 다른 접근 방식을 고민해 보는 것이 좋다. 재귀로 표현한 피보나치 수열이 대표적인 O(2^n)표기법이다.
Greedy Algorithm 🐳
Greedy Algorithm은 탐욕 알고리즘 으로 말 그대로 눈 앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법이다.
탐욕 알고리즘에 문제 해결법을 단계적으로 나누어 보면 다음과 같을 것이다.
- 선택절차: 현재 상태에서의 최적의 해답을 선택한다.
- 적절성 검사: 선택된 해가 문제의 조건을 만족하는지 검사한다.
- 해답검사: 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번으로 돌아가 위의 과정을 반복한다.
Dynamic Programming 🐳
Dynamic Programming은 동적 알고리즘으로 앞서 다룬 탐욕 알고리즘과 비슷하게 작은 문제에서 부터 출발하는점은 같지만 동적 알고리즘은 모든 경우의수를 다 따져서 최적의 해법을 찾는 방식이다.
동적 알고리즘은 주어진 문제를 여러개의 하위 문제로 쪼개어 하위 문제들의 해결법을 결합하여 최종문제를 해결해 나아가는 방식이다.
동적 알고리즘은 다음 가정이 만족할때 사용가능하다.
- 큰 문제를 작은 문제로 나눌수 있고 이 작은 문제들은 중복된다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.
하루를 마치며👋
오늘 배운 알고리즘 파트도 예상대로 만만치 않았다... 코플릿 문제를 페어와 마주할때 마다 고민하는 시간이 더 많고 속으로는 이번 ha는 진짜 큰일났다라는 생각밖에 안들었던거 같다... 내용 이해는 잘 했다고 생각했는데 막상 문제를 마주하면 대입하려고 하니 머리가 새하얘진다... 계속계속 문제를 보고 고민해보면 언젠간 능숙하게 하는 날이 오겠지...? 그전까진 힘들지만 이겨내려고 노력해야겠다 ㅠ...!!!
