Python

[python] 백준 - 1780. 종이의 개수

🤔문제 해결 S2 | 분할정복 첫번째에 있는 코드가 더 정답인거 같다( 둘다 통과했지만 ) 첫번째 코드는 항상 9개의 조각으로 잘라서 진행한다. - 이게 문제랑 더 맞는거 같다. 하지만 두번째 코드는 (처음 풀어서 통과하고 다시보니 이상함) 9개의 조각이 아니다. 종이가 들어오면 3x3으로 다 잘라버린다. 그래도 통과한다. 이게 되네?? 내가 문제를 잘 이해하지 못한건지... 내가 짠 코드를 이해하지 못한건지 잘 모르겠다. 💻소스 코드 from itertools import chain # 2차원 리스트를 1차원리스트로 바꿔주는 친구 def bt(paper): global a, b, c nn = len(paper) if len(set(chain.from_iterable(paper))) == 1: if pa..

[python] 백준 - 11279. 최대 힙

🤔문제 해결 S2 | 자료구조, 우선순위 큐 최대힙 자료구조를 활용하는 문제 하지만 귀찮으므로 힙큐 모듈을 사용했다. 💻소스 코드 import sys import heapq N = int(input()) numbers = [] for i in range(N): number = int(sys.stdin.readline()) if number: heapq.heappush(numbers, -number) else: if numbers: print(abs(heapq.heappop(numbers))) else: print(0) 📕문제 확인 출처: BACKJOON ONLINE JUDGE 링크: https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤..

[python] 백준 - 10819. 차이를 최대로

🤔문제 해결 S2 | 완전탐색 뭔가 특별한 방법이 있는거 같아서 열심히 짜봤지만 숫자가 겨우 8개 이하이므로 순열을 사용해서 해결(문제유형도 완전탐색) 경우의 수를 전부 구함 💻소스 코드 from itertools import permutations n = int(input()) numbers = list(map(int, input().split())) result = [] for permu in permutations(numbers, n): tmp = 0 for i in range(n - 1): tmp += abs(permu[i] - permu[i + 1]) result.append(tmp) print(max(result)) 📕문제 확인 출처: BACKJOON ONLINE JUDGE 링크: https:..

[python] 백준 - 1541. 잃어버린 괄호

🤔문제 해결 S2 | 수학, 그리디 요번 구현 문제의 핵심은 최초로 마이너스가 나온순간 뒤의 모든 숫자는 음수로 진행할 수 있다!! 💻소스 코드 c = input() answer = 0 c += '*' # 문제의 핵심!! 마이너스가 최초로 한번 나오는 순간 뒤의 모든 숫자들은 마이너스로 취급한다.!!! number = '' operator = '+' for i in range(len(c)): if c[i].isdigit(): number += c[i] else: if operator == '+': answer += int(number) else: answer -= int(number) if c[i] == '-': operator = '-' number = '' print(answer) 📕문제 확인 출처:..

[python] 백준 - 2133. 타일 채우기

🤔문제 해결 S2 | DP 이런문제는 역시 단골 DP문제 일단 손으로 구해봤다. i == 0, 2, 4, 6 ( 홀수 일 경우는 제외함 ) 경우의수 == 1, 3, 11, 41 점화식 dp[i] = dp[i-2] * 3 + (dp[2] ~ dp[i-2]) * 2 + 2 i경우의수 = 이전의 경우의 수 * 3 + 이전의 경우의 수 들 * 2 + i만 만드는 경우 💻소스 코드 N = int(input()) if N % 2: print(0) else: dp = [0] * (N + 1) dp[0], dp[2] = 1, 3 for i in range(4, N + 1, 2): dp[i] = dp[i - 2] * 3 + 2 for j in range(2, i - 2, 2): dp[i] += dp[j] * 2 prin..

힙 정렬(heap sort)

📔 힙 정렬(heap sort) 이란 힙트리구조를 이용하여 정렬하는 알고리즘 힙트리: 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리 힙정렬을 하기 위해서는 먼저 힙 구조를 가지도록 만들어야 한다. 히피파이 알고리즘을 통해 힙구조로 만든다. 모든 정점에 대해서 히피파이를 수행하므로 n x logn 의 시간복잡도를 가진다. 사실상 모든 정점이 아니라 절반의 정점만 해도 가능하다 n/2 x logn => (n/2이 logn 보다 크다고 가정할 때) => 결국 O(n) 의 시간복잡도를 가진다. 📔 힙 정렬(heap sort) 구현 # (최대)힙 구조 만들기 def heapify(): for i in range(1, N): c = i while c > 0: root = (c - 1..