Dior2ky의 it's IT

백준 11444번 피보나치 수 6 문제이다. 문제는 다음과 같다. 문제만 봤을때는 이게 왜 분할정복 분류지? 걍 하면 되겠는데? 하고 했다가 메모리 초과, 시간초과가 발생했다... 찾아보니 행렬을 이용한 방법이 있었다. 코드는 다음과 같다. import sys def mat_pow(mat, n): if n == 0: return mat elif n == 1: return mat else: tmp = mat_pow(mat, n//2) if n % 2 == 0: result = mul(tmp, tmp) else: a = [1, 1, 1, 0] result = mul(mul(tmp, tmp), mat) return result def mul(a, b): c = [(a[0] * b[0] + a[1] * b[2]..

백준 1922번 쿼드트리 문제이다. 문제는 다음과 같다. 이번 문제도 이전 2630번 색종이 만들기, 1780번 종이의 개수 문제와 유사한 문제이다. 다른점은 입력의 형식이 다르고 이전에는 종이의 개수를 구했다면 이 문제는 괄호와 0, 1을 이용한 문자열로 표현하는 것이다. 색종이 만들기와 같이 4분할을 하여 단계가 넘어가고 만약 모두 1이거나 모두 0이면 1, 0으로 표현 아니라면 4분면 각각을 숫자로 표현하는 방법이다 단계는 괄호로 구분해준다. 코드는 다음과 같다. import sys ln = int(sys.stdin.readline().strip()) result = '' arr = [] def check(n, x, y): global result for i in range(n): for j in ..

백준 1780번 종이의 개수 문제이다. 문제는 다음과 같다. 이전 색종이 만들기 문제와 유사하다. https://certangsecurity.tistory.com/148 백준 2630번 색종이 만들기 백준 2630번 색종이 만들기 문제이다. 문제는 다음과 같다. 이번 문제는 분할 정복 문제로 분류되어 있다. 분할 정복은 문제를 부분으로 나누어 푼것을 나중에 다시 합치는 것으로 재귀를 이용하 certangsecurity.tistory.com 4등분이었던 것이 9등분이 되었고 색깔의 종류가 2가지에서 3가지로 늘었다고 생각하면 될 것 같다. 이전 코드에서 바뀐부분만 수정하여 제출했는데.. 시간초과가 나온다.. 코드를 살펴보면 import sys ln = int(sys.stdin.readline().strip..

백준 2630번 색종이 만들기 문제이다. 문제는 다음과 같다. 이번 문제는 분할 정복 문제로 분류되어 있다. 분할 정복은 문제를 부분으로 나누어 푼것을 나중에 다시 합치는 것으로 재귀를 이용하여 풀어야 한다. 이번 문제를 보면 길이가 2의 배수로 진행된다. 주어진 모양을 문제에 있는 것 처럼 4등분을 해서 각각을 다시 살펴본다. 나누다 보면 1칸이 될 것이고 갯수에 더해주면 된다. 만약 나누었는데 전부 0이거나, 전부 1이면 더이상 나누지 않고 갯수를 더해준다. 코드는 다음과 같다. import sys n = int(sys.stdin.readline().strip()) cnt1 = 0 cnt2 = 0 arr = [] def nemo(n, arr): global cnt1, cnt2 if n == 1: if..

백준 1655번 가운데를 말해요 문제이다. 문제는 다음과 같다. 이번 문제도 우선순위 큐 의 분류로 들어있는 문제로 일반 배열을 사용해서 풀면 시간초과가 나올것이다. 최소 힙, 최대 힙을 통해서는 최소값, 최대값만 구할 수 있다. 중간값을 구하기 위해서는 조금 생각을 해주어야 한다. 이 문제에서는 이 최소 힙과 최대 힙을 둘 다 사용하여 양쪽의 갯수를 계속해서 맞춰주고 최소 힙의 첫번째 값과 최대 힙의 첫번째 값을 비교하면서 바꾸어 주면 중간 값을 구할 수 있을 것 같다. 코드는 다음과 같다. import sys import heapq n = int(sys.stdin.readline().strip()) minh = [] maxh = [] for i in range(n): num = int(sys.stdi..

백준 11279번 최대 힙 문제이다. 문제는 다음과 같다. 문제를 보면 최대 힙 문제는 최소 힙 문제와 비슷하다. 처음엔 최소 힙 문제에서 pop을 배열의 마지막을 하면 되지 않을까 생각했다. 생각한대로 구현 후 출력을 하니 생각과 많이 달랐다. heap에서의 순서는 배열의 순서를 그대로 따라가지 않았다. 트리구조를 그대로 출력한다고 생각하면 이해가 빠르게 될 것이다. 그래서 힙 자체를 변형을 시키기로 했다 최소값이 맨 앞으로 오는 구조이기 때문에 이를 바꾸어 최댓값이 맨 앞으로 오도록 만들기로 했다. 값에 -를 붙이면 제일 큰수가 제일 작은수로 바뀌어 맨앞에 저장이 되고 출력할때만 다시 -을 붙여 출력하면 되는 것이다. 코드는 다음과 같다. import sys import heapq n = int(sy..

백준 1927번 최소 힙 문제이다. 문제는 다음과 같다. 0이 나오면 배열에서 최소값을 출력하고 이외의 숫자는 배열에 넣어주는 문제이다. 이번 문제는 전에 풀었던 절댓값 큐 문제와 유사하다. 오히려 조건이 덜 들어간 쉬운 버전인 것 같다. 음수에 대한 처리와 우선순위에 대한 부분을 없애고 제출을 하니 바로 '맞았습니다' 가 나왔다. 코드는 다음과 같다. import sys import heapq n = int(sys.stdin.readline().strip()) arr = [] for i in range(n): ins = sys.stdin.readline().strip() ins = int(ins) if ins == 0: if len(arr) == 0: print(0) else: print(arr[0])..

백준 11286번 절댓값 힙 문제이다. 문제는 다음과 같다. 요약해보면 첫번째로 몇번 입력받을것인지 N을 입력 받고 N번 입력을 받는다. 숫자가 0이 아닌 수가 나오면 배열에 저장하며 0이 나온 경우는 배열에서 절댓값이 가장 작은수, 절댓값이 같다면 원래의 값이 작은 수를 출력하는 문제이다. 처음엔 그냥 배열을 만들고 -값에 대한 처리는 -1인 경우 0.5, -2인경우 1.5 이렇게 +0.5를 한 후 절댓값을 구해서 동일한 양수값보다 조금 작게 만들어 정렬을 했을때 -값이 먼저 출력 되도록 했다. 하지만. 배열을 사용하고 sort()함수를 사용해서 그런지 시간초과가 발생했다. 찾아보니 heapq를 통해 우선순위 큐를 구현할 수 있었다. 이 heapq를 사용하면 입출력을 하면서 바로 대소비교되어 들어가기 ..

백준 5430번 AC 문제이다. 문제를 살펴보면 문제만 봤을때는 R 과 D에 따라서 처리해주면 쉽게 되지 않을까 생각했다. 실제 코딩을 해보니 생각해줄 것들이 꽤나 있었다. 먼저 D를 통해 pop이 되기 때문에 최종 결과가 요소가 없는 []인 상태가 될 수 있다. 이떼는 error가 아닌 []가 출력되도록 해야 한다. 출력은 [x,y,z,...]의 형태를 만족시켜야 했다. 중간에 띄어쓰기가 있으면 안된다. 로직은 맞지만 돌려보니 시간초과가 나오는 경우가 발생했다. R은 연속으로 나오면 뒤집은걸 다시 뒤집기 때문에 원래의 상태가 된다. 따라서 RR인 경우 없애버리는 로직을 만들었지만 이 또한 시간초과가 발생했다. 뒤늦게 생각해보니 뒤집을 필요가 없었다... Deque이기 때문에 앞뒤로 빼내는 것이 가능하고..

백준 18258번 큐2 문제이다. 문제를 보면 명령어를 계속해서 받고 명령어에 따라 큐를 처리해주면 되는 문제이다. 코드를 짜는 것은 쉽다, 하지만 리스트로 구현을 하는 경우 O(n)의 복잡도를 갖기 때문에 시간 초과가 발생한다. O(1)의 복잡도를 갖는다는 Queue를 사용하여 구현을 하려 했으나 어디서 큰 복잡도를 갖는것인지 시간초과가 나왔다... 결국엔 deque를 사용하여 풀었다. deque가 속도나, 사용하기에 훨씬 편한것 같다. 코드는 다음과 같다. import sys from collections import deque n = int(sys.stdin.readline().strip()) deq = deque() for i in range(n): ins = sys.stdin.readline()..