코테

[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] 백준 - 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..

[python] 백준 - 1182. 부분수열의 합

🤔문제 해결 S2 | 완전탐색(백트래킹) 문제를 잘 이해하지 못해서 많이 헷갈렸다. 그냥 쉽게 설명해서 주어진 숫자들 중 n개를 뽑아서 더한 값이 S와 같은 조합이 몇개인지 구하라는 말 파이썬에서는 쉽게 콤비네이션을 쓰면 된다. 문제 유형에 백트래킹이 있으므로 백트래킹을 연습하고 싶으면 백트래킹을 써도 좋다. 💻소스 코드 from itertools import combinations N, S = map(int, input().split()) numbers = list(map(int, input().split())) answer = 0 for i in range(1, N + 1): for combi in combinations(numbers, i): # print(combi) if sum(combi) ==..

[python] 백준 - 11055. 가장 큰 증가 부분 수열

🤔문제 해결 S2 | 다이나믹프로그래밍 역시 이런 문제는 DP문제이다. dp 리스트를 만든다.(1차원, 인풋값으로 받은 수열과 똑같은 값으로 만든다.) 수열에서 자신보다 앞 쪽에 있는 값 중에서 자신보다 작은 값의 인덱스를 찾는다. 해당 인덱스의 dp값중 가장 큰 값과 자신의 값을 더해 dp를 다시 채운다. dp에서 max값을 출력 💻소스 코드 N = int(input()) numbers = list(map(int, input().split())) dp = numbers[:] dp[0] = numbers[0] # print(f'최초DP: {dp}') for i in range(1, N): for j in range(i): if numbers[j] < numbers[i]: dp[i] = max(dp[i],..

[python] 백준 - 11722. 가장 긴 감소하는 부분 수열

🤔문제 해결 S2 | DP 참고(비슷한 유형) : deok2kim.tistory.com/173 [python] 백준 - 11055. 가장 큰 증가 부분 수열 🤔문제 해결 S2 | 다이나믹프로그래밍 역시 이런 문제는 DP문제이다. dp 리스트를 만든다.(1차원, 인풋값으로 받은 수열과 똑같은 값으로 만든다.) 수열에서 자신보다 앞 쪽에 있는 값 중에서 자신 deok2kim.tistory.com numbers에는 수열이 들어있다. dp라는 1차원 리스트를 만든다. (1초 초기화, 감소하는 부분 수열의 길이가 들어갈 것이다.) 1로 초기화한 이유는 혼자만 가능할 때는 길이가 1이므로 numbers를 하나씩 돌면서 자신보다 앞쪽의 숫자와 비교한다. 자신보다 앞쪽의 숫자가 클 경우 - 나와 그 숫자는 감소하는 부..