스택, 큐, 정렬, 탐색

스택

- LIFO, DFS

- 삽입(push)과 삭제(pop)이 top에서만 일어남

 

큐

- FIFO, BFS

- 가장 먼저 들어온 데이터는 front, 가장 늦게 들어온 데이터는 back

- 삽입(push)은 back에서, 삭제(pop)는 front에서 일어남

 

버블 정렬

1. 두 인접 데이터의 크기를 비교해 정렬(swap)

2. 개수가 N개 일 때 정렬된 영역 설정을 위해 j < N-1-i

for(int i = 0; i < N-1; i++){
	for(int j = 0; j < N-1-i; j++){
    }
}

 

선택 정렬

1. 최솟값 또는 최댓값을 찾아 가장 앞 데이터와 swap

2. index++, index가 전체 데이터 크기 이상이 되면 종료

 

삽입 정렬

1. 데이터 값을 선택하여, 정렬된 데이터 범위에 삽입될 위치를 탐색

2. 삽입 위치부터 index까지 shift

3. 데이터를 삽입하고 index++, index가 전체 데이터 크기 이상이 되면 종료

 

퀵 정렬

1. pivot을 설정

2. start와 end를 설정하고 pivot과 비교하며 이동

3. start와 nd가 만난 지점의 데이터가 pivot보다 크면 pivot을 좌측에, 작으면 pivot을 우측에 삽입

4. 두 부분으로 분리하여 1~3 과정을 반복하고, 분리 집합이 1개 이하가 될 때 까지 반복

 

병합 정렬

- 나눠진 그룹을 병합하는 과정에서 데이터를 비교하여 병합

 

DFS

- 인접 리스트, 스택(LIFO)

1. 시작 노드를 설정 후 스택에 삽입

2. 스택에서 노드를 꺼낸 후 인접 노드를 다시 스택에 삽입

3. 모든 노드를 탐색할 때까지 반복

 

BFS

- 인접 리스트, 큐(FIFO)

1. 시작 노드를 설정 후 큐에 삽입

2. 큐에서 노드를 꺼낸 후 인접 노드를 다시 큐에 삽입

3. 모든 노드를 탐색할 때까지 반복

 

이진 탐색

1. 중앙값을 설정

2-1. 중앙값>타깃 데이터면 좌측 데이터셋을 선택

2-2. 중앙값<타깃 데이터면 우측 데이터셋을 선택

3. 중앙값==타깃 데이터일 때까지 반복