Data(자료)
참고 또는 분석을 위해 수집된 사실과 통계.
현실 세계로부터 수집되는 값 또는 이들의 집합이며 가공되기 전의 상태.
데이터를 가공하고 해석한 후의 상태를 정보(Information)이라고 한다.
자료구조(Data Structure)
컴퓨터 메모리상에서 데이터를 표현하건 저장하는 방법이다.
효과적으로 설계된 자료구조는 프로그램 실행시간을 단축하며 메모리 용량을 최소한으로 사용한다.
1. 단순 구조 (기본 자료형 + 사용자 정의 자료형)
1-1. 2진수
1-2. 정수, 실수
1-3. 문자, 문자열
2. 선형 구조
2-1. 리스트(배열)
2-2. 연결 리스트
- 단순 연결 리스트
- 이중 연결 리스트
- 원형 연결 리스트
2-3. 데크
2-4. 스택
2-5. 큐
3. 비선형 구조
3-1. 트리
- 일반 트리
- 이진 트리
3-2. 그래프
- 방향 그래프
- 무방향 그래프
4. 파일 구조
4-1. 순차 파일
4-2. 색인 파일
4-3. 직접 파일
알고리즘 (Algorithm)
저장된 데이터를 이용하여 문제를 해결하기 위한 절차나 방법
시간 복잡도 & 공간 복잡도(메모리)
효과적인 알고리즘을 얻기 위해 알고리즘의 성능을 분석하고 평가할 수 있어야 한다.
시간 복잡도(Time Complexity) : 알고리즘의 수행 시간을 분석한 결과, 알고리즘이 시작되어 완료되는 데까지 걸리는 시간 but 실제 실행 시간은 하드웨어 성능 혹은 프로그래밍 언어에 따라 값이 달라지므로 고려하지 않는다. 즉, 알고리즘에서의 시간 복잡도란 명령어의 실행 횟수를 뜻한다.
공간 복잡도(Space Complexity) : 메모리 사용량을 분석한 결과
Big-O 표기법
알고리즘의 시간복잡도와 공간복잡도를 표현하는 대표적인 방법에는 Big-O 표기법이 있다.
이 표기법은 알고리즘 실행에 있어 최악의 경우를 나타낸다.
즉, 시간 또는 공간의 상한선을 두는 것이다.
예를 들어 3n^2 + 20n + 100 이라는 시간복잡도 함수가 있으면 입력값 n이 증가할수록 차수가 가장 큰 항이 결과값에 가장 큰 영향을
미치며, 다른 항들은 상대적으로 무신된다. 최고 차항의 상수 계수 3 또한 무시된다.
따라서, Big-O 표기법에서는 영향력이 없는 항과 상수 계수를 제거하고 가장 영향력이 큰 항으로만 시간복잡도를 표현한다.
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) : 오른쪽으로 갈수록 비효율적인 순서
자료구조 연산별 평균 시간복잡도
| 자료구조 | 접근 | 검색 | 입력 | 삭제 |
| 배열 리스트 | O(1) | O(n) | O(n) | O(n) |
| 단일 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 스택 | O(n) | O(n) | O(1) | O(1) |
| 큐 | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블 | 불가 | O(1) | O(1) | O(1) |
| 이진 트리 | O(log n) | O(log n) | O(log n) | O(log n) |
그래서 알고리즘 어떻게 공부하는건데?
기본적인 개념을 알았으니 공부하는 방법에 대해 말해보겠습니다. 위 글을 읽어도 어떻게 공부해야하는지 감이 안 잡히실텐데요
제 기준 공부 순서는
- 자신이 사용하는 언어로 자료구조들 구현해보기 (코딩테스트에서 제공이 안 될수있으므로 암기 해주시면 좋음)
- 유튜브나 검색을 통해 알고리즘 종류별로 공부 후 개념 파악 후 코드를 따라서 처본 후 확실하게 이해하기
- 문제 풀이를 통한 숙달과 재암기 및 응용
2번까지 공부하셨으면 문제에 대해 궁금하실 것 같은데 가장 기본적으로 백준을 통해 접근하시는게 좋을 것 같아 유형별로
소개해드리겠습니다.
| 문제 유형 | 백준 문제 번호 |
| 입출력 | 2557, 1000, 2558, 10950, 10951, 10952, 10953, 11021, 11022, 11718, 11719, 11720, 11721, 2741, 2742, 2739, 1924, 8393, 10818, 2438, 2439, 2440, 2441, 2442, 2445, 2522, 2446, 10991, 10992 |
| 정렬 | 2751, 11650, 11651, 10814, 10825, 10989, 11652, 11004 |
| 스택 | 10828, 9012, 1079 |
| 큐 | 10845 |
| 데크 | 10866 |
| 문자열 처리 | 10808, 10809, 10820, 2743, 11655, 10824, 11656 |
| 기타 자료구조 | 1406, 1158, 1168 |
| 기초 수학 | 10430, 2609, 1934, 1850, 9613, 11005, 2745, 1373, 1212, 2089, 11576, 1978, 1929, 11653, 10872, 1676, 2004, 6588 |
| 그래프 | 1260, 11724, 1707, 10451, 2331, 9466, 2667, 4963, 7576, 2178, 2146, 1991, 11725, 1167, 196 |
| 이분탐색/삼분탐색 | 1654, 2805, 2110, 10815, 10816, 11662 |
| 분할정복 | 11728, 1780, 11729, 1992, 2447, 2448, 1517, 2261 |
| 완전탐색 | 1476, 1107, 1451, 9095, 10819, 10971, 1697, 1963, 9019, 1525, 2251, 2186, 3108, 5014, 1759, 2580, 1987, 6603, 1182, 2003, 1806, 1644, 1261, 1208, 7453, 2632, 2143 |
| 그리디 | 11047, 2875, 10610, 1783, 1931, 11399, 2873, 1744 |
| DP | 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052 |
주의 사항으론 문제 해결 시간을 자기만의 기준을 세워서 (약 30분 ~ 1시간) 그 시간안에 풀지 못할 시 단계적으로 힌트를 보고
풀어보며 그래도 안 될시 답을 보며 재학습을 하는게 좋습니다.
백준 알고리즘을 다 푸셔서 기본 토대가 마련되셨으면 프로그래머스, 리트코드, 코드포스 등을 통해 더 높은 난이도의 알고리즘을 통해
연습하시면 될 것 같습니다