개발일지

[필수 알고리즘] 폴로이드

개념- 모든 노드에서 다른 모든 노드까지 가는 최소비용, O(V^3)- 다익스트라는 한 노드 -> 모든 노드 작동원리- 노드 j -> 노드 i 비용 배열 만들기, 초기값 : INF- 간선의 값을 비용 배열에 반영- 모든 노드에 대해 해당 노드 거쳐 비용이 작아질 경우 값 갱신 핵심코드// 플로이드 워셜 알고리즘for (int k = 1; k rs[j, k] + rs[k, i]) { rs[j, i] = rs[j, k] + rs[k, i]; } } }}- 3중 for문 이용- rs[j, i] 현재 저장 된 값이 rs[j, k] + rs[k, i] 보다 크면 갱신 아이디어- 거리 초기값을 무한대로 설정 후 자기 자신으로 가는..

[필수 알고리즘] 다익스트라

작동원리- 초기값 무대한으로 설정 및 힙 시작점 추가- 힙에서 현재 노드를 빼며 간선을 통할때 거리가 짧아진다면 거리 갱신 및 힙 추가 핵심코드// [비용, 노드번호] 형태로 저장하기 위한 우선순위 큐 선언PriorityQueue heap = new PriorityQueue();// 시작점 초기화dist[K] = 0;heap.Enqueue(new int[] {0, K}, 0); // [비용, 노드번호]를 저장하고, 비용을 기준으로 정렬while (heap.Count > 0){ // 현재 가장 비용이 적은 노드 정보 추출 int[] current = heap.Dequeue(); int ew = current[0]; // 비용 int ev = current[1]; // 노드 번호 ..

[필수 알고리즘] 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(..

[필수 알고리즘] 그리디

개념- 현재 차례의 최고의 답을 찾는 문제- 어려운 이유 : 왜 그런지 증명하기가 어려움- 예시 : 다른 금액의 동전이 여러개 주어졌을때 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 ..

[필수 알고리즘] 시뮬레이션

시뮬레이션이란?- 각 조건에 맞는 상황을 구현하는 문제(지도상에서 이동하면서 탐험?하는 문제, 배열 안에서 이동하면서 탐험? 하는 문제)- 별도 알고리즘 없이 풀수 있으나, 구현력이 중요- 매 시험마다 1문제 이상 무조건 출제 시간복잡도- N * M- 각 칸에서 4방향 연산 수행 자료구조- 전체 지도 int[][]- 내 위치, 방향; int, int, int 문제풀이- 백준 14503 1. // 입력 받기string[] input = Console.ReadLine().Split();int N = int.Parse(input[0]);int M = int.Parse(input[1]);input = Console.ReadLine().Split();int y = int.Parse(input[0]);int x =..

백트래킹이란?- 모든 경우의 수를 확인해야할 때 사용(for으로 확인 불가할 경우 - 깊이가 달라질때)- 수열을 구하는 문제에 사용 아이디어 1. 1~N중에 하나를 선택2. 이미 선택한 값이 아닌 경우를 선택(방문여부 체크)3. M개를 선택할때 프린트(재귀 함수 사용) 시간복잡도- N^N: 중복이 가능, N = 8까지 가능 (2억이 넘지 않아야함)- N! : 중복이 불가능, N = 10까지 가능 (2억이 넘지 않아야함) 자료구조- 방문 여부 확인 배열 : bool[]- 선택한 값 입력 배열 : int[] 문제풀이- 백준 15649번 1. /*1. 아이디어- 백트래킹 재귀함수 안에서, for 돌면서 숫자 선택(이때 방문 여부 확인)- 재귀함수에서 m개를 선택할 경우 출력2. 시간복잡도- N! 3. 자료..