본문 바로가기

알고리즘/Baekjoon

 (196)
이분 탐색. [2805] [1. 문제 설명] 일렬로 있는 각기 다른 높이의 나무를 절단기를 통해 일정 높이로 베었을 때, 얻을 수 있는 나무의 길이를 만족하는 것 중, 절단기에 설정할 수 있는 높이의 최대값. [2. 풀이 접근] 나무를 베어 얻을 수 있는 나무의 길이는 범위는 다음과 같다. [1, MaxTree] 여기서 MaxTree 는 나무의 최대 높이 이 범위 내에서 절단기에 설정 할 수 있는 높이를 결정해야 한다. 나무의 최대 높이는 10억 정도 되므로, 순차 탐색으로는 시간 내에 해결 할 수 없으므로, 이분 탐색을 적용한다. 일부 나무는 탐색 중 적용 할 높이 보다 작은 것 이 있으므로, 얻은 나무 길이가 0 이하의 값은 얻을 수 있는 것에서 제외해야 한다. [3. 코드]
이분 탐색. [1654] [1. 문제 설명] [2. 풀이 접근] 첫번째 접근 (틀린 풀이) 전체 랜선 중 최소 길이를 찾는다. => A [1, A] 범위로 하여 랜선의 길이를 이분 탐색 한다. 전체 랜선의 개수가 조건에 만족하는지 확인한다. (랜선 개수가 더 많은 것은 중요하지 않다.) 이분 한 값이 이전에 최대 랜선 길이보다 더 길 경우 교체한다. 위 접근이 틀린 이유는 전체 랜선 중 최소가 랜선길이의 상한 값이 되었기 때문이다. K 개의 랜선이 각각 [100, 100, 100, 1] 인 경우 왠만하면 필요한 랜선 N 개를 만족하지만, 랜선의 길이는 고작 1밖에 되지 않기 때문이다. 이 경우 1짜리 랜선을 버리는 것이 더 낫다. 따라서, 위 접근에서 A 를 전체 랜선 중 최대 길이로 해야 올바른 접근이 된다. 랜선의 최대 길이..
이분 탐색. [10816] [1. 문제 설명] 입력으로 주어진 숫자 카드를 몇 장 갖고 있는지 계산한다. [2. 풀이 접근] 갖고 있는 카드들을 먼저 오름 차순으로 정렬한다. lower_bound 하한 값 찾고자 하는 값이 제일 처음 오는 index 를 찾는다. => index1 upper_bound 상한 값 찾고자 하는 값 보다 큰 값이 제일 처음 오는 index 를 찾는다. => index2 하한 값이 없을 수 있음에 유의해야 한다. 하한 값이 있는 경우 range: [index1, index2) 따라서, 숫자 카드를 소유 한 개수는 (index2 - index1) 이 된다 [3. 코드] c++ 코드
분할 정복. [6549] [1. 문제 설명] 밑변이 1이고, 높이가 서로 다른 직사각형이 일렬로 인접하여 놓여 있을 때, 가장 넓이가 큰 직사각형을 구해야 함 [2. 풀이 접근] 1. 완전탐색 풀이 l: 왼쪽 offset r: 오른쪽 offset h: [l, h] 에서 최소 높이 넓이 = (l - r + 1) * h => 모든 l 과 h 에 대해서 넓이의 최소 값을 갱신해나가는 방법 이 방법은 n^2 의 시간 복잡도를 갖게 된다. 10^10 이므로 제한시간내 풀이가 불가능 함 2. 분할정복 하나의 큰 히스토그램을 아래와 같이 분할 [Left, Mid] [Mid+1, Right] Mid 를 중심으로 왼쪽과 오른쪽을 겹치도록 1과 2는 탐색 범위를 절반씩 줄여나가므로, logn 의 시간복잡도를 갖고, 3번은 Mid 를 중심으로 해서..
[11444]. 피보나치 수 6 [1. 문제 설명] [2. 풀이 접근] Fi+1 = Fi + Fi-1 Fi = Fi + 0 => 굳이 Fi = Fi-1 + Fi-2 로 표기 할 필요 없다. => Fi = Fi 항등식 위 식을 행렬로 표현할 수 있다. [3. 코드]
[10830]. 행렬제곱 [1. 문제 설명] [2. 풀이 접근] [3. 코드]
[2740]. 행렬 곱셈 [1. 문제 설명] [2. 풀이 접근] [3. 코드]
[1629]. 곱셈 [1. 문제 설명] [2. 풀이 접근] [3. 코드]
[1780]. 종이의 개수 [1. 문제 설명] [2. 풀이 접근] [3. 코드]
[2630]. 색종이 만들기 [1. 문제 설명] 정사각형 모양의 2차원 배열에서 같은 색깔로 구성 된 정사각형의 개수를 찾는 문제. 정사각형 한변의 길이는 최대 128이고, 현재 정사각형이 모두 같은 색깔로 구성되지 않은 경우, 4등분하여 검사한다. [2. 풀이 접근] 재귀로 접근 재귀의 탈출 조건, 정사각형 한변의 길이가 1인 경우 2차원 배열 내 모든 값의 합이 0 이거나, N^2 이면, 모두 같은 색깔로 이루어진 것을 판별할 수 있다. => 배열이 크지 않으니, 시간 상 큰 문제 없다고 생각함. 모든 색깔이 같은 경우, 정사각형 내 아무 원소나 선택 하여 그 색깔을 알 수 있다. 모든 색깔이 같지 않은 경우, 분할 후 재귀로 처리한다. [3. 코드]

티스토리툴바