개발일지

읽기 좋은 코드가 좋은 코드다 의 첫번째 주제는 "코드는 이해하기 쉬워야한다" 이다.읽은 내용을 정리하며 한번 더 머리속에 새기기 위해 한 단원씩 읽고 정리하려 한다. 1. 무엇이 코드를 '더 좋게' 만드는가?for(Node* node = list->head; node != NULL; node = node->next) Print(node->data); Node* node = list->head;if(node== NULL) return;while(node->next != NULL){ Print(node->data); node = node->next;}if(node != NULL) Print(node->data); 두 코드는 동일한 일을 수행하고 있음에도 첫번째 코드가 더 낫다 하지만 많은 경우에 판단..

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

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