[실버 5] 백준 11723 - 집합 (파이썬)
[실버 5] 백준 11723 - 집합 (파이썬)
2025.08.13# 백준 11723 - 집합import sysinput = lambda: sys.stdin.readline().rstrip()S = []M = int(input())for _ in range(M) : line = input().split() if len(line) > 1 : op = line[0] num = int(line[1]) if op == "add" : if num not in S : S.append(num) elif op == "remove" : if num in S : S.remove(num) elif op == "check" :..
[골드 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..
[골드 3] 백준 16957 - 체스판 위의 공 (파이썬)
[골드 3] 백준 16957 - 체스판 위의 공 (파이썬)
2025.07.21분류 : DFS링크 : https://www.acmicpc.net/problem/16957풀이각 공이 어디로 떨어지는가가 아니라 각 골짜기로 얼마나 많은 공이 모이는가를 역방향으로 계산한다.각 칸에서 인접한 8방향 중 가장 낮은 칸으로 공이 흘러간다.그 흐름을 역방향 그래프로 만들어 두고, 실제로 공이 도달할 수 있는 최종 지점부터 시작해서, 역으로 DFS를 돌며 얼마나 많은 공이 이 칸으로 오는지 세는 방식이다.입력 처리R, C = map(int, input().split())B = [list(map(int, input().split())) for _ in range(R)]dr = [0, 0, 1, 1, 1, -1, -1, -1]dc = [1, -1, -1, 0, 1, -1, 0, 1]B[r][c]는 ..
[실버 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]에서의 최솟값을..
[골드 1] 백준 1311 - 할 일 정하기 1 (파이썬)
[골드 1] 백준 1311 - 할 일 정하기 1 (파이썬)
2025.07.19분류 : 다이나믹 프로그래밍링크 : https://www.acmicpc.net/problem/1311풀이이 문제는 N * N 크기의 비용 행렬 D가 주어지고, 사람 N명에게 각각 하나의 일을 배정하는데, 각 사람마다 각 일에 대한 비용이 다르다.각 사람에게 정확히 하나의 일만, 각 일도 정확히 한 사람에게만 배정되도록 하면서 총 비용의 합을 최소화 해야한다.초기 설정cache = [[-1] * (2 ** N) for _ in range(N)]cache[x][mask]는 x번째 사람까지 할당했을 때, mask 상태에서의 최소 비용을 저장한다.기저 조건if x == 0: for i in range(N): if mask == (2 ** i): cache[x][mask] =..
[골드 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] 백준 11578 - 팀원 모집 (파이썬)
[골드 5] 백준 11578 - 팀원 모집 (파이썬)
2025.07.17분류 : 브루트포스 + 자료구조링크 : https://www.acmicpc.net/problem/11578풀이1번부터 N번까지의 문제를 모두 풀 수 있는 최소한의 팀원수를 구하는 문제이다.각 팀원은 자신이 풀 수 있는 문제 번호 리스트를 가지고 있다. 팀원은 M명이며, 문제를 모두 풀 수 있는 팀원의 최소 수를 구해야한다.A = [list(map(int, input().split()))[1:] for _ in range(M)]A = [set(a) for a in A]각 팀원이 자신이 풀 수 있는 문제 번호들을 입력받는다.list(map(int, input().split()))[1:] 에서 [1:] 부터 시작하는 이유는 첫 번째 숫자는 개수이므로 무시한다.set(a)로 변환해서 나중에 합집한 연산을 쉽게 ..
[골드 2] 백준 2450 - 모양 정돈 (파이썬)
[골드 2] 백준 2450 - 모양 정돈 (파이썬)
2025.07.16분류 : 브루트포스링크 : https://www.acmicpc.net/problem/2450풀이배열 A에는 1, 2, 3이 섞여있으면서, 각각 모양을 나타낸다.이 배열을 구간 3개로 나누어서, 각 구간에는 한 가지 모양이 있도록 정렬해야 한다.예를 들어서 [2, 2, 1, 1, 3, 3] 과 같은 형태이다.단, 숫자들을 바꾸는 횟수를 최소화 해아한다.입력 처리는 다음과 같다.N = int(input())A = list(map(int, input().split()))A = [x - 1 for x in A] # 0, 1, 2 로 바꿈입력 배열을 x - 1을 통해서 0, 1, 2로 정규화한다.그후 각 숫자의 개수를 센다.count = [0] * 3for x in A : count[x] += 1예를 들어..
[골드 4] 백준 20159 - 동작 그만. 밑장 빼기냐?
[골드 4] 백준 20159 - 동작 그만. 밑장 빼기냐?
2025.07.09https://www.acmicpc.net/problem/20159풀이플레이어가 번갈아 가면서 카드를 가져간다.짝수 번째(0, 2, 4 … )는 내차례, 홀수 번째는 상대 차례이다.마지막 카드 1장을 상다 차례에서 내가 가져도록 1번의 밑장 빼기를 허용한다.최대 점수를 얻기 위해 밑장 빼기를 어느 위치에서 할지를 결정해야한다.psum0 = [0] * N # 내 차례에서의 누적합psum1 = [0] * N # 상대 차례에서의 누적합psum0[0] = A[0]psum1[0] = 0for i in range(1, N): if i % 2 == 0: # 내 차례 psum0[i] = psum0[i - 1] + A[i] psum1[i] = psum1[i - 1] else: ..