[골드 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: ..
[골드 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))..
[골드 3] 백준 13904 - 과제 (파이썬)
[골드 3] 백준 13904 - 과제 (파이썬)
2025.04.21https://www.acmicpc.net/problem/13904풀이각각의 과제는 마감일(d)와 점수(w)가 주어진다.하루에 하나의 과제만 할 수 있다.점수를 최대화 하도록 과제를 선택해야 한다.즉, 뒤에서부터 앞으로 오면서 해당 날짜에 할 수 있는 과제 중 점수가 가장 높은 것을 선택하는 방식인, 그리디 + 우선순위 큐를 사용한다.왜냐하면 마감일이 큰 과제부터 보되, 그 날짜에 할 수 있는 가장 점수 높은 과제를 선택해야하기 떄문이다.우선순위 큐를 사용해 효율적으로 가장 점수가 높은 과제를 선택 할 수 있다.N = int(input())due = [[] for _ in range(1001)]due[i]는 마감일이 i인 과제들의 점수 리스트를 저장한다.1000일을 기준으로 만든 건, 문제 조건에서 최대..
[골드 1] 백준 2014 - 소수의 곱 (파이썬)
[골드 1] 백준 2014 - 소수의 곱 (파이썬)
2025.04.20https://www.acmicpc.net/problem/2014풀이우선순위 큐를 사용해 가장 작은 수부터 하나씩 꺼낸다.꺼낸 수에 소수 p를 곱해서 새로운 수를 힙에 추가한다.단, 중복된 수가 너무 많이 생길 수 있으므로 최적화를 진행한다.if v % p == 0: break이미 v가 p로 나누어 떨어진다면, 앞으로 곱할 수들은 p가 가장 작은 소인수이므로, 나머지 소수들과 곱하면 중복된 수가 생성된다.예를 들어 2 * 3과 3 * 2는 같은 수 6이 두번 생성된다.따라서 가장 작은 소인수만 사용해서 확장하고 나머지는 무시해서 중복을 방지한다.코드# 백준 2014 - 소수의 곱# 분류 - 수학import heapqK, N = map(int, input().split())P = list(map(in..
[실버 3] 백준 3273 - 두 수의 합 (파이썬)
[실버 3] 백준 3273 - 두 수의 합 (파이썬)
2025.04.20https://www.acmicpc.net/problem/3273풀이정수 수열 A에서 서로 다른 두 수의 합이 X가 되는 경우의 수를 구하는 문제이다.수의 개수 N은 최대 10만개수의 범위는 1이상 1백만 이하진짜 단순하게 itertools의 combination을 사용하면 시간 초과가 엄청나게 난다는 사실,,,# 백준 3273 - 두수의 합# 분류 - 투포인터import sysfrom itertools import combinationsinput = sys.stdin.readlineN = int(input())A = list(map(int, input().split()))X = int(input())count = 0for combination in combinations(A, 2) : if (su..
[골드 3] 백준 2616 - 소형기관차 (파이썬)
[골드 3] 백준 2616 - 소형기관차 (파이썬)
2025.04.20https://www.acmicpc.net/problem/2616풀이열차는 각 객차마자 탑승 인원이 주어져있다.한번에 K개의 객차만을 끌 수 있다.최대 3번까지 소형 기관차 운행이 가능하다.최대한 많은 승객을 운송하는 것이 목표이다.먼저 입력 및 누적합을 계산한다.N = int(input()) # 객차 수A = list(map(int, input().split())) # 각 객차에 탄 승객 수K = int(input()) # 소형 기관차가 끌 수 있는 객차 수psum = [0] * Npsum[0] = A[0]for i in range(1, N): psum[i] = psum[i - 1] + A[i]psum[i]는 0부터 i번째까지의 누적합이다.구간 합 A[i - K + 1] … + A[i]는 p..
[골드 2] 백준 1135 - 뉴스 전하기 (파이썬)
[골드 2] 백준 1135 - 뉴스 전하기 (파이썬)
2025.04.19https://www.acmicpc.net/problem/1135풀이회사에는 N명의 직원이 있고, 0번 직원이 사장이다.각 직원은 한 명의 상사를 가지고 있다. (par[i]가 i번 직원의 상사)뉴스는 각 사장(0번)부터 시작해서 전파되며, 각 직원은 동시에 한명에게만 뉴스 전달을 시작할 수 있다.모든 직원이 뉴스를 전달받기까지 걸리는 최소 시간을 구하는 문제이다.문제는 트리 형태의 구조에서, 루트 노드로부터 모든 노드에게 최대한 빠르게 뉴스를 전파하는 방식으로 시간을 최소화하는 것이다.서브트리들 간의 전파 순서에 따라 시간 차이가 발생하므로, 더 오래 걸리는 자식부터 먼저 처리하는 것이 유리하다.child = [[] for _ in range(N)]for i in range(1, N): child..
[브론즈 1] 백준 1333 - 부재중 전화 (파이썬)
[브론즈 1] 백준 1333 - 부재중 전화 (파이썬)
2025.04.19https://www.acmicpc.net/problem/1333풀이N개의 노래가 재생되고, 각 노래는 L초 동안 재생된다.각 노래가 끝난 후에는 5초의 쉬는 시간이 있다.민식이는 D초마다 전화를 걸며, 노래가 나오지 않을 때만 전화를 받는다.민식이가 전화를 받을 수 있는 가장 빠른 시간을 출력해야한다.check = [False] * 50000에서 4999초까지의 시간 동안 노래가 재생되는지 여부를 저장한다.True 라면 노래가 재생중인 상태이다.index = 0for _ in range(N) : for _ in range(L) : check[index] = True index += 1 for _ in range(5) : index += 1각 노래의 재생 ..
[실버 3] 백준 8911 - 거북이 (파이썬)
[실버 3] 백준 8911 - 거북이 (파이썬)
2025.04.19https://www.acmicpc.net/problem/8911풀이거북이는 F, B, L, R 네 가지 명령어를 받아서 움직인다.시작 위치는 (0,0), 시작방향은 북쪽이다.각 명령어를 수행한 후 거북이가 지나간 경로에서의 가장 큰 직사각형 넓이를 구하는 문제이다.directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]방향 배열을 먼저 설정한다. 각각 동, 북, 서, 남의 방향을 나타낸다.did는 현재 바라보는 방향의 인덱스이며, 처음에는 북쪽이므로 1로 지정한다.if s == "L": did = (did + 1) % 4if s == "R": did = (did + 3) % 4왼쪽 회전 : 90도 반시계 → 인덱스 + 1오른쪽 회전 : 90도 시계 → 인덱스 - ..
[골드 5] 백준 13549 - 숨바꼭질 3 (파이썬)
[골드 5] 백준 13549 - 숨바꼭질 3 (파이썬)
2025.04.18https://www.acmicpc.net/problem/13549풀이다익스트라 알고리즘을 이용해서 풀 수 있다.이 문제는 가중치가 0 또는 1인 그래프에서 최단 시간을 구하는 문제이다.문제를 확인하면 다음과 같은 정보를 확인 할 수 있다.수빈이는 현재 위치 N, 동생의 위치는 K이다.수빈이는 다음 3가지 방법으로 이동 가능하다.x - 1 = 1초x + 1 = 1초2 * x = 0초즉, 0초짜리 이동이 존재하는 가중치 0과 1의 그래프이므도, 일반 BFS보다는 0-1 BFS 또는 다익스트라가 적합하다.adj = [[] for _ in range(200001)]문제에서 최대 위치가 200000이므로, 0부터 200000까지 정점으로 보고 인접 리스트를 초기화한다.범위를 넉넉하게 잡은 이유는 2 * X 가 ..