◉ 학습목표
1. 시간복잡도를 이해하고, 가장 많이 쓰이는 Big-O기법의 종류에 대해 알 수 있다.
2. 탐욕 알고리즘을 이해하고, 사용할 수 있다.
3. 구현의 시뮬레이션과 완전 탐색 알고리즘에 대해 이해하고, 이진 탐색 알고리즘을 사요할 수 있다.Before To Start
⦿ 학습내용
☞ 알고리즘
✔︎ 문제를 해결하는 최선의 선택❗️
☞ 의사코드 (pseudocode)
✔︎ 의사코드 : 프로그래밍 언어로 코드를 작성하기 전 일상 언어로 프로그램이 작동하는 원리를 미리 작성하는 것
✔︎ 의사코드 사용 시 장점
① 시간 단축
② 디버깅 용이
③ 프로그래밍 언어를 모르는 사람과도 소통 가능
✔︎ 의사코드 작성 방식
① 다른 사람도 이해할 수 있는 자연어만 사용
② 자연어와 프로그램 언어를 조합하여 사용
- 시간복잡도 (Time Complexity)
⦿ 학습내용
☞ 시간복잡도
✔︎ 입력값을 바꿔주면서 연산을 수행할 때, 연산 횟수에 비해 시간이 얼마만큼 소요되는지를 계산한 것
☞ 시간복잡도 표기 방법
✔︎ Big-O(빅-오) : 시간복잡도를 최악으로 표현
✔︎ Big-𝛀(빅-오메가) : 시간복잡도를 최선으로 표현
✔︎ Big-θ(빅-세타) : 시간복잡도를 중간(평균)으로 표현
☞ Big-O(빅-오) 표기법
✔︎ 최악의 경우도 고려하여 대비하는 것이 중요하기에 Big-O 표기법 많이 사용
✔︎ 입력값의 변화에 따라 연산을 수행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?를 표기
✔︎ 종류
✓ O(1)
∙ constant complexity라고도 함
∙ 입력값이 증가하더라도 시간이 늘어나지 않음
∙ 입력값의 크기에 관계없이 즉시 출력값을 얻어낼 수 있음
✓ O(n)
∙ linear complexity라고도 함
∙ 입력값이 증가함에 따라 시간도 같은 비율로 증가
✓ O(log n)
∙ logarithmic complexity라고도 함
∙ Big-O 표기법에서 O(1)다음으로 가장 빠른 시간복잡도
∙ BST 탐색과 같은 로직으로 연산을 수행할 때마다 절반씩 줄어드는 방식
✓ O(n^2)
∙ quadratic complexity라고도 함
∙ 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가
✓ O(2^n)
∙ exponential complexity라고도 함
∙ Big-O 표기법 중 가장 느린 시간복잡도
∙ 연산을 수행할 때마다 2배씩 늘어나는 방식
- 탐욕 알고리즘 (Greedy)
⦿ 학습내용
☞ 탐욕 알고리즘 (Greedy)
✔︎ 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적 해답에 도달하는 방법
✔︎ 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 근사한 값을 빠르게 도출 가능 → 근사 알고리즘
☞ 단계적 문제 해결 방법
✔︎ 선택 절차(Selection Procedure) : 현재 상태에서 최적의 해답 선택
✔︎ 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건에 만족하는지 확인
✔︎ 해답 검사(Solution Check) : 문제가 해결되었는지 검사하고, 해결되지 않은 경우 선택 절차로 돌아가 다시 반복
☞ 탐욕 알고리즘 적용 조건
✔︎ 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않을 때
✔︎ 최적 부분 구조(Optimal Substructure) : 문제의 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됐을 때
- 구현 (Implementation)
⦿ 학습내용
☞ 구현 (Implementation) - 시뮬레이션 (Simulation)
✔︎ 문제에서 요구하는 복잡한 구현 요구 사항을 빠짐없이 코드로 옮기는 것
✔︎ 모든 과정과 조건이 제시되어, 그 과정에 거친 결과가 무엇인지 확인하는 유형
☞ 구현 (Implementation) - 완전 탐색 알고리즘 (Brute-Force Algorithm)
✔︎ 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식
✔︎ 무차별 대입 방법, 모든 가능성을 시도하여 문제 해결
✔︎ 공간복잡도와 시간복잡도 요소 고려 ❌, 최악의 시나리오를 취하더라도 솔루션을 찾는 방법
✔︎ 문제에 더 적절한 해결 방법을 찾기 전에 시도하는 방법
☞ 완전 탐색 알고리즘 (Brute-Force Algorithm) 사용할 경우
✔︎ 프로세스를 높이는데 사용할 수 있는 알고리즘이 없을 때
✔︎ 문제를 해결하는 여러 솔루션이 있는데 각 솔루션을 확인해야할 때
☞ 완전 탐색 알고리즘 (Brute-Force Algorithm) 한계
✔︎ 문제의 복잡도에 매우 민감
✔︎ 문제가 복잡할 수록 기하급수적으로 많은 자원 필요 → 비효율적
✔︎ 문제 규모가 현재 자원을 벗어나는 경우, 더 효율적인 알고리즘 사용
☞ 완전 탐색 알고리즘 (Brute-Force Algorithm) 사용 예시
✔︎ 순차 검색 알고리즘(Sequential Search)
: 배열 안에 특정 값이 존재하는지 검색할 때 인덱스 0부터 마지막 인덱스까지 차례대로 검색
✔︎ 문열 매칭 알고리즘(Brute-Force String Matching)
: 길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지를 검색
✔︎ 선택 정렬 알고리즘(Selection Sort)
: 전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소(오름차순 or 내림차순)를 교환
✔︎ 버블 정렬 알고리즘(Bubble Sort)
✔︎ Tree 자료 구조의 완전 탐색 알고리즘(BFS, DFS)
✔︎ 동적 프로그래밍(Dynamic Programming)
- 탐색 알고리즘 - 이진 탐색 알고리즘 (Binary Search Algorithm)
⦿ 학습내용
☞ 탐색 알고리즘 종류
✔︎ Linear Search Algorithm(선형 탐색 알고리즘)
✔︎ Binary Search Algorithm(이진 탐색 알고리즘)
✔︎ Hash Search Algorithm(해시 탐색 알고리즘)
☞ Binary Search Algorithm
✔︎ 데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복기법으로 특정한 값을 찾아내는 알고리즘
☞ Binary Search Algorithm 사용할 경우
✔︎ 정렬된 배열에서 요소값을 보다 효율적으로 검색할 때
✔︎ 정렬된 데이터 양이 많을 때
☞ Binary Search Algorithm 특징
✔︎ 시간복잡도 O(log n), 빠른 편이지만 항상 효율 좋은 건 ❌
✔︎ 데이터 양 적고, 앞쪽에 위치한 데이터는 Linear Search Algorithm(앞에서부터 비교)이 빠를 때 존재
☞ Binary Search Algorithm 한계
✔︎ 배열에만 구현
✔︎ 정렬되어 있어야만 구현
◉ 느낀 점
☞ 알고리즘 문제를 Greedy, Implementation 등 여러 가지 방법으로 나누어 각자에 맞는 자료구조를 적용시켜 문제를 푸는 연습이 필요하다 느꼈다. 코드를 작성할 때 쉽게 '성능'이라 말하는 게 시간복잡도에 따라 코드를 구성시켜야 하며, 정형적으로 정해진 몇 가지 방식이 있는 걸 알았다. 오늘 배운 내용들은 단지 이론 학습에서 끝날 것이 아니라 실제로 문제에 적용시키는 것이 중요한 것 같다. 내일 있을 문제 풀이 시간에 해당 문제들에 부딪혀보며 알고리즘 사고를 기르는 연습을 할 것이다.
◉ 내일의 키워드
・ Greedy Algorithm, Implementation 문제 풀이