백준(BOJ)

[백준/C++] 11286번: 절댓값 힙 ( 우선순위 큐 )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/11286 풀이이 문제는 힙 구조의 자료구조에 데이터를 입력하고, 0을 입력받으면 절댓값으로 가장 작은 원소를 출력하는 문제입니다. 이 글에선 C++ 표준 라이브러리의 우선순위 큐( std::priority_queue )를 이용해서 문제를 풀 생각입니다. 이 우선순위 큐( priority queue )는 높은 우선순위를 가진 원소가 먼저 출력되도록 하는 자료구조입니다. [C++] 우선순위 큐( std::priority_queue )의 활용법우선순위 큐( std::priority_queue )우선순위 큐는 가지고 있는 원소들의 우선순위에 따라 정렬된 자료 구조입니다. 일반 큐(queue)는 FIFO( first in, ..

2025. 4. 25.
표준 라이브러리

[C++] 우선순위 큐( std::priority_queue )의 활용법

우선순위 큐( std::priority_queue )우선순위 큐는 가지고 있는 원소들의 우선순위에 따라 정렬된 자료 구조입니다. 일반 큐(queue)는 FIFO( first in, first out ) 방식으로, 먼저 입력된 순으로 출력되지만, 이 우선순위 큐는 원소가 가진 우선순위 순으로 출력되는 순서가 결정됩니다.이러한 우선순위 큐의 원소 배치를 이미지로 나타낸다면 다음과 같습니다. 이 자료구조는 원소를 입력받을 때마다, 가장 높은 우선순위를 가진 원소가 트리의 최상위에 위치하도록 자동으로 정렬을 수행합니다. 그렇기 때문에, 주어진 원소들의 최대 값이나 최소 값을 구하는데 매우 빠른 수행시간을 보여줍니다. 이러한 우선순위 큐를 사용하려면, 우선 다음의 헤더 파일을 포함해야 합니다.#include ..

2025. 4. 25.
백준(BOJ)

[백준/C++] 12015번: 가장 긴 증가하는 부분 수열 2 ( 이진 탐색 )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/12015 풀이이 문제는 주어진 수열에서 오름차순의 숫자들을 찾아서 부분 수열을 만드는 문제입니다. 조건은 만들 수 있는 부분 수열 중에서 길이가 가장 긴 부분 수열을 찾아야 한다는 것입니다. 예를 들어, 다음과 같은 수열이 주어졌다고 해보죠.10 20 30 15 20 25 그러면, 만들 수 있는 오름차순의 부분 수열은 2개가 있습니다.10 20 30, 10 15 20 25이 중에서 길이가 더 긴 10 15 20 25의 부분 수열이 정답입니다.그래서, 길이 4를 출력하는 문제입니다. 이 문제를 푸는 아이디어는, 기존에 선택한 큰 숫자를 작은 숫자로 바꿔가면, 다음에 나오는 고를 수 없는 숫자도 고를 수 있게 된다는 것입..

2025. 4. 24.
백준(BOJ)

[백준/C++] 2805번: 나무 자르기 ( 매개 변수 탐색, Parametric Search )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/2805 풀이이 문제는 주어진 나무들로부터, 나무의 길이 M을 구하기 위한 절단기 높이의 최대 값을 구하는 문제입니다. 그런데, 이 절단기 높이를 높이면, 잘라낼 수 있는 나무의 길이가 줄어들 것이고, 높이를 낮추면, 나무의 길이는 늘어날 것입니다. 그래서, 나무의 길이가 M 이상이 되는 절단기 높이 x에서, 절단기 높이를 더 높이면, 얻을 수 있는 나무의 길이가 점점 줄어들다 어느 순간 M이 되는 절단기 높이 H를 찾을 수 있을 겁니다. 그리고, 절단기 높이를 이 H보다 높이면, 나무의 길이가 M보다 줄어들기 때문에, 이 높이 H가 절단기 높이의 최대 값임을 알 수 있습니다. 따라서, 이 문제를 풀기 위해서는, "절단기..

2025. 4. 23.
백준(BOJ)

[백준/C++] 1654번: 랜선 자르기 ( 매개 변수 탐색, Parametric Search )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/1654 풀이K개의 랜선으로부터 N개의 랜선을 만들 때, 가능한 랜선의 최대 길이를 구하는 문제입니다. 감을 잡기 위해서, 입력되는 값을 간단히 만들어, 어떻게 해야 원하는 값을 구할 수 있을지 생각해 보죠. 예를 들어, 가지고 있는 랜선의 개수 K = 1이고, 이 랜선의 길이는 100이라고 합시다.그리고, 만들고자 하는 랜선의 개수가 N = 10이라면, 랜선의 길이 1의 랜선을 만들 수 있습니다.하지만, 이 길이 1은, 랜선 10개를 만들 때 가능한 최대 길이는 아닙니다.길이 2의 랜선 10개도 가능하기 때문입니다.그런데, 길이 3의 랜선 10개도 가능하므로, 길이 2도 역시 최대 길이가 아닙니다. 이런 식으로, 랜..

2025. 4. 23.
백준(BOJ)

[백준/C++] 1920번: 수 찾기 ( 이진 탐색, binary search )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/1920 풀이이진 탐색을 통해서 찾고자 하는 숫자 X가 주어진 수들 중에 있는지를 판단하는 문제입니다. 이진 탐색( Binary Search )은 전체 구간을 둘로 나누는 과정을, 각 구간의 크기가 0이 될 때까지 반복하면서, 구간 내에 찾는 숫자가 있는지를 검사하는 방법입니다. 이 알고리즘의 과정은 다음과 같습니다. 전체 구간 G의 중간의 숫자가 찾는 숫자인지 검사한다. 찾는 숫자가 아니면, G구간을 A구간과 B구간으로 나눈다.A구간에 대해 1번의 과정을 반복한다. 이 과정을 나눠진 하위 구간의 크기가 0이 될 때까지 반복한다.A구간에서 찾는 숫자가 없으면, 반대쪽 B구간에 대해서도 A구간과 마찬가지로 탐색한다. 이..

2025. 4. 22.
백준(BOJ)

[백준/C++] 10830번: 행렬 제곱 ( 분할 정복법 )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/10830 풀이이번의 문제는 크기가 N x N인 행렬 A의 B제곱을 구하는 문제입니다. 그런데, 문제를 읽어보면 B의 크기가 심상치 않습니다. 실제로 이 문제를 풀면서, 당연히 int 범위의 숫자라고 생각했다가 한동안 헤맸었습니다. 그렇지만, 이 문제의 풀이 방식은 숫자의 거듭제곱을 풀었던 분할 정복법을 적용할 수 있습니다. 단지, A가 숫자가 아니라 행렬이라는 것이 다를 뿐입니다. [백준/C++] 1629번: 곱셈 ( 분할 정복법 )문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/1629 풀이자연수 A를 B번 곱한 수를 구하는 문제입니다. 당연히, A, B에 큰 수가 입력됐을 때 ..

2025. 4. 22.
백준(BOJ)

[백준/C++] 2630번: 색종이 만들기 ( 분할 정복법 )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/2630 풀이같은 색상을 가진 정사각형이 나올 때까지 4등분으로 크기를 점점 줄여가며, 같은 색상으로 이루어진 흰색과 파란색 정사각형의 개수를 세는 문제입니다. 이 문제는 분할 정복으로 문제를 푸는 방식을 보여주는 정석적인 예라고 할 수 있습니다.이 분할 정복법( Divide and Conquer )은 재귀적으로 자신을 호출하면서 조건에 맞을 때까지 그 연산의 단위를 조금씩 줄어가는 방식입니다. 큰 문제를 작고 풀기 쉬운 문제로 나눠 푼 후, 그 결과를 조합해 원래 문제의 답을 구하는 방식이라고 할 수도 있습니다.이러한 방법을 사용하는 대표적인 예로는 이진 탐색(Binary Search), 퀵 정렬(Quick Sort) ..

2025. 4. 22.
백준(BOJ)

[백준/C++] 1629번: 곱셈 ( 분할 정복법 )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/1629 풀이자연수 A를 B번 곱한 수를 구하는 문제입니다. 당연히, A, B에 큰 수가 입력됐을 때 글자 그대로 $A^B$ ( A * A * A * A *... )의 계산을 하면 시간제한에 걸립니다. 이런 경우에 분할 정복법을 쓰게 되면 계산 시간을 상당히 줄일 수 있습니다. 분할 정복법은 재귀적으로 자신을 다시 호출하면서, 조건에 맞을 때까지, 그 연산의 단위를 조금씩 줄어가는 방식입니다. 이 방식은, 큰 문제를 작고 풀기 쉬운 문제로 나눠 푼 후, 그 결과를 조합해 원래 문제의 답을 구하는 방식이라고 할 수도 있습니다. 예를 들어, $2^{10} = 2^5 * 2^5$로 분할할 수 있고, 이제 $2^5$의 계산만 ..

2025. 4. 22.
백준(BOJ)

[백준/C++] 1931번: 회의실 배정 ( 데이터 정렬 )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/1931 풀이이 문제는 겹치지 않으면서 가장 많이 열 수 있는 회의의 수를 찾는 문제입니다. 이러한 문제의 최적의 스케줄은 가장 빨리 끝나는 회의 A부터 시작해서, 끝나는 시간이 점점 늦어지는 회의 순으로 진행하는 것입니다. 만약, A 회의보다 끝나는 시간이 더 늦은 다른 회의 B부터 시작했을 경우를 가정해 봅시다. 그럼, 그다음 회의 C는 반드시 B회의가 끝나는 시간 이후부터 시작해야 합니다. 그런데, 회의 C는 회의 A의 다음 회의 후보가 되기도 하기 때문에, B로 시작하는 회의의 수가 A로 시작하는 회의의 수보다 많아질 수 없습니다. 그래서, 빨리 끝나는 회의부터 늦게 끝나는 회의 순으로 정렬한 후, 겹치는 회의를..

2025. 4. 22.