알고리즘12 [python] 백준 2630번 - 색종이 만들기 모두 같은 색이 나올 때 까지 색종이를 잘라서 각각의 종이의 개수를 구하는 분할정복 문제이다. import sysinput = sys.stdin.readlinedef f(x, y, N): global white, blue c = paper[x][y] same_color = True for i in range(x, x + N): for j in range(y, y + N): if c != paper[i][j]: same_color = False break if not same_color: break if same_color: if c =.. 2024. 8. 11. [python] 백준 11279번 - 최대 힙 최대 힙을 구현하는 문제. import sysimport heapqinput = sys.stdin.readlineN = int(input())heap = []for _ in range(N): x = int(input()) if x == 0: if len(heap) > 0: print(-heapq.heappop(heap)) else: print(0) else: heapq.heappush(heap, -x)heapq 모듈을 사용하면 힙 자료구조를 간편하게 사용할 수 있지만,최소 힙밖에 제공되지 않는다. 따라서 최대 힙을 구현하기 위해서는 원소를 저장할 때 마이너스 부호를 붙여간단하게 최대 힙을 구현할 수 있다. 2024. 8. 11. [python] 백준 1629번 - 곱셈 A^B%C를 구하는 문제.단순하게 쓰면 시간초과가 난다. 이 문제를 풀기 위해서는 두 가지의 개념을 알아야 한다. 분할정복(Divide and Conquer)을 활용한 거듭제곱분할정복을 사용하면 거듭제곱을 빠르게 할 수 있다.보통의 거듭제곱은 x를 n번 곱하기 때문에 시간복잡도가 O(N)이 된다. 하지만 다음과 같은 식을 통해 분할정복을 사용한다면 O(logN)으로 거듭제곱을 할 수 있다.다음은 이 식을 구현한 코드이자 이 문제의 정답이다,import sysinput = sys.stdin.readlineA, B, C = map(int, input().split())def pow(a, b): if b == 0: return 1 tmp = pow(a, b // 2) if b % .. 2024. 8. 5. [python] 백준 9012번 - 괄호 주어진 괄호 문자열이 올바른 괄호 문자열 VPS인지 아닌지 판단하는 문제. 스택이 어떤식으로 활용 되는지 감이 잡히는? 문제인 것 같다.import sysinput = sys.stdin.readlinedef isVPS(s): stack = [] for i in s: if i == "(": stack.append(i) elif i == ")": if len(stack) == 0: return False else: del(stack[-1]) if len(stack) == 0: return True else: return F.. 2024. 7. 22. [python] 백준 16564번 - 히오스 프로게이머 N개의 캐릭터와 각 캐릭터는 X의 레벨을 가진다.레벨을 최대 총합 K만큼 올릴 수 있을 때, 최대 팀 목표레벨 T(min(X))를 구하는 문제. 그냥 이분 탐색 문제이다. import sysinput = sys.stdin.readlineN, K = map(int, input().split())X = [0] * Nfor i in range(N): X[i] = int(input())start = min(X)end = min(X) + Kwhile start x: total += mid - x if total 찾고자 하는 값을 T로 두었다.start는 당연히 min(X)라고 생각했지만, end는 처음에 max(X) + K인 줄 알았다.하지만 다시 생각해보니 min(X) + K여도.. 2024. 7. 20. [python] 백준 2805번 - 나무 자르기 상근이가 M만큼의 나무를 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 문제. 이분 탐색(Binary Search)을 활용하는 문제이다.최근에 문제들을 풀면서 시간 초과 때문에 막힌적이 많은데,이 문제도 마찬가지이다. 시간 복잡도(Time Complexity)를 고려하며 코드를 짜는 연습을 해야겠다는 생각이 들었다. import sysinput = sys.stdin.readlineN, M = map(int, input().split())trees = list(map(int, input().split()))def fn(target): start = 0 end = max(trees) result = 0 while start mid) if s >= .. 2024. 7. 16. 이전 1 2 다음
