Scat

yongmin's dev blog

[BOJ] 11286번 절대값 힙 - C++

"우선순위 큐"

문제 절대값 힙 풀이 최소힙에서, pair<T, T>로 절대값 최소힙을 구현하는 코드이다. pair<절댓값, 실수값>으로 설정하여, 절대값이 제일 작은 것 중 실수값이 제일 작은 것, 즉, 절댓값이 같으면 음수가 top에 위치해있도록 하게 한다. 이렇게 구현하면 문제에서 원하는대로 구현이 되어 쉽게 top의 second를 출력하...

Posted by Yongmin on July 3, 2021

[BOJ] 12015 가장 긴 증가하는 부분 수열 2 - C++

"이분탐색"

문제 가장 긴 증가하는 부분 수열 2 풀이 기존에 DP로 풀었던 문제와 같은 문제이다. 그러나, 같은 알고리즘으로 하면 testcase의 arr.size()가 커져서 시간초과가 나는 문제이다. 문제의 알고리즘은 다음과 같다. 주어진 testcase의 첫번째 값을 result vector에 넣는다. iteration으로 N번째까지 조건에 부합...

Posted by Yongmin on July 2, 2021

[BOJ] 1300번 K번째 수 - C++

"이분탐색"

문제 K번째 수 풀이 이분 탐색을 위해 1을 left로 N x N 을 right로 먼저 시작한다. mid = (left+right)/2; 로 설정하여, mid보다 작거나 같은 수가 몇개인지 셉니다. 그 숫자가 K보다 크다면 범위를 줄이기 위해서 right = mid - 1 로 설정하고 그 숫자가 K보다 작다면 범위를 늘리기 위해서 left = mid...

Posted by Yongmin on July 1, 2021

[BOJ] 2110번 공유기 설치 - C++

"이분탐색"

문제 공유기 설치 풀이 거리의 최솟값 1을 left로 거리의 최대값 arr[N-1] - arr[0]을 right로 설정하여 이분탐색을 진행한다. mid = (left+right)/2로 설정하여 그 간격 이상에 위치한 집에 공유기를 설치했을 때 설치하려는 공유기 수 보다 많은 값이 나오면 간격을 늘려서(left = mid + 1로 바꾸어서 간격을 늘린...

Posted by Yongmin on June 30, 2021

[BOJ] 2805번 나무 자르기 - C++

"이분탐색"

문제 나무 자르기 풀이 가장 긴 나무를 right로, 1을 left로 시작하여 이분탐색을 진행하였다. 기존의 이분 탐색과 똑같으며, 다만 mid가 tree의 높이보다 클 때 추가되는 나무의 길이가 없다는 것만 고려해주면 되는 문제이다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ...

Posted by Yongmin on June 30, 2021

[BOJ] 1654번 랜선 자르기 - C++

"이분탐색"

문제 랜선 자르기 풀이 이 문제 역시 이분탐색으로 시간초과를 면해야 하는 문제이다. 주어진 testcase에서 가장 높은 것을 right로, 1을 left로 시작하여 mid보다 크냐 작냐로 이분탐색을 해나간다. mid로 나누었을 때 생긴 랜선 갯수가 주어진 testcase보다 크거나 같을 때 더 큰 값을 탐색하기 위해 left = mid + 1로, ...

Posted by Yongmin on June 29, 2021

[BOJ] 10816번 숫자 카드 2 - C++

"이분탐색"

문제 숫자 카드 2 풀이 이분탐색을 통해서 시간 초과를 피해야 하는 문제이다. 해당코드는 Referece에서 가지고 왔다. lower_bound(해당 숫자가 맨 처음 나타나는 index)와 upper_bound(해당 숫자가 맨 나중에 나타나는 index)를 구해서 서로 빼주면 되는 문제이다. lower_bound와 upper_bound의 구현을 기억...

Posted by Yongmin on June 28, 2021

[BOJ] 11444번 피보나치 수 6 - C++

"분할정복"

문제 피보나치 수 6 풀이 피보나치 수를 구하는 문제이다. 기존에 재귀함수식으로는 N의 범위를 표현할 수가 없다. Fn+1 = 1xFn + 1xFn-1 이고, Fn = 1xFn + 0xFn-1 이므로, 결과적으로 (Fn+1, Fn)^T = (1 1, 1 0)^T x (Fn, Fn-1)^T 이다. Un = (Fn+1, Fn)^T로, A = (1 1,...

Posted by Yongmin on June 25, 2021

[BOJ] 10830번 행렬 제곱 - C++

"분할 정복"

문제 행렬 제곱 풀이 알고리즘 자체는 행렬들을 분할정복으로 거듭제곱을 하는 식이 같지만, 구현이 행렬로 바뀜에 따라 어려움이 있어 다른 분의 코드를 가지고 왔다. 2중벡터로 행렬을 표현하고, 거듭제곱 부분에서 분할정복을 이용하는 코드이다. 거듭제곱을 하는 부분을 기억해두면 좋을 것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 matr...

Posted by Yongmin on June 24, 2021

[BOJ] 11401번 이항 계수 3 - C++

"분할정복"

문제 이항 계수 3 풀이 이항 계수에 moduler 연산을 하는 문제이다. N과 K의 범위가 4,000,000(4백만)이나 되기 때문에 factorial을 구하면 long long 범위를 훨씬 넘는다. (20!조차도 long long 범위를 넘는다고 한다. nCk = n! / (k! * (n-k)!) 이다. 그러므로 이 문제에서는 n! / (k! *...

Posted by Yongmin on June 24, 2021

FEATURED TAGS
Format BOJ C++ Python Algorithm
ABOUT ME

짱구