위상 정렬(Topological Sortin) 위상 정렬이란 순서가 있는 작업(방향이 있는)을 차례로 진행해야 할 때 순서를 결정해 주기 위해 사용하는 알고리즘 사이클이 없는 방향 그래프(DAG; Directed Acyclic Graph)의 모든 노드를 주어진 방향성에 어긋나지 않게 순서를 나열하는 것 Ex) 대학 선수과목, 공장의 작업 순서, 요리 순서, ... 등 사전 지식 진입 차수: 특정 노드로 들어오는 간선의 개수 진출 차수: 특정 노드에서 나가는 간선의 개수 위상 정렬 Queue 구현 위상 정렬 방법(Queue 사용) 진입 차수가 0인 모든 노드를 Queue에 삽입 Queue가 공백 상태가 될 때까지 반복 수행 Queue에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거 (연결된 노..
프림 알고리즘 프림 알고리즘이란? 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식 임의의 정점을 선택하여 시작 어짜피 모두 연결되므로 임의의 정점을 선택해도 된다 그러므로 첫 정점(0번 또는 1번)을 고른다 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택 모든 정점이 선택될 때까지 2번 과정을 반복 서로소인 2개의 집합 정보를 유지 트리 정점: MST를 만들기 위해 선택된 정점들 비트리 정점들: 선택되지 않은 정점들 프림 알고리즘 의사코드 MST-PRIM(G, r) FOR u in G.V u.key ← ∞ u.p ← NULL r.key ← 0 Q ← G.V WHILE Q != 0 Q ← Extract-MIN(Q) FOR v in G.Adj[u]..
이진 탐색 - 자료구조와 알고리즘 탐색 알고리즘 중 하나인 이진 탐색(Binary Search)이란 '정렬된 배열'에서 '특정 값'을 찾는 알고리즘을 의미한다. 이진 검색은 정렬된 배열에서 검색 간격을 반으로 반복적으로 나누어 사용하는 검색 알고리즘으로 정의된다. 이진 검색의 아이디어는 배열이 정렬된 정보를 사용하여 시간 복잡도를 O(로그 N)으로 줄이는 것이다. 이진 탐색 알고리즘의 예시로 아래의 그림을 참고하자. 정렬된 배열에서 23을 찾는 과정이다. 배열의 중앙 인덱스를 찾는다. M = (0 + 9) / 2 = 4 인덱스 4에 위치한 16과 23을 비교한다. 16 < 23 23이 더 크므로 L(5) ~ H(9) 사이에서 다시 탐색을 실시한다. M = (5 + 9) / 2 = 7 인덱스 7에 위치한 ..
오전에는 운동, 오후에는 집안일과 각종 잡무들을 처리하느라 많은 공부를 하지 못하였다. 백준에서 문제를 풀다가 코드가 너무 복잡해지고, 속도 또한 느리게 나오는 문제를 발견했다. 그래서 어떻게 해야할지를 고민하다가 평소에 많은 배움을 얻고 있는 Stranger-Lab님의 블로그에서 카운팅 정렬을 학습했다. 링크는 페이지 하단 참고자료란에 첨부하겠다. 카운팅 정렬(Counting Sort) 카운팅 정렬 사용 이유 시간복잡도가 O(n)으로서 엄청난 성능. 대표적인 정렬 알고리즘(퀵 정렬, 힙 정렬, 합병 정렬 등)의 평균 시간복잡도는 O(nlogn)이다. 정렬 방법 카운팅 정렬은 데이터의 값이 몇 번 나왔는지를 세는 메커니즘 array 배열 counting 배열 array를 순회하면서 해당 값을 index..
9월 30일은 세미나를 보고 정리한 내용만 올리고 오랜만에 한국으로 돌아온 친구, 타지에서 일하는 친구들이 모두 부산에 모여서 친구들을 만났고, 10월 1일은 부모님과 함께 보냈다. 번아웃으로 조금 힘든 날들을 보내고 있었는데 오랜만에 공부를 잠깐 쉬어가면서 사람들을 만나니 다시 에너지를 얻은 기분이다. 역시 공부와 휴식이 조화를 이룰 때 공부도, 휴식도 잘할 수 있는 게 맞다. 오늘은 본가에 다녀와서 짧게나마 알고리즘 문제풀이와 객체지향의 사실과 오해를 읽고 정리했다. TIL-37 시작하겠다. 백준 4949 자바(Java) 균형잡힌 세상 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"..
[백준 2839/자바(Java)] 설탕 배달 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 시간 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 302839 112158 84392 36.699% 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에..
