백준 문제풀이(파이썬)

두 번째 LIS 문제이다. 이전에 풀었던 문제와 같지만 범위가 1000에서 1000000으로 늘어났기 때문에 O(N²) 풀이법인 dp로 풀면 시간 초과가 나올게 분명하다. O(NlogN) 풀이의 핵심은 LIS를 구하는 것이 아니라 LIS의 길이만 구하는 것이다. 단지 길이만 구하는 것이기 때문에, 순회하면서 저장해둔 배열의 마지막 원소보다 크면 append해주고 작으면 덮어주는(?) 식으로 풀면 된다. ##함수 선언 부분 import sys input = sys.stdin.readline ##변수 선언 부분 A = [] dp = [0] mid = 0 ##메인 함수 부분 if __name__ == "__main__": N = int(input()) A = [int(x) for x in input().spl..

놀랍게도 이분 탐색으로 풀리는 문제이다. B[k]는 어찌됐건 1부터 N²까지 수 중에 하나이기 때문에, 1을 left, N²을 right로 설정하여 이분 탐색을 진행하면 될 것이다. k가 의미하는 것이 무엇일까? N = 5이고, k = 16인 경우를 생각해보자. N = 5인 경우를 쭉 나열해보면, B[k] = B[16] = 10이다. 10과 N과 k의 관계에 대해 알아내면 대충 감이 올 것 같다. B = [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 8, 8, 9, 10(k), 10, 12, 12, 15, 15, 16, 20, 20, 25] k번째 이전의 숫자들은 2차원 배열일 때 [1][1] ~ [1][5] : 5개 [2][1] ~ [2][5] : 5개 [3][1] ~ [3][3] ..

히스토그램에서 넓이가 가장 큰 직사각형을 구하는 문제이다. 최댓값이 될 수 있는 경우는 1. 경계의 왼쪽에서 너비 1의 직사각형이 최대인 경우 2. 경계의 오른쪽에서 너비 1의 직사각형이 최대인 경우 3.경계를 기준으로 붙어있는 직사각형이 최대인 경우로 세가지가 있다. 1번과 2번 경우는 너비가 1이 될 때까지 분할해서 1이면 높이를 return해주면 되지만, 3번 경우는 combine해줄 때 start부터 end까지 돌면서 최대의 직사각형을 구해줘야하기 때문에, 3번의 경우에 주목해서 코드를 짜야한다. start부터 end까지의 범위가 정해졌을 때 경계(mid)를 기준으로 맞닿아있는 직사각형은 각각 square[mid](왼쪽), square[mid+1](오른쪽)일 것이다. left와 right는 각각 ..

행렬의 제곱을 이용하여 피보나치수열을 구하는 문제이다. 피보나치 수를 구하는 방법 중에 DP를 이용하는 방법이 가장 효율적이라고 생각했었는데, 더 빠른 방법이 있다는 것이 신기했다. 일단 입력값이 매우 크기 때문에 O(N)의 알고리즘으로는 절대 풀 수 없음을 인지하고 있어야 한다. DP로 풀면 O(N)이기 때문에 다른 방법으로 풀어야 하는데, 앞에서 계속 풀었던 행렬을 이용하면 된다. 피보나치수열을 행렬을 이용하여 표현하면 밑의 식과 같다. 위의 식이 의미하는 것은 행렬 [[1,1], [1,0]]을 i번 제곱한 값에 행렬 [[1], [0]]을 곱하여 피보나치 수를 구할 수 있다는 것이다. 또한 제곱을 해줄 때 매번 1/2로 단축이 되기 때문에 시간 복잡도는 O(logN)이다. ##함수 선언 부분 MAX_..

이항 계수를 구하는 문제이다. 이항 계수 1과 이항 계수 2에서는 DP로 풀 수 있었지만, 이 문제의 입력 범위가 매우 크기때문에 같은 방식으로 풀면 시간 초과가 뜬다. 그러므로 문제 앞에 나와있는 페르마의 소정리를 이용하여 풀어보자. 정수 a와 p가 있고 a가 p의 배수가 아니면서 p가 소수(Prime number)일 때 다음이 성립한다. 수식을 풀이하면 a^p를 p로 나눈 나머지는 a를 p로 나눈 나머지가 된다는 뜻이다. 또한 양 변을 a로 나누면 다음 식을 유도할 수 있다. (n, k)%p -> (n!/k!(n-k)!)%p -> A=n!, B=k!(n-k)!로 치환 -> (A*B^(-1))%p -> ((A%p) * (B^(-1)%p))%p -> ((A%p) * (B^(p-2))%p)%p -> (A*..

파란색 사각형과 하얀색 사각형의 개수를 구하는 문제이다. 1/4로 계속해서 나누어 주면서 만약 나누어진 영역의 값이 모두 1이거나 모두 0 이면 카운트해주면 되겠다. 2차원 배열로 입력값을 받기 때문에 분할을 한 뒤 각 영역의 시작과 끝 인덱스가 중요할 것이다. merge sort 알고리즘을 짜 보면 대충 어떻게 풀 지 감이 온다. merge sort에서는 left와 right로 mid를 구해서 left부터 mid, mid+1부터 right까지 두 개로 분할해서 재귀 함수를 만들었다. 같은 원리로 이 문제에서는 두 개로 나누는 것이 아니라 네 개로 나눌 뿐이다. 그렇다면 어떻게 나누어야 할까? 시작 부분의 인덱스와 끝 부분의 인덱스를 안다면 그것을 꼭짓점으로 하는 사각형을 구할 수 있을 것이고, 모두 1..

중간값을 찾는 문제이다. 매번 입력을 받을 때마다 지금까지 입력받은 수들의 중간값을 출력해주면 된다. 정렬을 한 뒤 중간 index의 값을 출력해주면 되겠지만, 입력 값이 100,000개이기 때문에, O(n^2)의 시간 복잡도를 생각하면 시간 초과가 뜰 것이다. 이번 단계가 우선순위 큐인 만큼 힙을 이용해야한다. 예를 들어 11개의 원소가 있고, 그 중 중간값의 특징을 생각해보자. 11개를 오름차순으로 정렬한다고 할 때 중간값을 포함한 왼쪽 6개중에서 중간값은 그들중에서 최댓값일 것이고, 오른쪽 5개의 원소들의 최솟값보다 작을 것이다. 짝수개일때도 마찬가지로, 만약 10개라고 가정한다면, 중간값을 포함한 왼쪽 5개중에서 최댓값이고, 오른쪽 5개의 원소들의 최솟값보다 작을 것이다. 꼭 정렬을 하여 최소 최..

11279번 문제는 최대 힙, 1927번 문제는 최소 힙을 이용하여 각각 최댓값, 최솟값을 구하는 문제이다. 두 문제 모두 등호만 다를 뿐 코드는 같기 때문에, 더 어려울 수 있는 최소 힙을 풀겠다. 그전에 힙에 대해 알아보자. 힙이란, 우선순위 큐를 위한 자료구조이자, 다른 알고리즘에 비해 최댓값, 최솟값을 빠르게 구하게 해준다. 또한 힙은 반 정렬 상태이다. 처음에 우선순위 큐와 힙에 대해서 혼동이 왔었다. 내가 알던 큐는 처음에 들어온 것이 제일 먼저 나가는 FIFO형태였는데, 우선순위에 따라 먼저 나간다는 개념이 낯설었다. 힙은 우선순위 큐를 구현하기 위한 도구(?)이고, 또한 힙은 반 정렬 상태라는 것을 알고 나니 이해가 됐다. 반 정렬 상태라는 건 트리안의 모든 수가 정렬이 되어있는 것이 아니..