반응형 코딩테스트 준비220 알고리즘 - 그리디(Greedy) 알고리즘 그리디 알고리즘 미래를 고려히지 않고 오직 현재 시점에 가장 좋은 선택 ex) 백준 - 동전0(11047) 핵심은 최소 동전 수이다. N개의 동전 중 금액이 제일 큰 것부터 가능한 많이 사용하고 그 다음 큰 동전 사용하기를 반복하면 된다. 그러므로 가장 큰 금액부터 최대한 많이 소진하고 뒤에있는 동전은 신경쓰지 않는다. 특징 미래를 신경쓰지 않고 현실에만 충실한 게 최적의 해가 될 수 있을까? 항상 보장하지 못한다. 그러므로 근사 알고리즘이라고 한다. 01 탐욕스런 선택 조건(Greedy Choice Property) 현재의 선택이 미래의 선택에 영향을 주지 않는다. 예를 들어 서울-대전-부산에 가는 방법 02 최적 부분 구조 조건(Optimal Substructure) 부분의 최적 해가 모이면 전체의 .. 2024. 3. 26. 백준 C# - 2108 +) 풀이 01 산술평균 소수점 이하 첫째 자리에서 반올림한 값을 출력한다. Math.Round를 사용했다. (int)Math.Round(sum / n) 02 중앙값 문제에서 N이 홀수인 조건이 있다. 홀수가 아니였으면 푸는게 복잡했을텐데 홀수이므로 입력받은 값들을 정렬시키고 중간위치에 있는애를 출력하면 된다. (int)list[n/2] 03 최빈값 제일 구하기 복잡했던 최빈값 먼저 생각했던 방법은 Dictionary를 사용해서 입력받은 m이 있는 경우 해당 Value값을 증가시키고 없는 경우 Key가 m, Value가 1인 값을 추가한다. for(int i = 0; i x.Value).ThenBy(x => x.Key).ToDictionary(x => x.Key, x => x.Value); 여러 개 있을 때에는 최.. 2024. 3. 24. C# - 1966 +) 풀이 기본 셋팅 01 Queue 생성 Tuple의 첫번째 요소에는 index값 두번째 요소에는 중요도를 담는다. Queue queue = new Queue(); int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse); for (int i = 0; i < N; i++) { queue.Enqueue(new Tuple(i, input[i])); } 02 input.Sort() 중요도를 오름차순으로 정렬한다. Array.Sort(input); 03 하나씩 꺼내기 Tuple firstitem = queue.Dequeue(); 주요 알고리즘 01 만약 firstitem이 현재의 제일 큰 중요도와 같을 경우 현재 중요도는 그럼 dequeue됐으니까 다음.. 2024. 3. 17. 백준 C# - 11286 +) 눈물의 풀이 들어가기 앞서 풀다가 못풀겠어서 힌트를 찾아봤는데 C#으로된 정답 코드가 없었다.. Phthon으로 된 코드는 heapq을 이용해서 코드가 간단한데 C#은 없다 눈물.. 그래서 6시간정도 걸렸다. 하핳.. 그래도 통과돼서 뿌듯하다 실패 01 Sort 사용 첫번째로 풀었을때 Sort를 이용해서 풀었는데 2%에서 시간초과가 떴다. using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace baek2 { class Program { public static void Main() { List pq = new List(); int n = int.Parse(Console.ReadLine()); for(i.. 2024. 3. 17. C# - 백준 코드 처리 속도(실행 시간) 측정 방법 +) Stopwatch 프로퍼티 및 메서드 설명 Stopwatch Stopwatch 클래스를 사용하기 위해서는 using System.Diagnostics; 네임스페이스를 추가해야한다. using System.Diagnostics; 01 인스턴스 생성 및 코드 실행 시간 측정 시작 Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); 02 코드 실행 시간 측정 종료 stopwatch.Stop(); 03 코드 실행 시간 출력 // 측정된 시간 출력 Console.WriteLine($"코드 실행 시간: {stopwatch.Elapsed}"); // 측정된 시간 출력 (밀리초 단위) Console.WriteLine($"코드 실행 시간 (밀리초): {stopwatch.ElapsedMilliseconds}");.. 2024. 3. 17. C# - 우선순위 큐(Priority Queue)와 힙(Heap) Queue 큐는 FIFO구조로 먼저 들어온 데이터가 먼저 나가는 구조이다. Priority Queue 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나온다. 예를 들어 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건보다 꺼내서 확인해야 하는 경우이다. 우선순위큐를 구현하는 방법 01 리스트를 이용 데이터의 개수가 N개 일 때, 구현 방식에 따라서 시간 복잡도 삽입시간 O(1), 삭제 시간 O(N) 02 힙(Heap)을 이용 데이터의 개수가 N개 일 때, 구현 방식에 따라서 시간 복잡도 삽입시간 O(logN) (힙의 조건을 유지하기 위해 부모 노드와 비교하면서 올라간다) ,삭제 시간 O(logN)(루트 노드를 삭제한 후 힙을 재조정해야 한다) Heap 완전 이진 트리 자료 구조의 일종이다. 항상.. 2024. 3. 16. 이전 1 2 3 4 5 6 7 8 ··· 37 다음 반응형
