개발공부일지

다이나믹 프로그래밍(동적 계획법, DP; Dynamic Programming)큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정에서, 계산된 결과를 기록하고 재활용하며 문제의 답을 구하는 방식중간 계산 결과를 기록하기 위한 메모리가 필요한 번 계산한 부분을 다시 계산하지 않아 속도가 빠름 다른 알고리즘과의 차이점분할 정복과의 차이분할 정복은 부분 문제가 중복되지 않음DP는 부분 문제가 중복되어 재활용에 사용그리디 알고리즘과의 차이그리디 알고리즘은 순간의 최선을 구하는 방식(근사치)DP는 모든 방법을 확인 후 최적해 구하는 방식 다이나믹 프로그래밍 예시 다이나믹 프로그래밍 방법타뷸레이션(Tabulation)상향식(Bottom-up) 접근 방법작은 하위 문제부터 풀면서 올라감모두 계산하면서 차례대로 진행메모..

최소 신장 트리(Minimum Spanning Tree)MST: Minimum Spanning Tree그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법크루스칼, 프림 크루스칼(Kruskal) 알고리즘 (1/2)간선 중 최소 값을 가진 간선부터 연결사이클 발생 시 다른 간선 선택주로 간선 수가 적을 때 사용O(ElogE)    크루스칼(Kruskal) 알고리즘 (2/2)사이클 발생 체크 방법Union-FindUnion-Find 배열을 사용하여 자기 자신이 어떤 부모 노드를 가리키는지 더 작은 넘버링 쪽으로 업데이트를 해주면서 이미 연결이 되어 있었다는 것을 판별하여 사이클 발생 여부를 체크  크루스칼 알고리즘 구현 코드// 알고리즘 - 최소 신장 트리// 크루스칼 알고리즘import java.util..

백트래킹(Backtracking)모든 경우의 수를 탐색하며 최적해를 구하는 과정에서 유망하지 않은 쪽은 더 이상 구하지 않는 방법돌다리 두드려보고 가는 느낌용어유망(Promising): 해가 될 가능성이 있는 경우 유망하다고 함가지치기(Pruning): 해가 될 가능성이 없는 경우 해당 노드를 제외하는 것백트래킹(Backtracking): 유망하지 않은 쪼그로 가지 않고 되돌아 오는 것  백트래킹 예시(1)N-Queen 문제N X N 체스판에서 퀸 N개를 서로 공격할 수 없도록 배치하는 경우의 수  백트래킹 예시(2)N-Queen 문제N X N 체스판에서 퀸 N개를 서로 공격할 수 없도록 배치하는 경우의 수  백트래킹 예시(3)N-Queen 문제N X N 체스판에서 퀸 N개를 서로 공격할 수 없도록 배치..

트라이(Trie)문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조정렬된 트리 구조문자열 저장을 위한 메모리가 필요하지만 탐색이 빠름길이가 N인 문자열 탐색의 시간 복잡도: O(N)생성 복잡도: O(N)M: 문자열 개수  트라이 형태문자열 구성apple, april, ace, bear, best파란색 노드: 문자열의 끝을 표시하는 flag를 나타냄  트라이 - 삽입(1)삽입 문자열: apple 트라이 - 삽입(2)삽입 문자열: april 트라이 - 삽입(3)삽입 문자열: appapp까지 있는 단어의 존재를 표시하기 위해 flag가 필요한 것임  트라이 - 삭제(1)삭제 문자열: applee의 flag 표시를 해제하고 자식 노드들이 없으면 e를 지우고l도 자식노드들이 없으므로 지움p는 flag표시..

플로이드-워셜(Floyd-Warshall)모든 노드 간의최단 경로를 구하는알고리즘음의 간선이 포함되어 있어도 사용 가능음수 사이클이 있으면 정상 동작하지 않음알고리즘 복잡도: O(V^3)  플로이드-워셜 알고리즘 Flow (1 / 8)노드 수 V일 때, V x V만큼의 메모리 필요모든 노드에서 모든 노드로 가는 경로 DP 방식 업데이트자기 자신 노드에서 출발은 0으로 업데이트  플로이드-워셜 알고리즘 Flow (2 / 8)각 노드에서 인접 노드로 가는 경로 DP 방식 업데이트  플로이드-워셜 알고리즘 Flow (3 / 8)2번을 지나 2번의 인접노드로 가는 경로들 업데이트6이 2를 거쳐서 다른 노드로 가는 경로 업데이트  플로이드-워셜 알고리즘 Flow (4 / 8)3번을 지나 3번의 인접노드로 가는 경..

