Programming/백준
[골드 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..