배열

배열이란? 인덱스와 인덱스에 대응되는 데이터로 이루어진 자료구조를 말한다.

vs 리스트

배열하고 가장 유사하면서도 다른 자료구조가 바로 리스트이다.
둘의 차이를 표를통해 알아보자.

	배열	리스트
메모리 저장	연속적	연속적+불연속적
데이터 조회	O(1)	O(N)
데이터 삽입/삭제	O(N)	O(1)

문자열

문자열(String)이란? 문자가 연속적으로 나열된 것을 말한다.

vs 문자

문자(Char)란 정확히 한 글자를 말한다.

• 'hello' -> 문자열
• 'h' -> 문자

반복문

제어문 중 하나로 특정 구간의 코드가 반복적으로 사용될 수 있는 것을 말한다.
Python의 경우 while,for을 활용해 반복을 할 수 있다.

재귀함수

함수를 실행하는 과정에서 자기함수를 재호출하는 함수를 말한다.

재귀함수를 왜 쓰는 걸까?

재귀함수와 비슷한 역할을 할 수 있는 게 바로 반복문이다.
재귀적 사고로 함수를 적절하게 표현한다면 보다 간결한 코드를 작성할 수 있다.

재귀함수 vs 반복문

	재귀함수	반복문
장점1	간결한 코드로 표현할 수 있다.	상대적으로 적은 메모리 사용
장점2	적은 변수로도 표현이 가능하다.	빠른 실행시간
단점1	반복 호출로 메모리 사용이 많다.	상대적으로 긴 코드
단점2	반복호출로 느린 실행시간	상대적으로 많은 변수가 필요하다.

복잡도(BigO,시간,공간)

시간 복잡도: 프로그램이 실행하는데 걸리는 시간
입력 데이터가 n개일 때

• Big(O): 프로그램이 최대로 걸릴 수 있는 시간

공간 복잡도: 프로그램을 실행하는데 차지하는 메모리 소모량

알고리즘에서 시간복잡도 계산

연산 1억($10^8$)번에 보통 1초가 걸린다고 한다.
예시를 통해서 소요시간을 계산해보자.

백준 2805 https://www.acmicpc.net/problem/2805

정리하자면

• 시간제한: 1초
• 메모리 제한: 256 MB
• 입력 데이터 갯수: 1~1,000,000개
• 입력 데이터의 크기: 1,000,000,000

이때 1초면 연산 1억($10^8$)번 이하로 끝내야한다.
만약 이때 탐색 알고리즘이 O($n^2$)이라면
데이터 갯수가 1,000,000개($10^6$개)일 때
연산이 $10^{12}$번을 해야하므로 시간초과가 나게 된다.
그래서 탐색 알고리즘이 최소 O(nlogn)은 되어야한다는 걸 알 수 있다.

O($n^2$) = $10^6\times 10^6 = 10^{12}$번
O(nlogn) => $10^6\times log2^{20}=10^6\times20$번

$10^3=>2^{10}$
$10^6=>2^{20}$

알고리즘에서 공간복잡도 계산

정렬

정해진 순서대로 나열하는 것. 이때 정렬 기준에 따라 다른 결과가 나온다.

정렬 알고리즘

자료구조에 저장된 데이터를 일정한 기준에 따라 순서대로 열거하는 알고리즘
자주 쓰이는 알고리즘으로는 크게 4가지가 있다.

알고리즘	최악 시간복잡도	평균 시간복잡도
삽입 정렬(Insertion Sort)	$O(n^2)$	$\theta(n^2)$
합병 정렬(Merge Sort)	$O(nlogn)$	$\theta(nlong)$
퀵 정렬(Quick Sort)	$O(n^2)$	$\theta(nlogn)$
힙 정렬(Heap Sort)	$O(nlogn)$	$\theta(nlogn)$

여기서 $\theta$(세타)는 평균 시간복잡도를 표현할 때 쓰인다.

완전탐색

완전 탐색이란 Exhaustive search, Brute force, Backtracking라고도 하며
모든 경우의 수를 알아보는 탐색 방법이다.

백트래킹

완전 탐색이랑 백트래킹이 헷갈릴 수 있는데 가장 큰 차이는
백트래킹은 탐색을 시도하고 실패하면 이전 상태로 돌아가 다른 가능성을 시도한다는 점이다.

백트래킹 = 완전탐색+재귀

탐색에서 백트래킹은 모든 경우의 수를 고려하되
더 이상 탐색해도 답이 될 수 없는 경우 이전 상태로 돌아가
다음 경우의 수를 탐색한다. 이 돌아가는 과정에서 재귀가 사용된다.

이분탐색

이분 탐색, 이진 탐색, Binary Search라고 한다.
이분이라는 말에서 알 수 있듯이
정렬되어 있는 리스트에서 탐색 범위를 1/2로 줄여나가는 방식이다.
이분 탐색의 알고리즘의 시간복잡도는 $O(logN)$이 나온다.

분할정복

분할정복(Divide and conquer)이란
그대로 해결할 수 없는 문제를 작은 문제로 분할하여
문제를 해결하는 알고리즘이다.

스택

스택(Stack)은 데이터를 쌓아 올린 형태의 자료구조이다.
마지막에 들어온 데이터가 가장 먼저 나가는 후입선출 구조이다.
Last In First Out = LIFO
데이터의 이동이 마지막 인덱스에서만 일어나는 것이 특징이다.

스택이 유리한 상황은?

큐

큐(Queue)는 입장 대기열 형태의 자료구조이다.
먼저 들어온 데이터가 먼저 나가는 선입선출 구조이다.
First In First Out = FIFO
데이터의 이동이 처음과 끝의 인덱스에서만 일어나는 것이 특징이다.

큐를 언제 쓰는게 좋을까?

