[Do it! 알고리즘 코딩 테스트 자바] 2주차. 정렬과 탐색

이번 주차는 지난주부터 나왔던 기본 정렬과 탐색 알고리즘에 대해 공부하는 주차다.

주요 알고리즘은

• 삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬
• DFS, BFS
• 백트래킹
• 이진 탐색

 

[6일차]

 

삽입 정렬

: 선택된 데이터를 현재 정렬된 데이터 범위 내에서 적절 위치에 삽입하는 것

평균 시간 복잡도 : O(N^2)

- 과정 

1. 현재 인덱스의 데이터 값 선택
2. 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치 탐색 → O(N) 소요 
3. 삽입 위치부터 인덱스에 있는 위치까지 shift 연산 수행
4. 삽입 위치에 현재 선택한 데이터 삽입 후 인덱스++ 연산
5. 선택할 데이터가 없을 때까지 반복  → O(N) 소요

예제문제

- 백준 11399번 : ATM 인출 시간 계산하기 (실버3)

 

퀵 정렬

: 기준값(pivot)을 선정하여 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬

평균 시간 복잡도 : O(nlogn)

 

- 과정

1. 데이터 분할하는  pivot 설정
2. pivot 기준 아래 과정 거쳐 데이터를 2개의 집합으로 분리
   1) start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동
   2) end가 가리키는 데이터가 pivot 데이터보다 크면 end를 왼쪽으로 1칸 이동
   3) start 데이터가 pivot 데이터보다 크고, end 데이터가 pivot 데이터보다 작으면, start,end 데이터를 스왑 후 start는 오른쪽 end는 왼쪽으로 1칸씩 이동
   4) start와 end가 만날 때까지 반복
   5) 둘이 만났을 때 해당 지점 데이터와 pivot 데이터를 비교해서 pivot이 크면 해당 지점 오른쪽, 작으면 왼쪽에 pivot 삽입
3. 분리 집합에서 다시 pivot 선정
4. 반복

예제문제

- 백준 11004번 : K번째 수 구하기 (실버5)

---

[7일차]

병합 정렬

: 분할 정복 방식 사용하여 데이터 분할하고 분할한 것들을 다시 정렬하면서 합치는 알고리

평균 시간 복잡도 : O(nlogn)

 

- 과정

1. 8개의 숫자를 기준으로 각각의 8개 그룹으로 나눈다.
2. 2개씩 그룹을 합치며 오름차순으로 정렬
3. 이어서 2개씩 그룹 합치며 오름차순 정렬
4. 반복하여 최종 원래 크기의 배열로 합쳐질 때까지 진행

병합 정렬의 원리는 꼭 숙지할 것.

*투 포인터 개념을 사용해서 왼쪽, 오른쪽 그룹 병합

 

예제문제

- 백준 2751번 : 수 정렬하기 2 (실버5)

- 백준 1517번 : 버블 정렬 프로그램 2 (플래티넘)

 

기수 정렬

: 값을 비교하지 않는 정렬로, 값을 놓고 비교할 자릿수를 정한 후 해당 자릿수만 비교 

시간 복잡도 : O(KN) K는 데이터의 자릿수

 

기수 정렬은 10개의 큐를 이용한다. 각 큐는 자릿수를 대표함

 

- 과정

1. 일의 자릿수 기준으로 배열 원소를 큐에 집어 넣는다. (0~9)
2. 그 후 0번째 큐부터 9번째 큐까지 pop 진행
3. 십의 자릿수 기준으로 같은 과정 
4. 마지막 자릿수 기준으로 정렬할 때까지 앞 과정 반복

기수 정렬은 시간 복잡도가 가장 짧은 정렬로, 정렬해야 하는 데이터의 개수가 많으면 기수 정렬 알고리즘을 활용

 

예제문제

- 백준 10989번 : 수 정렬하기 3 (실버 5)

---

[8일차]

깊이 우선 탐색(DFS : Depth First Search)

