의사코드
프로그래밍 언어로 코드를 작성하기 전에 우리가 쓰는 일상 언어로 프로그램이 작동하는 논리를 먼저 작성
장점
- 시간 단축
- 디버깅 용이
- 프로그래밍 언어를 모르는 사람과도 소통이 가능해진다
쓰는 방법
- 다른 사람도 이해할 수 있는 자연어
- 자연어와 프로그램 언어의 조합
Time Complexity
시간 복잡도라고 한다. 알고리즘 문제를 풀게 될 때 효율적인 방법을 찾는 것은 매우 중요하다.
- O(1)
-> 계산하여 값이 바로 나올 때 - O(log n)
-> 2씩 나눠가며 중간값 찾아 계산할 때 - O(n)
-> for문 한번 돌려서 값이 나올 때 - O(n^2)
-> 2중 for문 돌릴 때
데이터 크기에 따른 시간 복잡도
| 데이터 크기 제한 | 예상 time complexity |
|---|---|
| n<=1,000,000 | O(n) or O(log n) |
| n<= 10,000 | O(n^2) |
| n<=500 | O(n^3) |
Greedy Algorithm
당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.
- 선택 절차 : 현재 상태에서 최적의 해답을 선택한다
- 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다
- 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 그렇지 않다면 위의 과정을 반복한다.
Brute Force Algorithm
이는 무차별 대입 방법을 나타내는 알고리즘이다. 순수한 컴퓨팅 성능에 의존해 모든 가능성을 시도 하여 문제를 해결하는 방식이다.
-> 문제가 복잡할수록 기하급수적으로 많은 자원을 필요로 하는 비효율적인 알고리즘
- 순차 검색 알고리즘
- 배열 안에 특정 값이 존재하는지 0번 인덱스부터 차례대로 검색
- 문열 매칭 알고리즘
- 선택 정렬 알고리즘
- 전체 배열을 검색해 컬렉션이 완전히 정렬될 때까지 요소를 교환하는 정렬 알고리즘
Binary Search Algorithm
데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복기법으로 특정한 값을 찾아내는 것을 이진 탐색 알고리즘이라고 한다.
- 배열의 가장 중간 인덱스 지정
- 찾는 값이 그 이상인지 이하인지 확인
- 값이 있는 부분과 값이 없는 부분으로 분리
- 값이 있는 부분에서 다시 1단계부터 반복
-> 시간복잡도 : O(log n)
한계 : 배열에만 구현할 수 있다, 정렬되어 있어야만 구현할 수 있다.
