[실버 3] 백준 6666 - Help Me with the Game (파이썬)
[실버 3] 백준 6666 - Help Me with the Game (파이썬)
2025.07.31분류 : 구현링크 : https://www.acmicpc.net/problem/6666풀이문제집에서 이거 안풀면 꿈에서 나온다는 말이 있어서 찾아보게된 문제이며, 문제 번호부터가 6666으로 예사롭지가 않다.근데 진짜 문제도 예사롭지 않다.입력을 한번 봐보자+---+---+---+---+---+---+---+---+|.r.|:::|.b.|:q:|.k.|:::|.n.|:r:|+---+---+---+---+---+---+---+---+|:p:|.p.|:p:|.p.|:p:|.p.|:::|.p.|+---+---+---+---+---+---+---+---+|...|:::|.n.|:::|...|:::|...|:p:|+---+---+---+---+---+---+---+---+|:::|...|:::|...|:::|....
[골드 4] 백준 2661 - 좋은수열 (파이썬)
[골드 4] 백준 2661 - 좋은수열 (파이썬)
2025.07.30분류 : 백트래킹링크 : https://www.acmicpc.net/problem/2661풀이이 문제는 숫자 1, 2, 3 으로만 이루어지는 수열이 있으며, 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열은 나쁜 수열이라고 한다.좋은 수열은 인접한 두 개의 부분 수열이 동일하면 안된다. 즉 1212는 마지막 두자리 12가 반복되므로 나쁜 수열이다.길이 N의 좋은 수열 중 사전순으로 가장 앞서는 수열을 찾아야한다.def is_good(seq) : length = len(seq) for i in range(1, length // 2 + 1) : if seq[-i:] == seq[-2 * i : -i] : return False retu..
[실버 2] 백준 11279 - 최대 힙 (파이썬)
[실버 2] 백준 11279 - 최대 힙 (파이썬)
2025.07.29분류 : 자료구조링크 : https://www.acmicpc.net/problem/11279풀이백준 1927과 비슷한 문제이다. 1927 최소 힙 문제에서는 정석대로 heap에 값을 양수로 넣었지만, 이번 문제는 최대 힙을 구하는 문제이기에, -를 붙여서 음수로 넣어주면 힙에서는 최대 힙으로 정렬되게 된다.이때 문제점은 pop 할때도 음수로 나오기에, 다시한번 -를 붙여주면, 최대 힙으로 출력 할 수 있다.코드# 백준 11729 - 최대 힙import heapqimport sysinput = sys.stdin.readlineN = int(input())heap = []for i in range(N) : x = int(input()) if x == 0 : if len(heap) > ..
[실버 2] 백준 1927 - 최소 힙 (파이썬)
[실버 2] 백준 1927 - 최소 힙 (파이썬)
2025.07.29분류 : 자료구조링크 : https://www.acmicpc.net/problem/1927풀이힙의 기초적인 문제이다. 사실 시간초과가 나긴했는데, sys.stdin.readline을 고려하지 못했다.문제에서는 N이 최대 10만개이기 때문에 단순히 input()으로만으로는 당연히 시간 초과가 날 수 밖에 없다.문제에서 N을 입력받고, 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 X가 주어진다고 한다.X가 0이 아닌 경우에는 배열에 자연수 X를 넣고, 0이라면 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거하면 된다.이에 적합한 자료구조는 heap이기에 아래와 같은 코드로 작성하였다.코드# 백준 1927 - 최소 힙import heapqimport sysinput = sys.stdin.r..
[실버 4] 백준 25214 - 크림 파스타 (파이썬)
[실버 4] 백준 25214 - 크림 파스타 (파이썬)
2025.07.20분류 : 다이나믹 프로그래밍링크 : https://www.acmicpc.net/problem/25214풀이각 인덱스 i에 대해, D[i]는 A[0]부터 A[i]까지의 최솟값, E[i]는 E[i-1]과 (A[i] - D[i]) 중 더 큰 값이다.즉, E[i]는 앞에서부터 지금까지의 최댓값을 유지하면서, A[i]에서 이전까지의 최솟값을 뺀 값 중 최대를 갱신한다.D = [0] * NE = [0] * ND[i]는 A[0] ~ A[i] 중 최솟값을 나타내고, E[i]는 지금까지의 A[i] - D[i] 중 최대를 나타낸다.D[0] = A[0]for i in range(1, N) : D[i] = min(D[i - 1], A[i])최솟값 갱신은 위와 같이 작성하며, D[i]는 A[0] ~ A[i]에서의 최솟값을..
[골드 3] 백준 7579 - 앱 (파이썬)
[골드 3] 백준 7579 - 앱 (파이썬)
2025.07.18분류 : 다이나믹 프로그래밍링크 : https://www.acmicpc.net/problem/7579풀이메모리 확보를 위해서 필요한 최소 비용을 구하는 문제다.앱 N개가 있고, 각각 메모리 m[i], 비용 c[i]를 가진다.총 확보해야 할 메모리는 M보다 크거나 같으며, 비용의 합이 최소가 되도록 하는 앱을 선택한다.DP 테이블은 다음과 같이 정의한다.D = [[0] * 10001 for _ in range(N)]D[i][j]는 i번 앱까지 고려했을 때, 비용 j 이하로 확보 가능한 최대 메모리를 나타내며, 비용 최대치가 10000이므로 열 크기를 10001로 설정한다.# D[0][i] : 첫 번째 앱만 사용할 때의 최대 메모리for i in range(c[0], 10001) : D[0][i] = ..
[플래티넘 5] 백준 1981 - 배열에서 이동 (파이썬)
[플래티넘 5] 백준 1981 - 배열에서 이동 (파이썬)
2025.07.15분류 : 이분 탐색 + BFS링크 : https://www.acmicpc.net/problem/1981풀이N x N 크기의 정수 배열 A가 주어짐(0, 0) → (N-1, N-1)까지 상하좌우로 이동 가능단, 이동하는 칸의 숫자는 어떤 [min, max] 구간에 속해야 함이때 max - min 의 최소값을 구하는 것이 목적문제 풀이 아이디어는 다음과 같다.배열의 값은 최대 200이므로 min ~ max 범위가 0~200 사이임max - min mid 값을 이분 탐색으로 줄여나가며 최소값을 찾는 방식초기 설정은 다음과 같이 진행한다.low, high = 0, 200answer = -1mid = max_val - min_val 을 이분 탐색으로 줄여 나갈 범위이다.이분 탐색을 시작한다.while low 현재..
[골드 5] 백준 17072 - 나무 위의 빗물 (파이썬)
[골드 5] 백준 17072 - 나무 위의 빗물 (파이썬)
2025.07.11https://www.acmicpc.net/problem/17073풀이이 문제는 비의 양 W가 루트 노드에 고이며, 나무는 N개의 정점으로 이루어진 트리이고, 루트 노드는 1번이다.비는 모든 리프 노드까지 동일하게 분배되며, 각 리프 노드까지 고인 빗물의 양을 구하는 문제이다.결국 이 문제를 해결하는 방법은 다음과 같다.트리는 사이클이 없는 연결 그래프이므로, DFS로 리프 노드를 쉽게 찾을 수 있다.루트에서 DFS를 돌려 리프 노드의 개수를 센다.전체 물이의 양 W를 리프 노드 개수로 나눈다.리프노드마다 동일한 양의 물이 고이기 때문이다.먼저 정점 수, 물의 양을 입력받는 인접 리스트를 생성한다.N, W = map(int, input().split())adj = [[] for _ in range(N)]..