왜?
코테 준비하면서
자료구조, 시간복잡도, 정렬에 사전지식이 없으면, 내가 아무리 생각해봐도 짜낼수없는 답안들이있었다. 수준차이가 느껴진다
따라서 나도 그런 답안을 작성하고 더 나은 코드를 짜기위해, 코테를 중심으로 공부하면서 30분동안 안풀리면, 답안을 보고 내가 자연스레 작성할수있을만큼, 그 문제와 관련된 자료구조, 시간복잡도, 정렬을 공부해야되겠다란 생각이들었다.
시간 복잡도
문제를 해결하는 데 걸리는 시간과 입력의 함의 관계.
Big O표기법을 사용하고 이는 이전에 읽었던 코테 책에 기반한다.
알고리즘에서 반복문을 기준으로 주어진 수행시간 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법이다.(앞에상수도빼버림)
| 시간 복잡도 | 설명 |
|---|---|
| O(1) | 상수 형태. n의 값에 상관없이 일정한 양의 계산만 한다. |
| O(logn) | 로그 형태 |
| O(n) | 선형 |
| O(nlogn) | 선형로그 형태 |
| O(n2),O(n3),⋯ | 다차 형태 |
| O(2n) | 지수 형태 |
| O(n!) | 팩토리얼 형태 |
위로갈수록 시간 복잡도가 낮고 빠르다.
자료구조(특히 중요)
모두가 강조하는것
자료구조란, 데이터 사이의 관계를 반영한 저장구조 및 그 조작 방법을 뜻한다
프로그램을 실행하면 CPU에서 메모리로 데이터를 이동하여 처리하는데, 이때 메모리를 효율적으로 사용하기 위해 데이터에 맞는 특성의 자료구조를 사용해야한다.
이중에
- 선형 자료 구조: 한 종류의 데이터가 선처럼 길게 나열된 자료구조
- 비선형 자료구조: 선형 자료구조가 아닌 모든 자료구조 i번째 값을 탐색한 뒤의 i+1이 정해지지 않은 구조
큐
큐의 구조는 선입선출이다(은행번호표생각하자)
반대로 스택은 후입선출(아래가 막힌 상자 생각하자)
큐는 처음 위치와 마지막의 위치만 기억하면 모든게 쉽게 풀린다. 이 위치들을 큐(Queue)에서는 front, rear라고 하죠.
- Enqueue : 큐 맨 뒤에 어떠한 요소를 추가
- Dequeue : 큐 맨 앞쪽의 요소를 삭제
- Peek : front에 위치한 데이터를 읽음, 다음 서비스를 받을 손님이 누구인지 확인
- front : 큐의 맨 앞의 위치(인덱스), 다음 서비스를 받을 손님의 번호
- rear : 큐의 맨 뒤의 위치(인덱스), 마지막에 온 손님의 번호
정렬(???)
- 버블 정렬 - 가장 쉽지만, 시간 복잡도가 높아 효율적이진 않다.
- 선택 정렬 - 버블 정렬과 알고리즘이 유사하다. 가장 큰 수를 찾아 배열의 마지막 위치와 교환한다.
- 삽입 정렬 - 인덱스를 설정하여 현재 위치의 값을 아래쪽으로 순회하며 알맞은 곳에 넣어준다.
- 병합 정렬 - 정렬한 리스트를 반으로 쪼개며 좌우 리스트를 분할해 정렬 후 병합한다. 가장 많이 쓰이는 정렬 중 하나이다.
- 힙 정렬 - 힙이라는 자료구조를 통해 내림차순으로 숫자를 넣은 후, 역순으로 꺼내어 정렬한다.
- 퀵 정렬 - pivot 기준으로 좌측과 우측으로 작은 값과 큰 값을 재배치하고 분할하여 정렬한다.