개발일지

[필수 알고리즘] MST

개념- Minimum Spanning Tree- Spanning Tree : 모든 노드가 연결된 트리- MST : 최소 비용으로 모든 노드가 연결된 트리 MST 푸는 방법 - Kruskal or Prim- Kruskal : 전체 간선 중 작은 것부터 연결- Prim : 현재 연결된 트리에 이어진 간선중 가장 작은 것을 추가 MST 팁- 모든 노드가 연결되도록 한다거나, 이미 연결된 노드를 최소의 비용으로 줄이는 것 MST 사용! heap 사용- 최대값, 최소값을 빠르게 계산하기 위한 자료구조- 이진 트리 구조- 처음에 저장할때부터 최대 or 최소값 결정 핵심코드heap = [[0,1]] -> 앞자리 0은 비용, 뒷자리 1은 노드 번호PriorityQueue heap = new PriorityQueue(..

[필수 알고리즘] DP

개념- Dynamic Programming- 이전의 값을 재활용하는 알고리즘- 예시 : 1~10 숫자중, 이전 값들을 합한 값을 구하라- 이전의 값을 활용해서 시간복잡도를 줄일 수 있음- 점화식이 있어야 풀기 쉬움(An = An-1 + An-2)* for문을 이용해 값을 도출할 때 이전의 결과값과 현재 값을 더하면 시간복잡도를 줄일 수 있음 O(N^2)에서 O(N)이 될 수 있음 아아디어- A1 : 1, A2 : 2, A3 : 1 + 2- An = An-1 + An-2-for문으로 3부터 N까지 돌면서- 이전값과, 그 이전값을 더해서 저장(이때 10007로 나눈 나머지 값) 시간복잡도- for : N > O(N) 자료구조- 방법의 수 배열(An) : int[] 문제풀이- 백준 11726 1. /*1. 아..

[필수 알고리즘] 그리디

개념- 현재 차례의 최고의 답을 찾는 문제- 어려운 이유 : 왜 그런지 증명하기가 어려움- 예시 : 다른 금액의 동전이 여러개 주어졌을때 M원을 만드는 최소의 개수 아이디어- 큰 금액부터 동전 차감- 반례? : 동전의 개수가 무한대라서 없는 것으로 보임- K를 동전 금액으로 나눈 뒤 남은 값을 갱신 시간 복잡도- for : N >O(N) 자료구조- 동전 금액 : int[]- 현재 남은 금액 : int- 동전 개수 : int 문제풀이- 백준 11047 1.class num_11047{ static void Main(string[] args) { var sr = new StreamReader(Console.OpenStandardInput()); var sw = new ..