전체 글

[필수 알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm) 이해

다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘은 음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘을 말한다. 다익스트라 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만, 더 일반적인 변형은 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것으로도 사용한다. 다익스트라 알고리즘은 그리디 알고리즘이자 다이나믹 프로그래밍 기법을 사용한 알고리즘이라고 볼 수 있다. 그리디 알고리즘과 다이나믹 프로그래밍 기법은 아래의 글에 포스팅되어있다. 그리디 알고리즘 https://cobi-98.tistory.com/44 [필수 알고리즘] 그리..

[자료구조] Java 우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue) Priority Queue란 우선순위 큐로써 일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이며, 힙(Heap)이라고도 부른다. 일반적인 큐의 구조 FIFO (First In First Out)을 가진다. 우선순위를 먼저 결정하고, 우선순위가 높은 데이터가 먼저 나가는 구조이다. Heap을 이용하여 구현하는 것이 일반적이다. 데이터 추출 시, 루트 노드를 얻어 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입 후 아래 노드로 내려가면서 정렬하는 방식으로 진행된다. 최대 힙 = 최대 값이 우선..

[필수 알고리즘] 그리디 알고리즘(Greedy Algorithm) 이해

그리디 알고리즘 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란, "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다. 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 루트 노드부터 시작하여 거쳐 가는 노드 값의 최대로 구한다면, 값은 5+7+9 = 21로 다음과 같지만 거쳐가는 노드의 경우에서 가장 큰 값(최적의 값만) 구한다면, 값은 5+10+4 = 19 가 된다. 이처럼, 그리디 알고리즘은 최적의 값을 도출해내지 못하지만 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용할 수 있다. 그리디 알고리즘 기법 활용..

[필수 알고리즘] 이분 탐색(Binary Search) 이해

이분/이진 탐색 Binary Search 정렬 등과 함께 가장 기초인 알고리즘으로 꼽히는 문제. 이진 탐색은 오름차순으로 정렬된 리스트에서 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있다. 이진 탐색 기법 활용 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 사용한다. 이때, 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 배열의 중간 값을 가져온다. 중간 값과 검색 값을 비교한다. 중간 값이 검색 값과 같다면 종료한다. (..

[필수 알고리즘] 동적계획법 DP (Dynamic Programming) 이해

동적계획법 DP (Dynamic Programming) 동적 계획법은 프로그래밍 대회 문제에 자주 출현하는 알고리즘 기법 중 하나이며, 프로그램이 실행되는 도중, 실행에 필요한 메모리를 기억하여 할당하는 기법을 의미한다. : 큰 문제를 작은 문제로 나눈 뒤, 기억하여 푸는 기법 공간복잡도를 늘리는 대신 시간복잡도는 줄이는 방식이다. 중복되는 부분 문제 피보나치 수열을 예시로 코딩하려고 한다. 점화식이 F(n) = F(n-1) + F(n-2)이기 때문에 단순 재귀 함수로 구현된다. public class fibonacciEx{ static int fibonacci(int n){ if(n == 0) return 0; if(n == 1) return 1; return fibonacci(n - 2) + fibo..