목록전체 글 (114)
suyeonme
플로이드 와샬 알고리즘(Floyd Warshall Algorithm)이란? 음수 사이클이 없는 그래프에서 모든 정점에서 다른 모든 정점으로의 최단거리를 구하는 알고리즘으로, 거쳐가는(경유) 정점을 기준으로 거쳐가는 경로가 기존의 경로보다 더 효율적인지 판단하여 최단 거리를 구한다. 정점의 개수만큼 3중 반복문을 수행하기때문에 O(V^3)만큼의 시간 복잡도를 갖는다. 동적 프로그래밍 기법을 사용한다. 음수 사이클이 존재하지 않으면 음의 가중치를 가질 수 있다. (≠ 다익스트라 알고리즘) 음수 사이클 사이클의 모든 경로의 합이 음수가 되는 사이클이다. 1 --> 2 --> 3 --> 1의 경우, (1 -3 -2) = -4 이므로 음수 사이클이 존재한다. 구현 순서 인접 행렬을 생성하고 간선의 정보를 저장한다..
우선순위 큐(Priority Queue)란? 큐의 구조를 따르지만(FIFO, First In First Out) 우선 순위를 결정하고 높은 우선순위를 가진 요소를 먼저 꺼내서 처리하는 자료구조이다. 우선순위큐는 내부적으로 힙(Heap)으로 구성되어 이진트리의 구조로 이루어져있다. 따라서 O(N log N)의 시간복잡도를 가진다. Heap이란? Heap은 완전 이진트리로 구현되었으며 우선순위 큐를 위한 자료구조이다. 부모 노드의 값은 자식 노드의 값보다 크거나(Max Heap) 작아야(Min Heap)한다. 이러한 구조를 이용하여 최댓값과 최솟값을 빠르게 찾아낼 수 있다. 힙은 배열로 구현된다. 편의상 0번 인덱스는 사용하지 않는다. 왼쪽, 오른쪽 노드의 위치가 대소 관계를 반영하지 않는다. 즉 왼쪽 노..
다익스트라 알고리즘(Dijkstra Algorithm)이란? 그리디 알고리즘/다이나믹 프로그래밍을 이용한 대표적인 그래프의 최단 경로(Shortest Path)를 구하는 알고리즘이다. 다익스트라 알고리즘은 음의 가중치가 없는 그래프의 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구한다. 다익스트라 알고리즘은 하나의 최단 거리를 구할 때 이전에 구했던 최단 거리 정보를 그대로 사용한다. 최단 거리는 여러개의 최단거리로 이루어져있다고 볼 수 있다. 따라서 다익스트라 알고리즘은 다이나믹 프로그래밍 기법을 사용한다. * 인공 위성 GPS에 가장 많이 사용된다. 그래프의 최단 경로를 구하는 알고리즘 비교 알고리즘 특징 BFS 간선의 가중치가 모두 같은 그래프의 경우 다익스트라 알고리즘(Dijkstra A..
크루스칼 알고리즘(Kruskal Algorithm)이란? 최소 비용으로 모든 노드를 연결하기 위해서 사용하는 알고리즘으로 대표적인 최소 신장 트리(MST, Minimum Spanning Tree)를 만드는 대표적인 알고리즘이다. 가장 적은 비용(weight)을 탐욕적(Greedy Algorithm)으로 확인하여 가장 적은 비용으로 사이클이 발생하지 않게 모든 노드를 연결한다. 시간복잡도는 O(E log E)이다. 간선을 가중치순으로 정렬하므로 E log E만큼의 시간이 소요된다. (=퀵정렬의 시간 복잡도) 반복문에서 V-1만큼의 시간이 소요된다. 최소 신장 트리(MST, Minimum Spanning Tree)란? 신장 트리(Spanning Tree): 그래프의 모든 정점을 연결하고 사이클이 없는 그래프..
합집합 찾기(Union Find) 알고리즘이란? 대표적인 그래프 알고리즘으로, 여러개의 노드가 존재하는 경우 두 개의 노드를 선택하여 선택된 노드가 서로 같은 그래프에 속하는지 확인하는 알고리즘이다. 서로소 집합(Disjoint-Set) 알고리즘이라고도 불리운다. 크루스칼 알고리즘(Kruskal Algorithm)등 고급 그래프 알고리즘에 사용된다. 사이클(Cycle)이 있는지 확인하는 문제 구현 방법 노드의 부모가 자기 자신이 되도록 초기화한다. 두개의 노드를 연결한다. 이 때 더 작은 노드가 부모가 되도록 합친다. -- unionFind 재귀를 사용하여 두개의 노드가 같은 그래프에 속해있는지 확인한다. -- findParent 알고리즘 구현 // 부모노드를 찾는다. const getParent = (..
태그(Tag)란? 태그란 커밋을 참조하기 쉽도록 이름을 붙이는 것으로, 즉 커밋을 태깅(tagging)하는 것이다. 주로 배포 브랜치(release branch)에서 서비스의 버전을 지정할 때 사용한다. 서비스의 버전이 1.0이라면 서비스 1.0을 릴리즈할 때 태깅을 한다. 그 이후 신규 기능은 커밋으로 관리를 하다가 서비스 1.1을 릴리즈할 때의 커밋에 태깅을 할 수 있다. 이런식으로 배포 브랜치를에 태그를 달아서 서비스의 버전을 명시하거나 문제가 생겼을 때 해당 부분을 롤백(rollback)하는등의 행위를 할 수 있다. 태그의 종류 Lightweight Tag: 이름만 붙일 수 있는 태그(커밋번호가 곧 태그)로, 임시로 태그를 생성하거나 메타 데이터를 제공하고 싶지 않은 경우 사용한다. Annotat..
Servlet이란? 클라이언트의 요청(request)을 처리하고 응답(response)을 반환하는 Servlet 클래스를 따라는 자바 프로그램이다. Servlet 특징 HttpServletRequest로 HTTP 요청을 쉽게 다룰 수 있다. (query string, 메세지 바디 조회등) HttpServletResponse로 HTTP 응답을 쉽게 다룰 수 있다. (status code, content-type, cookie, redirect등) 개발자는 서블릿을 사용하여 HTTP를 쉽게 핸들링할 수 있다. Servlet 예시 코드 @WebServlet(name = "requestParamServlet", urlPatterns = "/request-param") public class RequestServ..
문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000) 출력 상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정..