SeSAC 27일차 / 정렬 알고리즘, 탐색

SeSAC 27일차(2023-08-23)
정렬 알고리즘, 탐색

---

 

기수 정렬

• 기수 정렬(Radix Sort)
  • 낮은 자리 수부터 비교하는 정렬 방법
  • 기(radix)는 특정 진수를 나타내는 숫자들
    • 10진수의 기는 0~9이고 2진수의 기는 0~1
  • 제한적인 범위 내에 있는 숫자에 대해서 각 자릿수 별로 정렬하는 알고리즘
  • 기수 정렬의 장점은 빠르다.

 

탐욕 알고리즘

• 그리디 알고리즘(Greedy Algorithm)
  • 최적화 문제를 해결하는 알고리즘
  • 가능한 해들 중에서 가장 좋은 해를 찾는 문제
  • 부분적인 최적 해를 찾고, 이들을 모아서 문제의 최적 해를 얻는다.
  • 시간 복잡도: O(nlogn)

 

깊이 우선 탐색

• 깊이 우선 탐색(depth-first search, DFS)
  • 탐색 트리에서 해가 존재할 가능성이 존재하는 한 앞으로 계속 전진하여 탐색하는 방법
  • 시간 복잡도: O(b의 m제곱), b는 분기 계수 및 m은 트리의 최대 깊이
  • 공간 복잡도: O(bm)

 

너비 우선 탐색

• 너비 우선 탐색(breadth-first search, BFS)
  • 루트 노드의 모든 자식 노드 들을 탐색한 후에 해가 발견되지 않으면 한 레벨 내려가서 동일한 방법으로 탐색을 계속하는 방법

 

클래스 초기화

• static initializer(클래스 초기화)

private static ArrayList<Integer>[]queue= new ArrayList[10];
// static initializer(클래스 초기화)
static {
    for(int i = 0; i < 10; i++){
queue[i] = new ArrayList();
    }
}

 

미니 프로젝트 답안 풀이

• 내용: 직원 관리 시스템
• Project: EmpProject
• package: com.iyb
• Main-class: ManageService
  • member method: insert(), select(), update(), delete(), selectAll()
• class 1: Employee
  • member field: id, pwd, name, email, phone, jumin (모두 String)

 

오늘의 실습 코드

https://github.com/yubin-im/SeSAC/tree/d12fd680cc819357801f02874f2b6a2d532f7379/20230823