Programming/백준
[플레티넘 5] 백준 3197 - 백조의 호수 (파이썬)
[플레티넘 5] 백준 3197 - 백조의 호수 (파이썬)
2025.04.26https://www.acmicpc.net/problem/3197풀이백조의 호수 문제는 BFS를 통해서 풀이가 가능하다.문제에서 요구하는 조건은 호수에 얼음이 덮여있다.얼음으로 뒤덮인 호수에 백조 두 마리가 있음물은 백조가 지나갈 수 있지만 얼음은 못 감매일 얼음이 물과 접촉한 부분부터 녹음두 백조가 만날 수 있는 최소 날짜를 구하는 문제입력 처리 및 초기 세팅을 진행R, C = map(int, input().split())A = [list(input()) for _ in range(R)]R, C와 맵을 2차원 리스트로 저장한다.백조 위치 탐색swans = []for i in range(R): for j in range(C): if A[i][j] == "L": swa..
[골드 5] 백준 12919 - A와 B 2 (파이썬)
[골드 5] 백준 12919 - A와 B 2 (파이썬)
2025.04.26https://www.acmicpc.net/problem/12919풀이문자열 S에서 시작하여 문자열 T를 만들 수 있는지 판단하는 문제이다.수행할 수 있는 연산은 다음과 같다,문자열 뒤에 ‘A’ 추가문자열을 뒤집고 뒤에 ‘B’ 추가하지만 이 코드에서는 역방향으로, 즉 T에서 시작해서 S로 갈 수 있는지 확인한다.def dfs(t): if len(t) == len(S): return t == S현재 문자열 t의 길이가 S와 같아졌다면 t == S 인지 비교해서 결과를 반환한다.if t[-1] == "A": if dfs(t[:-1]): return True재귀 조건으로 문자열 끝이 A라면 A를 추가한 결과였을 수 있으므로 마지막 문자를 제거하고 재귀를 호출한다.if t[0..
[골드 2] 백준 2381 - 최대 거리 (파이썬)
[골드 2] 백준 2381 - 최대 거리 (파이썬)
2025.04.25https://www.acmicpc.net/problem/2381풀이N = int(input())P = [list(map(int, input().split())) for _ in range(N)]N개의 점을 입력받고 리스트 P에 저장한다.max_plus = -1e9min_plus = 1e9for x, y in P : max_plus = max(max_plus, y + x) min_plus = min(min_plus, y + x)(x + y)의 최대값 최소값을 계산한다.max_minus = -1e9min_minus = 1e9for x, y in P : max_minus = max(max_minus, y - x) min_minus = min(min_minus, y - x)(y - x)의..
[실버 4] 백준 2980 - 도로와 신호등 (파이썬)
[실버 4] 백준 2980 - 도로와 신호등 (파이썬)
2025.04.25https://www.acmicpc.net/problem/2980풀이길이 L인 도로 위에 N개의 신호등이 있음각 신호등은 D(거리), R(빨간불 지속 시간), G(초록불 지속 시간)의 정보를 가짐차량은 초당 1m 이동빨간불이면 정지, 초록불이면 통과도로의 끝까지 도달하는 데 걸리는 시간 출력사실 이부분에서 계속 오류가 나서 봤더니 “)” 위치가 왜 뒤로 가 있던건지,, 하,,N, L = map(int, input().split())info = [list(map(int, input().split())) for _ in range(N)]N, L, info는 각각 신호등의 개수, 도로 길이, 각 신호등의 위치 D, 빨간불 R, 초록불 G를 저장한다.state = ['R'] * Nremain = [info[i]..
[골드 3] 백준 16437 - 양 구출 작전 (파이썬)
[골드 3] 백준 16437 - 양 구출 작전 (파이썬)
2025.04.24https://www.acmicpc.net/problem/16437풀이각 섬에는 양(S) 또는 늑대(W)가 있으며,한 섬에 있는 동물들은 연결된 부모 섬(루트 방향)으로 이동한다.만약 늑대 수가 양보다 많으면 그만큼 양이 잡아먹힌다.목표: 1번 섬(루트)에 도착할 수 있는 양의 최대 수 구하기입력처리는 다음과 같이 지정한다.N = int(input()) # 섬의 개수A = [0] * N # 각 노드에 있는 양 또는 늑대 수 (양은 양수, 늑대는 음수)child = [[] for _ in range(N)] # 트리 구조 저장 (부모 -> 자식)for i in range(1, N) : t, a, p = input().split() a = int(a) p = int(p) - 1 ..
[골드 1] 백준 2213 - 트리의 독립집합 (파이썬)
[골드 1] 백준 2213 - 트리의 독립집합 (파이썬)
2025.04.24https://www.acmicpc.net/problem/2213풀이정점 포함 vs 미포함 두 가지 상태로 나눠서 각각 최적값을 저장서브트리의 정보를 재귀적으로 계산하면서 합산각 노드가 포함되는 경우, 자식 노드는 반드시 제외각 노드가 포함되지 않는 경우, 자식 노드는 포함 여부 선택 가능D[u] : 정점 u를 포함하는 경우 최대 독립집합 가중치 합E[u] : 정점 u를 포함하지 않는 경우 최대 독립집합 가중치 합D_sol[u] : 정점 u를 포함하는 경우 선택된 정점 목록E_sol[u] : 정점 u를 포함하지 않는 경우 선택된 정점 목록DFS는 다음과 같이 처리한다.def dfs(u): visit[u] = True D[u] = A[u] # 자기 자신 포함 D_sol[u].append(..
[실버 4] 백준 11508 - 2+1 세일 (파이썬)
[실버 4] 백준 11508 - 2+1 세일 (파이썬)
2025.04.24https://www.acmicpc.net/problem/11508풀이N개의 물건 가격이 주어진다2 + 1세일은 물건을 세개 살때 가장 싼 한개는 무료로 적용한다.이때, 최소 비용으로 구매하는 금액을 구하라아이디어비싼 순으로 정렬후3개씩 묶어서, 그 중 가장 싼 물건은 빼기discount = 0for i in range(0, N, 3) : if i + 2 3개씩 묶어서 매 세번째 아이템을 할인 대상으로 적용한다.단, 범위를 벗어나지 않도록 if i + 2 print(sum(C) - discount)전체 가격 합에서 할인액을 뺴서 최종 결제 금액을 출력한다.코드# 백준 11508 - 2+1 세일# 분류 : 그리디N = int(input())C = []for i in range(N) : C.app..
[골드 5] 백준 15989 - 1, 2, 3 더하기 4 (파이썬)
[골드 5] 백준 15989 - 1, 2, 3 더하기 4 (파이썬)
2025.04.23https://www.acmicpc.net/problem/15989풀이정수 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구하라같은 수라도 순서가 다른 것은 같은 경우로 취급한다.예를 들어 3 = 1 + 2 와 2 + 1은 같은 경우로 처리된다.DP 배열을 아래와 같이 정의한다.D = [[0] * 10001 for _ in range(4)]D[i][j]는 1부터 i까지의 숫자만 사용해서 j를 만드는 경우의 수를 의미한다.예를 들어서 D[2][4]는 1, 2만 사용해서 4를 만드는 방법의 수를 나타낸다.점화식은 아래와 같이 구성한다.D[0][0] = 1for i in range(1, 4): # 1, 2, 3 사용 for j in range(10001): D[i][j] = D[i - ..
[골드 3] 백준 2629 - 양팔저울 (파이썬)
[골드 3] 백준 2629 - 양팔저울 (파이썬)
2025.04.23https://www.acmicpc.net/problem/2629풀이추는 영쪽 저울에 올릴 수 있다.이떄 만들 수 있는 무게 차를 추들을 사용해서 계산한다.D[i][j]는 앞에서 i개의 추를 사용해서 j - zero 만큼의 무게 차이를 만들 수 있는가?N = int(input()) # 추의 개수A = list(map(int, input().split())) # 추의 무게 리스트M = int(input()) # 구슬의 개수B = list(map(int, input().split())) # 구슬의 무게 리스트zero = 40001로 초기화 해주었다. 그 이유는 인덱스에서 음수를 표현하기 위해서 기준점 0을 40001로 설정하였다.점화식의 초기 값을 다음과 같이 설정한다.D[0][zero] = True..
[골드 2] 백준 13334 - 철로 (파이썬)
[골드 2] 백준 13334 - 철로 (파이썬)
2025.04.22https://www.acmicpc.net/problem/13334풀이N개의 사람 정보 (집과 사물실의 좌표)철로의 길이는 D로 고정됨하나의 철로로 최대 몇 명을 커버할 수 있는가?즉 철로구간[a, a + D] 내에 (start, end) 모두 포함된 사람이 최대 몇명인지?일단 코드를 잘못 짠 부분이 있다.for i in range(N) : pq.put(X[i][1])그냥 끝점 기준으로 넣고, 무조건 X[i][1] + D를 오른쪽 끝이라 생각해버렸다.시작점이 X[i][0] 보다 작은 사람도 같이 포함될 수 있다.이 뿐만 아니라 시작점보다 왼쪽인 선분을 제외하기 않았다.철로 구간 [x, x + D] 안에 들어오려면, start ≥ x and end ≤ x + D 여야한다.따라서 end를 기준으로 정렬..
[골드 4] 백준 16562 - 친구비 (파이썬)
[골드 4] 백준 16562 - 친구비 (파이썬)
2025.04.22https://www.acmicpc.net/problem/16562풀이친구끼리 돈을 모아서 대표 한 명의 친구비만 내면 된다.모든 사람들과 친구가 되려면 각 친구 그룹당 최소 친구비만 내면 된다.이때 전체 친구비가 K원 이하라면 총합을 출력, 초과하면 “Oh no”를 출력for _ in range(M): u, v = map(int, input().split()) u -= 1 v -= 1 adj[u].append(v) adj[v].append(u)친구 관계 입력을 받는다 이때 0-Based Index를 통해서 1씩 빼주고 무방향 그래프로 설정 한다.visit = [False] * Ntotal = 0for i in range(N): if visit[i]: cont..
[골드 4] 백준 1253 - 좋다 (파이썬)
[골드 4] 백준 1253 - 좋다 (파이썬)
2025.04.22https://www.acmicpc.net/problem/1253풀이핵심 아이디어는 투포인터 기법을 이용하여 어떤 수가 두 수의 합으로 표현될 수 있는지를 판별하는 것이다.즉, N개의 수가 주어졌을때, 그 수들 중 어떤 수 하나가 나머지 두수의 합으로 표현될 수 있는 경우를 찾고, 그러한 수의 개수를 구하는 문제이다.N = int(input())A = list(map(int, input().split()))A.sort()A를 정렬하면 투 포인터를 사용할 수 있는 기반이 마련된다.for j in range(N): if j == i: continue target = A[i] - A[j]A[i]에서 A[j]를 빼서 나머지 한 수 target이 A 배열 안에 존재하는지 확인한다.k = N..
[실버 4] 백준 3986 - 좋은 단어 (파이썬)
[실버 4] 백준 3986 - 좋은 단어 (파이썬)
2025.04.22https://www.acmicpc.net/problem/3986풀이좋은 단어란 연속된 두 문자가 항상 짝을 이뤄서 서로 제거되며, 최종적으로 아무 글자도 남지 않는 단어를 의미한다.예를 들어서 AABB → A-A, B-B 가 짝지어 제거되므로 좋은 단어이다.stack = []for s in S: if len(stack) == 0 or stack[-1] != s: stack.append(s) else: stack.pop(-1)각 문자를 순서대로 읽으면서 스택을 이용해서 처리한다.스택이 비어있거나, 스택의 마지막 문자와 현재 문자가 다르면 현재 문자를 스택에 push한다.스택의 마지막 문자와 현재 문자가 다르면 pop하여 짝짔는다.if len(stack) == 0: ..
[실버 2] 백준 5397 - 키로거 (파이썬)
[실버 2] 백준 5397 - 키로거 (파이썬)
2025.04.21https://www.acmicpc.net/problem/5397풀이문자열 입력 중에 , - 는 특별한 키로 작동한다.: 커서를 오른쪽으로 옮긴다.: 커서 왼쪽의 문자를 삭제한다.나머지 문자는 커서 위치에 삽입되며, 최종적으로 만들어진 문자열을 출력해야한다.스택 2개를 활용하여 커서의 왼쪽과 오른쪽을 나누어 관리한다.stack1 : 커서 왼쪽에 있는 문자들stack2 : 커서 오른쪽에 있는 문자들이 방식은 시간복잡도를 O(N)으로 유지하면서 빠르게 구현이 가능하다.시간 복잡도 분석각 테스트케이스마다 O(N)전체 시간복잡도 : O(T * N)코드# 백준 5397 - 키로거# 분류 : 자료구조T = int(input())for i in range(T) : S = input() stack1 ..
[골드 4] 백준 1967 - 트리의 지름 (파이썬)
[골드 4] 백준 1967 - 트리의 지름 (파이썬)
2025.04.21https://www.acmicpc.net/problem/1967풀이트리의 지름은 다음의 두번의 DFS로 구할 수 있다.임의의 노드에서 가장 먼 노드를 찾는다 → who그 노드에서 다시 가장 먼 노드까지의 거리가 트리의 지름이다.import syssys.setrecursionlimit(10 ** 9)파이썬의 기본 재귀 깊이가 얕기 때문에 DFS에서 런타임 에러 방지를 위해서 깊이를 늘린다.N = int(input())adj = [[] for _ in range(N)]노드 수 N입력 후, 입접 리스트 adj를 생성한다.for _ in range(N - 1): u, v, w = map(int, input().split()) u -= 1 v -= 1 adj[u].append((v, w))..