벨만-포드(Bellman-Ford)음수 간선이 포함되어 있어도 최단 경로 구할 수 있음 (↔ 다익스트라는 음수 간선 포함 X)다만, 음수 사이클이 있으면 정상 동작하지 않음매번 모든 간선을 확인하기 때문에 다익스트라에 비해 느림알고리즘 복잡도: O(VE)  ** V: 노드 // E: 간선 **   음수 간선이 포함된 가중그래프노드1 -> 노드4 최단 경로다익스트라 적용 시: 7 최단 경로: 5   벨만-포드 알고리즘 Flow (1 / 2)다음과 같이 노드와 간선 가중치 정보가 있을 때, A 노드에서 다른 노드들에 대한 최단 거리 구하기1번 노드부터 돌면서 모든 간선들에 대한 정보를 갱신해 줌(더 작은 값이면 업데이트)   벨만-포드 알고리즘 Flow (2 / 2)다음과 같이 노드와 간선 가중치 정보가 있..

최단 경로 알고리즘가중 그래프 상의 두 노드를 연결하는 가장 짧은 경로를 찾는 방법지도 경로 탐색, 네트워크 구축에 드는 비용을 최소화 하는데 사용최단 경로 알고리즘 다익스트라벨만-포드플로이드-워셜  다익스트라(Dijkstra)출발점에서 목표점까지의 최단 경로를 구하는 알고리즘한 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있음간선에 음의 가중치가 없어야 함그리디 + DP(Dynamic Programming)형태알고리즘 복잡도: O(ElogV)  ** E: 간선 수 / V: 노드 수 **  다익스트라 알고리즘 Flow다음과 같이 노드와 간선 가중치 정보가 있을 때,A 노드에서 다른 노드들에 대한 최단 경로 구하기A 노드부터 A와 연결된 간선 경로 업데이트연결된 간선 중 가장 최단 경로 선택: B (..

분할 정복(Divide and Conquer)큰 문제를 작은 부분 문제로 나누어 해결하는 방법합병 정렬, 퀵 정렬, 이진 검색, ...  분할 정복 과정문제를 하나 이상의 작은 부분들로 분할부분들을 각각 정복부분들의 해답을 통합하여 원래 문제의 답을 구함  분할 정복 장/단점장점문제를 나누어 처리하며 어려운 문제 해결 가능병렬 처리에 이점이 있음 단점메모리를 많이 사용 (재귀 호출 구조)  분할 정복 예시   분할 정복 예시 구현 코드public class Main { public static int getMax(int[] arr, int left, int right) { int m = (left + right) / 2; if (left == right) { ..

그리디 알고리즘(Greedy Algorithm)매 순산 현재 기준으로 최선의 답을 선택해 나가는 기법빠르게 근사치를 계산할 수 있음결과적으로 최적해가 아닐 수도 있음   그리디 알고리즘 예시_1 (1)Activity Selection ProblemN 개의 활동과 각 활동의 시작/종료 시간이 주어졌을 떄, 한 사람이 최대한 많이 할 수 있는 활동의 수 구하기  그리디 알고리즘 예시_1 (2)Activity Selection Problem종료 시간 기준으로 정렬먼저 종료되는 활동 순, 겹치지 않는 순으로 선택  그리디 알고리즘 - Activity Selection Problem 구현 코드// 알고리즘 - 그리디 알고리즘// Activity Selection Problemimport java.util.Arra..

우선순위 큐(Priority Queue)(Priority Queue)우선순위가 높은 데이터가 먼저 나옴 (!= FIFO)모든 데이터에 우선순위가 있음Dequeue 시, 우선순위가 높은 순으로 나감우선 순위가 같은 경우는 FIFO  우선순위 큐 - enqueue, dequeue최소 힙 및 최대 힙의 삭제와 같음    우선순위 큐 - 구현배열 연결 리스트힙    우선순위 큐 자바 코드 구현// 비선형 자료구조 - 우선순위 큐// 연결 리스트를 이용한 우선순위 큐// 자바 기본 PriorityQueueimport java.util.*;public class Main { public static void enqueue(LinkedList list, int data) { int idx = lis..