: 그래프 완전 탐색 기법 중 하나로 그래프 시작 노드에서 출발해 한 쪽 탐색 분기를 정해 최대 깊이까지 탐색 마친 후 다른 분기로 이동하여 다시 탐색하는 알고리즘

 

시간 복잡도 O(V + E) V : 노드 수, E : 엣지 수

 

DFS는 재귀 함수를 이용하여 구현하기 때문에 스택 오버플로우에 유의해야 함.

 

*핵심

DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 방문한 노드를 체크할 배열 필요.
DFS는 후입선출 특성을 가지므로 스택을 사용하여 구현함.

 

예제문제

- 백준 11724번 : 연결 요소의 개수 구하기 (실버 5)

- 백준 2023번 : 신기한 소수 찾기 (골드 5)

- 백준 13023번 : 친구 관계 파악하기 (골드 5)

 

백트래킹(BackTracking)

: 문제를 해결할 수 있는 모든 경로를 탐색하며 선택 경로가 유효하지 않거나 해를 찾지 못하면 이전 단계로 돌아가 다른 경로 시도

시간 복잡도 : O(N^d) d : 탐색 깊이

백트래킹은 재귀 함수 형태로 구현하며, *가지치기를 통해 유효하지 않은 경로를 조기에 배제하여 성능을 높일 수 있다.

 

- 과정

1. 가능한 선택지 탐색하기 : 가능한 선택지 모두 탐색
2. 유효성 검사 및 가지치기 : 각 선택지가 조건 만족하는지 검사
3. 해답 도출 : 해답 찾으면 기록, 필요에 따라 다른 경로도 계속 탐색

예제문제

- 백준 15649번 : N과 M (실버 3)

- 백준 9663번 : N-Queen 배치하기 (골드 4)

- 백준 17136번 : 색종이 붙이기 (골드 2)

---

[9일차]

너비 우선 탐색(BFS : Breadth First Search)

: 그래프 완전 탐색 기법 중 하나로 그래프 시작 노드에서 출발해 시작 노드 기준 가까운 노드를 먼저 방문하며 탐색하는 알고리즘

시간 복잡도 : O(V + E) V : 노드 수, E : 엣지 수

 

BFS는 선입선출 방식으로 탐색하므로 큐를 이용하여 구현

*목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장함

 

예제문제

- 백준 1260번 : DFS와 BFS 프로그램 (실버 2)

- 백준 2178번 : 미로 탐색하기 (실버 1)

- 백준 1167번 : 트리의 지름 구하기 (골드 3)

---

[10일차]

이진 탐색(Binary Search)

: 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터 크기를 절반씩 줄이면서 대상을 찾음

 

시간 복잡도 : O(logN)

*정렬 데이터에서 원하는 데이터 탐색 시 사용하는 가장 일반적인 알고리즘

 

- 과정

1. 현재 데이터셋의 중앙값 선택
2. 중앙값 > 타깃 데이터일 때 중앙값 기준 왼쪽 데이터셋을 선택
3. 중앙값 < 타깃 데이터일 때 중앙값 기준 오른쪽 데이터셋 선택
4. 위 과정 반복하다가 중앙값 == 타깃 데이터일 때 탐색 종료

예제문제 

- 백준 1920번 : 원하는 정수 찾기 (실버 4)

- 백준 2343번 : 블루레이 만들기 (실버 1)

- 백준 1300번 : 배열에서 K번째 수 찾기 (골드 2)

 

---

 

2주차 내용 요약

1. 정렬 알고리즘 : 삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬
2. DFS와 BFS : 깊이 우선 방식과 너비 우선 방식 차이 및 자료구조 차이
3. 백트래킹 : 가지치기로 성능 향상 및 완전 탐색 방식
4. 이진 탐색 : 정렬 데이터 탐색 알고리즘 → O(logN)으로 성능 우수

 

주간 회고록

• 이번 주는 자격증 시험 때문에 거의 공부를 못했다 ㅠ 다음주까지는 일정이 바빠서 개념 위주로 해야할 듯하다!
• 4주차 부터는 문제 풀이에 좀 시간 비중을 많이 가져가야겠다.