Programming/백준
[골드 5] 백준 - 노드사이의 거리 (파이썬)
[골드 5] 백준 - 노드사이의 거리 (파이썬)
2025.04.03https://www.acmicpc.net/problem/1240풀이트리의 노드 N, 거리 구할 쌍의 개수 M을 초기에 입력받는디ㅏ.N - 1개의 간선정보와 M개의 노드 쌍이 주어진다.트리는 사이클이 없고, 두 노드사이의 경로가 항상 유일하게 존재한다.따라서 s번 노드에서 DFS를 돌리면 모든 노드까지의 거리를 구할 수 있다.t번 노드까지의 누적 거리를 출력하면 s - t 거리이다.for _ in range(N - 1): u, v, w = map(int, input().split()) u -= 1 v -= 1 adj[u].append((v, w)) adj[v].append((u, w))트리의 간선을 입력 받고, 편의를 위해서 1씩 빼준다.또한 양방향으로 연결하기 u, v를 각각..
[실버 4] 백준 1269 - 대칭 차집합 (파이썬)
[실버 4] 백준 1269 - 대칭 차집합 (파이썬)
2025.04.02https://www.acmicpc.net/problem/1269풀이A를 집합(set)으로 변환집합을 사용하면 in 연산이 평균 시간 복잡도 O(1)로 빠르게 작동B를 순회하며 A에 포함된 원소 개수를 센다.대칭 차집합 개수 계산print(N + M - 2 * count)시간 복잡도 분석집합 변환 (set) : O(N)B 순회 및 포함 여부 확인 : O(M)최종 연산 : O(1)최종 시간 복잡도 : O(N + M)코드# 백준 1269 - 대칭 차집합# 분류 : 집합N, M = map(int, input().split())A = list(map(int, input().split()))B = list(map(int, input().split()))A = set(A)count = 0for b in B : ..
백준 2495 - 연속구간 (파이썬)
백준 2495 - 연속구간 (파이썬)
2025.04.02https://www.acmicpc.net/problem/2495풀이이 문제는 0과 1로 이루어진 문자열이 세 줄 주어졌을 때, 각 줄에서 같은 숫자가 연속으로 등장하는 가장 긴 길이를 구하는 문제이다.예를 들어, “0001000”이라는 문자열에서는 0이 최대 3번 연속으로 등장하므로 정답은 3이 된다.문자열을 앞에서부터 한 글자씩 확인하면서, 이전 문자와 같은지 비교한다.만약 현재 문자가 이전 문자와 같다면, 현재 연속 길이(count)를 1 증가시킨다.반대로 다르다면, 연속이 끊긴 것이므로 count를 1로 초기화한다.매 반복마다 지금까지의 최대 연속 길이(max_count)를 갱신다.문자열을 모두 확인한 후, 해당 줄의 최대 연속 길이를 출력한다.시간 복잡도 분석각 줄에 대해 한번 씩 문자열을 순회..
백준 2456 - 나는 학급회장이다 (파이썬)
백준 2456 - 나는 학급회장이다 (파이썬)
2025.04.01https://www.acmicpc.net/problem/2456풀이투표는 여러 명의 학생들이 진행하며, 각 사람은 1번, 2번, 3번 후보에게 1~3점 중 하나씩 점수를 준다.가장 총점이 높은 사람이 회장이 됨.동점일 경우에는 다음 우선순위로 결정.3점을 더 많이 받은 후보2점을 더 많이 받은 후보그래도 같으면 무효처리 (0)코드# 백준 2456 - 나는 학급회장이다# 분류 : 구현N = int(input())score = [0] * 3count_3 = [0] * 3count_2 = [0] * 3for _ in range(N) : s = list(map(int, input().split())) for i in range(3) : score[i] += s[i] if s..
백준 2491 - 수열 (파이썬)
백준 2491 - 수열 (파이썬)
2025.03.31https://www.acmicpc.net/problem/2491풀이어떤 수열이 주어졌을 때, 연속적으로 커지거나 같거나, 혹은 작아지거나 같은 부분 수열 중 가장 긴 길이를 구하는 문제이다.비내림차순 수열의 최대 길이 계산비오름차순 수열의 최대 길이 계산위 두 결과 중 최대값을 출력A[: : -1] 로 뒤집어서 감소하거나 같은 부분 수열을 구할 수 있도록 바꾼다.시간복잡도 분석비내림차순 수열의 계산 → O(N)비오름차순 수열의 계산 → O(N)즉, O(N)코드# 백준 2491 - 수열# 분류 : 구현N = int(input())A = list(map(int, input().split()))max_count = 1count = 1for i in range(1, N) : if A[i- 1]
백준 2506 - 점수계산 (파이썬)
백준 2506 - 점수계산 (파이썬)
2025.03.30https://www.acmicpc.net/problem/2506풀이쉬운 문제이다, 각 문제가 연속해서 옳은 정답인 경우 증가하고, 틀린 문제가 있다면 0점으로 초기화 하여, 누적합이 되지 않도록 하는 문제이다.단순히 for문으로 O(N) 시간 복잡도로 문제를 해결할 수 있다.코드# 백준 2506 - 점수계산# 분류 : 구현N = int(input())scores = list(map(int, input().split()))answer = 0score = 0for i in scores : if i == 1 : score += 1 answer += score else : score = 0 print(answer)
백준 2485 - 가로수 (파이썬)
백준 2485 - 가로수 (파이썬)
2025.03.30https://www.acmicpc.net/problem/2485풀이가로수들이 일정하지 않은 간격으로 심어져 있다. 이 간격을 모두 같게 만들기 위해 새로운 나무들을 더 심어야한다.현재 심어진 가로수의 좌표가 주어진다.추가로 심어야 하는 나무의 수를 구하는 문제이다.풀이과정은 다음과 같다.각 인접한 나무 사이의 간격을 구한다.3 - 1 = 2, 7 - 3 = 4, 13 - 7 = 6이 간격들의 최대공약수를 구한다.간격을 모두 gcd로 만들면 최소한의 나무로 균등 간격이 된다.전체 거리에서 gcd 간격으로 나무를 심었을 때의 전체 나무를 개산한다.기존에 있던 나무 수를 빼면, 추가로 심어야 할 나무 수가 나온다.코드# 백준 2485 - 가로수# 분류 : 수학N = int(input())X = [0] * N..
백준 2527 - 직사각형 (파이썬)
백준 2527 - 직사각형 (파이썬)
2025.03.28https://www.acmicpc.net/problem/2527풀이두 직사각형이 주어졌을 때, 겹치는 영역이 어떤 형태인지 판단하는 문제이다.다양한 겹침의 경우를 다음 네가지 중 하나로 분류해야한다.a → 직사각형이 겹치는 경우 (면적으로 겹침)b → 직사각형이 선분으로 겹침c → 꼭짓점만 겹침d → 전혀 겹치지 않음x축 겹침 여부 판단 및 y축 겹침 여부 판단을 진행하면 된다.위에서 구한 x_intersection, y_intersection 값을 조합해서 미리 정의된 결과 테이블에서 문자를 출력하면 답을 쉽게 구할 수 있다.코드# 백준 2527 - 직사각형# 분류 : 기하학answer = [ ['d', 'd', 'd'], ['d', 'c', 'b'], ['d', 'b', 'a']]f..
백준 2460 - 지능형 기차 2 (파이썬)
백준 2460 - 지능형 기차 2 (파이썬)
2025.03.28
백준 2526 - 싸이클 (파이썬)
백준 2526 - 싸이클 (파이썬)
2025.03.28https://www.acmicpc.net/problem/2526풀이수열 A는 다음과 같이 정의할 수 있다.A_0 = NA_i = A_{i-1} * N mod P수열을 계속 계산하다 보면, 언젠가 같은 값이 다시 등장해서 반복(싸이클)이 발생한다. 이때 반복되는 구간의 길이를 구하는 문제이다.order 딕셔너리는 각 숫자가 몇 번째에 처음 등장했는지를 저장한다.n = n * N % P는 문제에서 정의된 수열의 다음 항을 계산한다.만약 n이 이미 order에 있다면싸이클이 시작된 시점은 order[n]현재 시점은 count즉, 싸이클 길이는 count - order[n]코드# 백준 2526 - 싸이클# 분류 : 구현N, P = map(int, input().split())n = Norder = {}coun..
백준 2530 - 인공지능 시계 (파이썬)
백준 2530 - 인공지능 시계 (파이썬)
2025.03.28https://www.acmicpc.net/problem/2530풀이조금 고민을 한 문제이다.그냥 단순히 수학 공식을 이용해서 풀려다가 어짜피 초를 입력 받기 때문에 초 단위로 증가시켜도 된다는 판단이 들은 문제이다.시긴도 1초에다가, 최대 500,000초가 주어지기 때문에 시간도 넉넉하다고 생각했다.단순히 6025를 입력받으면 6025번 반복을 진행한다.만약 C가 60이 되면 B를 1 증가 시키고 C를 0으로 바꾸는 식으로 진행해서 췹게 풀수 있는 문제였다.코드# 백준 2530 - 인공지능 시계# 분류 : 수학A, B, C = map(int, input().split())D = int(input())for i in range(D) : C += 1 if C == 60 : B += ..
백준 31962 - 등교 (파이썬)
백준 31962 - 등교 (파이썬)
2025.03.26https://www.acmicpc.net/problem/31962풀이학생 N명이 학교 까지 가는데 S[i] 분이 걸리고, 등교 준비 시간으로 T[i]분이 필요하다.등교 마감 시간 X분 전에 도착해야한다.이때 등교 가능한 학생 중 등교 시간이 가장 오래 걸리는 학생의 등교 시간(S[i])를 구하는 문제이다.단, 어떤 학생도 등교할 수 없다면 -1을 출력해야한다.즉, 각 학생에 대해서 S[i] + T[i]의 값이 X 보다 작거나 같음을 만족하면, max_time을 업데이트 하는 방식으로 풀수 있다.코드# 백준 31962 - 등교# 분류 : 구현N, X = map(int, input().split())S = [0] * NT = [0] * Nfor i in range(N) : S[i], T[i] = ma..
백준 25377 - 빵 (파이썬)
백준 25377 - 빵 (파이썬)
2025.03.25https://www.acmicpc.net/problem/25377풀이N개의 빵 가게가 있으며, 각 가게에서의 두가지 정보가 주어진다.A[i] → 내가 가게에 도착할 수 있는 시간B[i] → 해당 가게에서 빵을 구매할 수 있는 시간조건 A[i] ≤ B[i]를 만족하는 가게 중에서 가장 빠르게 빵을 살 수 있는 시간을 찾아야한다.만약 해당하는 가게가 없다면 -1을 출력한다.시간 복잡도 분석입력 처리: O(N)최소값 탐색: O(N)총 시간 복잡도: O(N) (선형 탐색이므로 매우 효율적)코드# 백준 25377 - 빵# 분류 : 구현N = int(input())A = [0] * NB = [0] * Nfor i in range(N) : A[i], B[i] = map(int, input().split())..
백준 10800 - 컬러볼 (파이썬)
백준 10800 - 컬러볼 (파이썬)
2025.03.24https://www.acmicpc.net/problem/10800풀이각 공은 색 c와 크기 s를 가짐, 공을 하나 선택했을 때, 자신보다 크기가 작은 모든 공들 중 색이 다른 공들의 크기 합을 구해야 한다.최대 크기인 2000을 기준으로 balls[크기] = [(색, 인덱스)] 형태로 공을 저장한다.N = int(input())balls = [[] for _ in range(2001)]입력받은 공의 색(c)과 크기(s)를 balls 배열에 저장한다. (같은 크기의 공들을 묶어서 저장)for i in range(N): c, s = map(int, input().split()) balls[s].append((c, i))누적합 계산을 진행한다. 단 작은 크기부터 순회한다.for i in range..
백준 21756 - 지우개 (파이썬)
백준 21756 - 지우개 (파이썬)
2025.03.23https://www.acmicpc.net/problem/21756풀이주어진 N개의 숫자가 1부터 N까지의 정수로 구성된 큐에서 특정 규칙에 따라 제거되며 마지막 남는 숫자를 출력하는 문제이다.초기 큐 구성deque를 활용하여 1부터 N까지의 숫자를 큐에 추가한다.반복적인 삭제 과정큐의 길이가 1보다 클 동안 계속 반복한다현재 큐의 길이를 n이라 할때, 처음부터 시작하여 짝수 번째 인덱스에 있는 원소를 제거한다.홀수번째 인덱스에 있는 원소는 큐의 뒤로 이동시킨다.마지막 남은 숫자 출력시간복잡도 분석모든 원소를 한번씩 탐색함 → O(N)최적화 코드이 문제의 패턴을 관찰하면, 2의 거듭제곱 형태로 숫자가 감소함을 알 수 있다.즉, N이하의 가장 큰 2의 거듭제곱 수가 정답이 된다.N = int(input()..