작업 스케줄링 (Job Scheduling) 문제 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제 시작시간, 종료시간, 작업 길이에 대한 그리디 알고리즘 빠른 시작시간 작업 우선 (Earliest start time first) 배정 빠른 종료시간 작업 우선 (Earliest finish time first) 배정 짧은 작업 우선 (Shortest job first) 배정 긴 작업 우선 (Longest job first) 배정 첫 번째 알고리즘을 제외하고 나머지 3가지는 항상 최적해를 찾지 못함 Pseudo code JobScheduling(t) Input: n개의 작업 t1, t2, ⋯, tn Output: 각 기계에 배정된 작업 순서 1. 시작시간의 오름차순으로 ..
Software
집합 커버 (Set Cover) 문제 n 개의 원소를 가진 집합 U U의 부분집합들을 원소로 하는 집합 F F의 원소들 중 선택하여 합집합이 U랑 같아지는 원소의 최소 개수 신도시 학교 배치 문제 아래 두 조건을 만족하는 학교 위치 선정 학교는 마을에 위치해야 함 등교 거리는 걸어서 15분 이내이어야 함 학교의 위치 최소 예시 문제 도식화 1. U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 2. F = {S1, S2, S3, S4, S5, S6, S7, S8, S9, S10} 3. S1 = {1, 2, 3, 8} 4. S2 = {1, 2, 3, 4, 8} 5. S3 = {1, 2, 3, 4} 6. S4 = {2, 3, 4, 5, 7, 8} 7. S5 = {4, 5, 6, 7} 8. S6..
배낭 (Knapsack) 문제 n개의 각각 무게와 가치를 지닌 물건을 최대의 가치를 갖도록 배낭에 넣는 문제 부분 배낭 (Fractional Knapsack) 문제 물건을 나눠서 담는 것을 허용 그리디 사용 가능 0-1 배낭 문제 물건을 통째로 배낭에 넣어야 함 동적 계획 알고리즘, 백트래킹 기법, 분기 한정 기법으로 해결 부분 배낭 문제 그리디 알고리즘 Pseudo code FractionalKnapsack(n, weightAndPriceList, C) Input 물건 n개 각 물건의 무게와 가치 배낭의 용량 C Output 배낭에 담은 물건 리스트 L 배낭에 담은 물건 가치의 합 v 1. 각 물건에 대해 단위 무게 당 가치를 계산 2. 물건들을 단위 무게 당 가치를 기준으로 내림차순으로 정렬하고, 정..
너비 우선 탐색 (Breadth First Search) 루트 노드에서 시작해서 인접한 노드를 먼저 탐하는 방법 Example private class BFSExample { private lateinit var visited: BooleanArray private val resultList = mutableListOf() fun solution( nodeSize: Int, edgeSize: Int, edges: Array ) { val sortedEdges = edges.map { it.sorted() }.toTypedArray() // for (i in 1 until sortedEdges.size) { // println("node = $i, child = ${sortedEdges[i]}") // }..
계층화 패턴 (Layered pattern) 하위 모듈들의 그룹으로 나눌 수 있는 구조화된 프로그램에서 사용 각 하위 모듈들은 특정한 수준의 추상화를 제공 n-티어 아키텍쳐 패턴이라고도 불림 계층 프레젠테이션 계층 (Presentation layer) UI 계층 (UI Layer) 어플리케이션 계층 (Application layer) 서비스 계층 (Service Layer) 비즈니스 논리 계층 (Business logic layer) 도메인 계층 (Domain Layer) 4계층시 사용 데이터 접근 계층 (Data access layer) 영속 계층 (Persistence layer) 도메인 기반 설계 (Domain Driven Design, DDD) 계층 Presentation layer Applica..
깊이 우선 탐색 (Depth First Search) 트리나 그래프에서 최대한 깊숙하게 탐색한 이후 가장 최근의 갈림길로 돌아가 다른 노드를 탐 DFS 구현 방법 재귀 호출을 이용한 구현 private fun dfs( edges: Array, node: Int = 1 ) { resultList.add(node) for (next in edges[node]) { if (!visited[next]) { visited[node] = true dfs(edges, next) visited[node] = false } } } 스택을 이용한 구현 private fun dfsUsingStack( edges: Array, node: Int = 1 ) { val deque = ArrayDeque() deque.add(no..
트리 순회 (Tree Traversal) 트리 구조의 모든 노드를 방문하는 방법 트리의 모든 노드를 한 번씩 방문하고 각 노드에 대해 원하는 작업을 수행하는 방법 전위 순회 (Preorder traversal) 현재 노드에 대한 작업을 수행 이후 각 자식 노드를 순서대로 방문하여 작업을 수행 Example fun preOrder(root: TreeNode) { print(root.data) root.left?.let { preOrder(it) } root.right?.let { preOrder(it) } } 중위 순회 (Inorder traversal) 현재 노드에 대한 작업을 수행 이후 각 자식 노드를 순서대로 방문하여 작업을 수행 Example fun inOrder(root: TreeNode) { r..
최단 경로 찾기 (Shortest path problem) 주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제 다익스트라 (Dijkstra) 알고리즘 주어진 출발점에서 시작 출발점으로부터 최단 거리가 확정되지 않은 점들 중에서 출발점으로부터 가장 가까운 점을 추가하고, 그 점의 최단 거리를 확정 Pseudo code ShortestPath(G, s) Input: 가중치 그래프 G = (V, E), |V| = n, |E| = m Output: 출발점 s로부터 (n - 1)개의 점까지 각각 최단 거리를 저장한 배열 D 1. 배열 D를 ∞로 초기화시킨다. 단, D[s] = 0으로 초기화한다. // 배열 D[v]에는 출발점 s로부터 점 v까지의 거리가 저장된다. 2. whi..
프림 최소 신장 트리 (Prim MST) 임의의 점 하나를 선택한 후, (n - 1)개의 선분을 하나씩 추가시켜 트리 Pseudo code PrimMST(G) Input: 가중치 그래프 G = (V, E), |V| = n, |E| = m Output: 최소 신장 트리 T 1. 그래프 G에서 임의의 점 p를 시작점으로 선택하고, D[p] = 0으로 놓는다. // 배열 D[v]는 T에 있는 점 u와 v를 연결하는 선분의 최소 가중치를 저장하기 위한 요소 2. for (점 p가 아닌 각 점 v에 대하여) { // 배열 D의 초기화 3. if (선분 (p, v)가 그래프에 있으면) 4. D[v] = 선분 (p, v)의 가중치 5. else 6. D[v] = ∞ 7. } 8. T = {p} // 초기에 트리 T는..
크러스컬 최소 신장 트리 (Kruskal MST) 가중치가 가장 작은 선분이 사이클을 만들지 않을 때만 그리디하게 선분 추가 Pseudo code KruskalMST(G) Input: 가중치 그래프 G = (V, E), |V| = n, |E| = m Output: 최소 신장 트리 T 1. 가중치의 오름차순으로 선분들을 정렬한다. 정렬된 선분 리스트를 L이라고 하자. 2. T = ∅ // 트리 T를 초기화시킨다. 3. while ( T의 선분 수 < n-1 ) { 4. L에서 가장 작은 가중치를 가진 선분 e를 가져오고, e를 L에서 제거한다. 5. if (선분 e가 T에 추가되어 사이클을 만들지 않으면) 6. e를 T에 추가시킨다. 7. else // e가 T에 추가되어 사이클이 만들어지는 경우 8. e..
