개발일지

개념- 모든 노드에서 다른 모든 노드까지 가는 최소비용, 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]; // 노드 번호 ..

개념- 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(..

개념- 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 ..

이진탐색이란?- 어떤 값을 찾을때 정렬의 특징을 이용해 빨리 찾음- 정렬이 되어 있을 경우, O(N) -> (logN)- 기존 다른 방법으로 시간 복잡도를 생각했을때, 안되면 이진탐색으로 처리하면 좋음 첫 아이디어- M개의 수마다 각각 어디에 있는지 찾기- for : M개의 수- for : N개의 수안에 있는지 확인 첫 시간복잡도- for : M개의 수 > O(M)- for : N개의 수안에 있는지 확인 > O(N)- O(MN) = 1e10 > 시간초과 아이디어- M개를 확인해야는데, 연속하다는 특징 활용 가능(투포인터)? => 연속하지 않아 불가- 정렬해서 이진탐색 가능?(N개의 수 먼저 정렬)(M개의 수 하나씩 이진 탐색으로 확인) 시간 복잡도- N개의 수 정렬 : O(N * lgN)- M개의 수 ..

투포인터란?- 각 원소마다 모든 값을 순회해야할때, o(n^2)- 연속하다는 특성을 이용해 처리, O(N)- 두개의 포인터(커서)가 움직이면서 계산 처음 아이디어- for문으로 각 숫자의 위치에서 이후 K개의 개수를 더함- 이때마다 최대 값으로 갱신 처음 시간 복잡도- for문 : O(N)- 각 위치에 K개의 값 더함: O(K)- 총 : O(NK) 아이디어- 처음 K개의 값을 구함- for문: 다음 인덱스의 값을 더하고, 앞의 값을 뺌- 이때 최대값을 갱신 시간 복잡도- 숫자 개수만큼 for => O(N) 자료구조- 전체 정수 배열: int[]- 합한 수 : int 문제풀이- 백준 2559 1.public class num_2559{ static void Main(string[] args) {..

시뮬레이션이란?- 각 조건에 맞는 상황을 구현하는 문제(지도상에서 이동하면서 탐험?하는 문제, 배열 안에서 이동하면서 탐험? 하는 문제)- 별도 알고리즘 없이 풀수 있으나, 구현력이 중요- 매 시험마다 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 =..

백트래킹이란?- DFS와 유사한 알고리즘으로 차이점이 있다면 효율성이 있습니다. 가지치기라고 하여 조건에 만족하지 않을 경우 진행하지 않고 이전 단계로 넘어가는 형태를 말합니다. 이것으로 인해 모든 경로를 탐색하지 않아도 되어 효율성이 좋습니다. 구현방식 및 동작원리- 재귀함수로 구현하며 조건에 만족하지 않을 경우 이전 단계로 돌아감 시간 복잡도- 문제마다 다릅니다. 왜냐하면 조건에 만족하느냐 안하느냐에 따라 더 진행할지 말지가 정해지기 때문 입니다. 문제 유형- 순열, 조합, N-Queen 가 있습니다. 해당 문제들은 주어진 조건이 명확하고 조기에 진행 불가능한 상태를 확인할 수 있기 때문입니다. 참고영상- 바로가기 - 바로가기

DFS란?- 그래프 완전 탐색 중 하나로 깊이 우선 탐색 알고리즘 입니다.- 깊이 우선 탐색 특성상 Stack과 재귀함수로 구현합니다. 왜냐하면? 후입선출의 특성을 사용하기 위함입니다.예를들어 1 -> 2 -> 3으로 노드들이 붙어있을때 3번을 체크한 후 2번 1번 순으로 탐색하기 때문에 후입선출 특성이 필요합니다. 시각화- 1 -> 2 -> 3 -> 4 -> 6 -> 5 시간 복잡도- O(V+E)- BFS와 동일하게 완전 탐색이기 때문에 "모든 노드의 수" + "연결된 간선의 수"로 시간 복잡도를 계산합니다. 주의사항- 방문한 곳을 재방문하지 않도록 해야합니다.이유는첫번째로 효율성이 떨어지기 때문입니다. 이미 방문한 곳을 또 방문해서 체크할 필요 없기 때문이죠두번째는 무한루프가 발생할 수 있습니다. 예..