분류 전체보기

계층화 패턴 (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..

최소 신장 트리 (Minimum Spanning Tree) 주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리 (b)는 최소 신장 트리 (c)는 가중치의 합이 (b)보다 큼 (d)는 트리가 주어진 그래프의 모든 노드를 포함하지 않음 Idea 사이클이 없도록 모든 점을 연결 그래프의 점의 수가 n인 경우 신장 트리에 (n - 1)개의 선분이 존재 트리에 선분을 하나 추가할 경우, 반드시 사이클이 형성 관련 알고리즘 크러스컬 (Kruskal) 알고리즘 가중치가 가장 작은 선분이 사이클을 만들지 않을 때만 그리디하게 선분 추가 2024.03.10 - [Algorithm] - [알고리즘] 크러스컬 최소 신장 트리 (Kruskal MST) 프림 (Prim) 알..

동전 거스름돈 (Coin Change) 동전 거스름돈의 최소 동전 수를 찾는 문제 단, 동전 액면 500, 100, 50, 10, 1 Idea 남은 액수를 초과하지 않는 조건하에 가장 큰 액면의 동전을 택함 Pseudo code CoinChange(W) Input: 거스름돈 액수 W Output: 거스름돈 액수에 대한 최소 동전 수 1. change = W n500 = n100 = n50 = n10 = n1 = 0 // n500, n100, n50, n10, n1은 각각의 동전 카운트 2. while ( change ≥ 500 ) change = change-500, n500++ // 500원짜리 동전 수를 1 증가 3. while ( change ≥ 100 ) change = change-100, n1..

최근접 점의 쌍 찾기 (Closest Pair of Points Problem) 2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제 간단한 idea 모든 점에 대하여 각각의 두 점 사이의 거리를 계산하여 가장 가까운 점의 쌍을 찾는다 example 1, 2, 3, 4, 5 총 5개의 점이 주어진 경우 비교해야 할 쌍의 개수 = nC2 = n(n-1)/2 시간 복잡도는 O(n^2) O(n^2)보다 효율적인 분할 정복 이용 n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 점의 쌍을 찾고, 2개의 부분해 중에서 짧은 거리를 가진 점의 쌍을 찾는다 2개의 부분해를 취합할 때 아래와 같이 양쪽을 비교해서 짧은 해라고 답으로 정할 수 없다. 거리가 짧은 해 이내..

선택 문제 (Selection Problem) n 개의 숫자들 중 k 번째로 작은 숫자를 찾는 문제 간단한 idea 최소 숫자를 k번 찾는다 O(kn) 숫자들을 정렬한 후 k번째 숫자를 찾는다 O(nlogn) Idea 이진 탐색 (Binary Search) 정렬된 입력인 경우, 중간에 있는 숫자와 찾고자 하는 숫자를 비교함으로써, 입력을 반으로 나눈 두 부분 중 한 부분만을 검색 선택 문제 입력이 정렬되지 않는 형태, 입력 숫자 중 피봇을 선택하여 분할 Pseudo code Selection(A, left, right, k) Input: A[left] ~ A[right]와 k, 단 1 ≤ k ≤ |A|, |A| = right - left + 1 Output: A[left] ~ A[right]에서 k 번째..