개발일지

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

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

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

[필수 알고리즘] 이진탐색

이진탐색이란?- 어떤 값을 찾을때 정렬의 특징을 이용해 빨리 찾음- 정렬이 되어 있을 경우, 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 =..

백트래킹이란?- 모든 경우의 수를 확인해야할 때 사용(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. 자료..

DFS란?- 바로가기 [필수 알고리즘] 그래프 탐색그래프 탐색이란?- 어떤 것들이 연속해서 이어질때, 모두 확인하는 방법- Graph: Vertex(어떤 것) + Edge(이어지는 것) 그래프 탐색 종류- BFS : 너비 우선 탐색- DFS : 깊이 우선 탐색 BFS- 자기 자식을 우선lhy-info.tistory.com- Stack과 재귀함수를 이용해 풀수 있음- 그래프 탐색은 BFS로 대부분 풀수 있으며, DFS는 재귀 함수를 사용하기 위함이며 백트래킹에서 효율적이라함 재귀함수란?- 자기 자신을 다시 호출하는 함수- DFS, 백트래킹에서 주로 사용 풀이방법- 시작 Vertex 찾기- 연결된 Vertex를 계속 찾음(끝날때 까지)- 더이상 연결된 Vertex 없을 경우 다음 진행- 1 -> 2 -> 3..