본문 바로가기
반응형

코딩테스트 준비211

백준 C# - 2630 +) 풀이 분할 정복 문제이다. 예제를 보면서 어떻게 분할할지 생각해보자 8 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 알고리즘 생각 부분 색종이는 모두 같은 색상이어야한다. 그렇지 않는 경우 색종이를 1/2씩 분할하여 모두 같은 색인지 다시 체크하며 재귀적으로 확인한다. 위의 생각을 코드로 표현해보자 01 부분 색종이가 모두 같은 색상인지 체크 int firstColor = paper[row, col]; bool isSame= true; for (int i = row; i < row + size; i++) { for (int j .. 2024. 4. 1.
백준 C# - 1021 +) 풀이 이 문제는 Deque(덱) 자료구조를 사용해서 풀어야 되는 문제이다. C#은 제공되는 Deque(덱)자료구조가 없어서 직접 Queue를 이용해서 풀어야한다. Deque의 특징 큐와는 달리 항목의 추가와 삭제가 머리와 꼬리 양쪽 끝 모두에서 처리가 가능하다. (문제에서 자세히 안내되어있다) 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다. 과정 그림으로 예시 10 3 2 9 5 알고리즘 01 목표 원.. 2024. 3. 31.
백준 C# - 14425 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace baek2 { class Program { public static void Main() { int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse); int n = input[0]; int m = input[1]; List n_input = new List(); for(int i = 0; i0) { m--; m_input = Console.ReadLine(); if (n_input.Contains(m_input)) answer++; } Console.Write(ans.. 2024. 3. 31.
알고리즘 - 그리디(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.
반응형

티스토리툴바