우선순위 큐

우선순위 큐(Priority Queue)는 모든 원소가 우선순위를 가진 자료구조이다.
높은 우선순위를 가진 원소가 먼저 처리된다.

두 원소의 우선순위가 같다면?

구현 방식에 따라 달라질 수 있으나
대부분의 우선순위 큐에서는 두 원소가 추가된 순서대로 처리한다.
FIFO 구조로 큐와 같다.

vs 힙

힙(Heap)은 최대값 및 최소값을 찾는 연산을 빠르게 하기 위해서
완전 이진 트리를 활용한 자료구조이다.

	우선순위 큐	힙
우선순위 설정	여러 기준	값의 크기 순

힙은 여러 값중에서 최대값, 최소값을 찾는 자료구조라면
우선순위 큐는 '우선순위'를 가진 원소를 먼저 처리하는 자료구조이다.

힙이 '값이 크냐 작냐'로만 우선순위가 정해진다면
우선순위 큐는 다른 기준으로도 정렬을 할 수 있다.
예를 들어 문자열이면 '사전순','길이순'으로 정렬될 수 있다.

Linked List

Linked List, 연결 리스트는
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로
데이터를 저장하는 자료구조이다.
포인터에는 다음 인덱스의 노드 주소값을 저장한다.

연결리스트 vs 리스트

리스트 = 추상적 자료형
연결리스트 = 리스트를 실제로 구현한 자료구조

vs 배열

	배열	리스트
메모리 저장	연속적	연속적+불연속적
데이터 조회	O(1)	O(N)
데이터 삽입/삭제	O(N)	O(1)

위에도 적혀있던 내용이라 추가적인 설명을 덧붙이지만

데이터 조회시

배열의 경우 데이터를 조회할 때 인덱스+데이터로 저장하기 때문에
바로 조회가 가능하고 시간복잡도는 $O(1)$.
하지만 연결리스트의 경우 원하는 인덱스의 데이터를 찾기 위해서는
포인터를 따라 올라가야하기 때문에 시간복잡도가 $O(N)$가 나온다.

데이터 삽입/삭제

배열의 경우 데이터를 삽입/삭제할 때 인덱스에 맞춰서
나머지 데이터들을 1칸씩 이동해야한다.
그래서 데이터 삽입/삭제 연산의 시간복잡도가 $O(N)$이 나온다.
하지만 연결리스트의 경우 데이터를 삽입/삭제할 때 노드의 연결된 포인터의 값만
변경해주면 되기 때문에 데이터 삽입/삭제 연산의 시간복잡도가 $O(1)$가 나온다.

해시 테이블

해시 테이블(Hash table), 해시 맵(Hash map), 해시 표 라고도 하며
키와 값을 매핑할 수 있는 자료구조이다.
키를 해시함수를 사용하여 해시 코드(Hash Code)로 변환하고
이 해시코드를 기반으로 데이터를 조회,삽입,삭제를 합니다.

• 해시코드: 키를 해시함수에 넣은 결과값
• 버킷: 하나 이상의 키-값 쌍을 저장할 수 있는 공간
• 슬롯: 오직 하나의 키-값 쌍을 저장할 수 있는 공간

버킷

버킷(Bucket)은 해시 테이블에서 하나 이상의 키-값 쌍을 저장할 수 있는 공간을 의미합니다.
해시코드는 보통 버캣 배열의 인덱스로 변환되어, 해당 버킷에 키-값 쌍이 저장됩니다.
만약 해시 충돌이 일어나 체인법으로 해결할 때
하나의 버킷은 여러 개의 키-값 쌍을 저장하는 연결리스트나 다른 형태의 자료구조로
저장할 수 있습니다.

슬롯

슬롯(Slot)은 해시 테이블의 오직 하나의 키-값 쌍을 저장할 수 있는 공간을 의미합니다. 해시 충돌이 일어나 열린 주소법으로 키-값 쌍을 저장할 때는 "버킷=슬롯"의 의미로 쓰일 수 있다. 하지만 체인법으로 해결할 때는 "버킷=여러 슬롯"을 의미하게 됩니다.

해시 테이블을 쓰는 이유는?

원하는 데이터를 빠르게 찾아 조회,삽입,삭제를 하기 위해서다.
키를 해시코드로 변환해 그냥 인덱스를 조회할 때보다 빠르게 데이터를 찾을 수 있다.

어떻게 빠르게 데이터를 처리할 수 있을까?

원하는 키를 조회하고자 할 때 인덱스로 전체 검색을 하는 것보다
키를 해시함수에 넣어 해시코드를 구하고 해시코드를 기반으로 좁혀진 범위에서
검색을 하는 것이 더 빠르기 때문이다.

해시 충돌이란?

해시 충돌(Hash Collision)이란 2개 이상의 키가 동일한 해시함수 결과를 갖는 경우.
즉 2개 이상의 키가 동일한 해시코드를 갖는 경우를 말합니다.

해시 충돌를 해결하려면?

크게 2가지 방법이 있다. 체인법과 열린 주소법이다.

1. 체인법(Chaining): 같은 해시 코드를 갖는 요소들을 연결리스트로 연결해서 해결합니다.
   예를 들어, 키 순서대로
2. 열린 주소법(Open Addressing): 충돌이 발생하면 다른 버킷에 저장합니다.
   저장하는 방식은 크게 3가지가 있다.

• 선형 조사법 (Linear probing)
• 이차 조사법 (Quadratic probing)
• 이중 해싱 (Double hashing, Rehashing)

n의 설정한 이동 칸수?

선형 조사법	$n$칸을 옮겨 다음 버킷을 조사한다.
이차 조사법	$n^2$만큼 건너 뛰어 버킷을 조사하는 방법
이중 해싱	다른 해시 함수를 적용하는 방법