[골드 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))..
[골드 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 가 ..
[실버 1] 백준 1932 - 정수 삼각형 (파이썬)
[실버 1] 백준 1932 - 정수 삼각형 (파이썬)
2025.04.18https://www.acmicpc.net/problem/1932풀이정수로 이루어진 삼각형이 주어질 떄, 맨 위에서부터 아래로 내려가면서 선택한 수의 합이 최대가 되도록 경로를 찾는 문제이다.한 칸 아래로 이동할 떄는 바로 아래 또는 바로 아래 오른쪽으로만 이동할 수 있다.N = int(input()) # 삼각형의 높이A = [list(map(int, input().split())) for _ in range(N)] # 삼각형 데이터A는 삼각형 형태의 숫자 배열이다.D = [[0] * (i + 1) for i in range(N)]D[0][0] = A[0][0]D[i][j]는 i번째 줄, j번째 위치까지 올 때 최대 합을 저장하는 DP테이블이다.첫번째 숫자는 그대로 초기화한다.for i in rang..
[실버 2] 백준 11053 - 가장 긴 증가하는 부분 수열 (파이썬)
[실버 2] 백준 11053 - 가장 긴 증가하는 부분 수열 (파이썬)
2025.04.17https://www.acmicpc.net/problem/11053풀이이 문제는 조금 복잡하다… 일단 다이나믹 프로그래밍 풀이로 작성하였는데, 일반적인 풀이보다 2차원 DP를 활용한 조금은 특이한 방식이다.일단 문제는 수열 A가 주어졌을때, 증가하는 부분 수열 중 가장 길이가 긴 것의 길이를 구하는 문제이다.D = [[0] * 1001 for _ in range(N)] # N * 1001D[i][j] 는 i번째까지 고려했을때, 마지막 수가 j이하인 증가 부분 수열의 최대 길이이다.for i in range(1001): D[0][i] = 1 if A[0] 첫번째 원소만 쓸 수 있는 상황에서 j 조건을 만족하면 길이는 1로 지정한다.for i in range(1, N): for j in range..
[골드 4] 백준 1976 - 여행 가자 (파이썬)
[골드 4] 백준 1976 - 여행 가자 (파이썬)
2025.04.17https://www.acmicpc.net/problem/1976풀이N개의 도시가 있고, 어떤 도시끼리는 도로로 연결되어 있다.M개의 도시가 주어진 여행 계획에 포함되어 있다.주어진 도시들이 모두 같은 연결 요소에 속해 있다면 여행이 가능하다.연결 정보는 인접 행렬로 주어진다.이 문제는 그래프 연결 요소 판별 문제이다.BFS를 통해 각 도시가 어떤 연결 요소에 속해 있는지 visit 배열에 저장하고여행 계획에 포함된 도시들이 모두 같은 연결 요소에 속해 있는지를 확인한다.하나라도 다르면 NO, 모두 같으면 YES를 출력한다.N = int(input()) # 도시 수M = int(input()) # 여행에 포함된 도시 수adj = [[] for _ in range(N)]for i in range(N..
[브론즈 1] 백준 1526 - 가장 큰 금민수 (파이썬)
[브론즈 1] 백준 1526 - 가장 큰 금민수 (파이썬)
2025.04.17https://www.acmicpc.net/problem/1526풀이금민수란 숫자는 4또는 7로만 이루어진 수이다. 입력으로 주어지는 N이하의 수 중에서 가장 큰 금민수를 출력하는 문제이다.결국, 1~6자리의 모든 금민수를 생성하고, 그중 N이하인 것 중 가장 큰 수를 찾는다.이 문제는 6자리 이하의 숫자만 고려하면 되므로, 완전탐색으로 충분히 해결 할 수 있다.for i in range(1, 7): # 자릿수: 1~6자리 for j in range(i + 1): # 7을 넣을 자리 개수 for combination in combinations(range(i), j): kms = 0 for k in range(i): ..