알고리즘22 [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. [python] 백준 1914번 - 하노이 탑 아주 유명한 하노이 탑 문제.. 시작 기둥에 쌓여있는 n개의 원판 모두를 특정 규칙에 따라서 목표 기둥으로 옮겨야 하는 문제이다. 규칙은 다음과 같다 1. 한 번에 한 개의 원판만 다른 탑으로 옮길 수 있다. 2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 원판의 개수 N이 주어지면 옮긴 횟수, 그리고 그 옮긴 과정들을 출력해야 한다. 원판을 옮기는 과정에는 어떤 규칙이 있을까? A를 시작 기둥, B를 임시 기동, C를 목표 기둥이라고 하자. 가장 먼저 n == 1인 경우에는 단순히 A에 있는 원판을 C로 옮기면 된다. 다음으로는 n == 2인 경우를 보자. 원판 두 개를 옮기려면 다음과 같은 과정을 거쳐야 한다. A -> B A -> C B -> C 일단 A에 있는 작은 원판을 임시.. 2024. 7. 13. [python] 백준 28278번 - 스택 2 스택을 구현하는 문제 시간 초과 떠서 pypy 3로 풀었다. ㅎimport sysN = int(sys.stdin.readline())stack = []def one(X): stack.append(X)def two(): if len(stack) > 0: a = stack[-1] del(stack[-1]) print(a) else: print(-1)def three(): print(len(stack))def four(): if len(stack) == 0: print(1) else: print(0)def five(): if len(stack) > 0: print(stack[-1]) .. 2024. 7. 12. 이전 1 2 3 4 다음
