반응형 Programming406 [C/C++] 백준 #2261 가장 가까운 두 점(분할 정복) #2261 문제는 분할 정복의 대표격인, 병합정렬, 퀵정렬, 히스토그램과 함께 자주 나옵니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 분할 정복과 관련한 게시글은 다음과 같습니다. https://sdev.tistory.com/904 [C/C++] 백준 #1780 종이의 개수(분할정복) 이번 문제는 무조건 분할을 한 후에, 그 결과를 토대로 결정을 하게 하는 문제입니다. 결국 분할 정복.. 2023. 4. 19. [C/C++] 백준 #2252 줄 세우기(위상 정렬) #2252 문제는 위상 정렬을 이용해서 풀 수 있는 문제입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상 정렬은 작업의 선후관계 등에서 많이 사용됩니다. 소프트웨어 공학에서는 작업의 전체 시간을 결정하는 요소로도 많이 사용됩니다. 대부분의 경우 작업의 종류가 많지 않기 때문에 손쉽게 수작업으로도 표시할 수 있습니다. 위상 정렬과 관련된 문제들이 많이 있었으니, 참조하시길.. 2023. 4. 19. [C/C++] 백준 #2251 물통(너비 우선 탐색) #2251 문제는 고전적인 너비 우선 탐색인데, 노드의 개수가 정확하게 얼마인지 모르는 문제입니다. 하지만 상한은 정해져있습니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 이것은 옛날에 퀴즈에 자주 나오는 문제입니다. 3개의 물통을 가지고 정해진 물의 양을 만드는 방법으로 퀴즈를 풀었습니다. 그러한 것을 프로그램으로 푸는 방법입니다. 그림과 같이 용량이 정해져있는 3개의 물통이 있습니다. C에는 물.. 2023. 4. 19. [C/C++] 백준 #2250 트리의 높이와 너비(이진 탐색 트리) #2250 문제는 이진 탐색 트리를 잘 이해하는 가에 대한 문제입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 이진 탐색 트리(BST; Binary Search Tree)는 노드들을 탐색하는 방법으로 3가지 방법을 사용합니다. 전위(pre-order), 중위(in-order), 후위(post-order) 탐색법입니다. 우리는 이 중에 중위 탐색법을 사용합니다. 위와 같은 이진 탐색 트리가 있다면, .. 2023. 4. 19. [C/C++] 백준 #2247 실질적 약수(수학) #2247 문제는 주어진 범위안의 1과 자기자신을 제외한 약수들의 합을 계산하는 문제입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2247 2247번: 실질적 약수 첫째 줄에 CSOD(n)을 1,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 수학에서 약수와 배수는 밀접한 상관관계가 있습니다. \(2 \times 5 = 10 \)이란 식에서 2와 5는 10의 약수이기도 하지만, 10은 2의 배수이고, 10은 5의 배수이기도 합니다. 이 문제는 위의 원리를 잘 이해하는데에서 출발합니다. 문제는 주어진 N에 대해서 1부터 N까지 1과 자기자신을 제외한 약수들의 총 합을 구하라는 문제입니다. 일일이 하나씩 해보면, 1과 소수는 조건에 맞는(실질적).. 2023. 4. 18. [C/C++] 백준 #2243 사탕상자(세그먼트 트리) #2243 문제는 백준 사이트에서 자주 나오는 고급 문제인 세그먼트 트리 문제입니다. 세그먼트 트리가 이미 많이 알려져서, 사실 이제는 그렇게 어려운 알고리즘이라고 할 수도 없습니다. 문제 링크입니다. https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 세그먼트 트리는 쿼리의 종류가 두가지인 경우에 사용할 수 있습니다. 저는 읽는 쿼리와 쓰는 쿼리라고 이야기를 합니다. 읽는 쿼리만 있는 경우에는 전체의 개수가 N, 쿼리의.. 2023. 4. 18. 이전 1 ··· 7 8 9 10 11 12 13 ··· 68 다음 728x90
