Programming/백준
백준 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()..
백준 19941 - 햄버거 분배 (파이썬)
백준 19941 - 햄버거 분배 (파이썬)
2025.03.22https://www.acmicpc.net/problem/19941풀이그리디 알고리즘을 활용하여 P(사람)가 H(햄버거)를 최대한 많이 먹을 수 있도록 하는 문제이다.각 사람은 자신의 위치에서 왼쪽, 오른쪽 K칸 이내에 있는 햄버거를 먹을 수 있다.같은 햄버거를 여러명이 먹을 수 는 없다.최대 몇 명이 햄버거를 먹을 수 있는지 구해라.햄버거 위치를 우선순위 큐에 저장한다.문자열을 한번 순회하며 H의 위치를 pq에 저장한다.큐를 사용하면 햄머거를 오름차순으로 관리 할 수 있다.사람이 등장하면 가장 가까운 햄버거를 찾는다.P가 나오면 큐에서 H를 하나씩 꺼내서 사람이 먹을 수 있는 범위내에 있는지 확인한다.먹을 수 있으면 count += 1을 증가시키고, 다음 P로 넘어간다.만약 현재 H가 P의 범위를 벗어..
백준 17608 - 막대기 (파이썬)
백준 17608 - 막대기 (파이썬)
2025.03.21https://www.acmicpc.net/problem/17608풀이여러개의 막대기가 일렬로 세어져 있을 때, 오른쪽에서 보았을때 보이는 막대기의 개수를 구하는 문제이다.막대기는 왼쪽에서 오른쪽으로 나열되어 있으며, 각 막대기의 높이가 주어진다.오른쪽에서 왼쪽을 바라볼 때, 더 높은 막대기가 나오지 전까지의 막대기만 보이게 된다.for i in range(N - 1, -1, -1): # 오른쪽에서 왼쪽으로 순회 if max_height 오른쪽에서 왼쪽으로 막대기 리스트를 탐색한다.만약 현재 막대기의 높이가 max_height 보다 크다면, 이는 새로운 보이는 막대기 이므로, count를 증가시킨다.max_height를 현재 막대기의 높이로 갱신한다.시간 복잡도 분석한번의 순회만 이용하므로 O(N..
백준 17286 - 유미 (파이썬)
백준 17286 - 유미 (파이썬)
2025.03.20https://www.acmicpc.net/problem/17286풀이이 문제는 브루트포스를 활용하여 최소 이동 거리를 찾는 문제이다.주어진 네개의 좌표 중 첫번째 좌표에서 시작하여 나머지 세 좌표를 방문하는 모든 순열을 확인하며, 그중 최소 이동 거리를 찾는 방식이다.for permutation in permutations([1, 2, 3], 3):itertools.permutations([1, 2, 3] , 3)을 사용하여 첫 번째 좌표를 제외한 나머지 세 좌표의 모든 방문 순서를 생성한다.(1, 2, 3), (1, 3, 2), (2, 1, 3) 등 6가지가 존재x = X[0]y = Y[0]move = 0for i in permutation: move += (abs(x - X[i]) ** 2 +..
백준 30892 - 상어 (파이썬)
백준 30892 - 상어 (파이썬)
2025.03.19https://www.acmicpc.net/problem/30892풀이상어가 주어진 크기 T에서 시작하여, K번의 기회를 활용하여 먹이를 먹으며 성장하는 문제이다.주어진 먹이 리스트 A에서 적절한 먹이를 선택해 T를 최대한 티키우는것이 목표이다.즉, 그리디 알고리즘을 활용하여 해결할 수 있다. 먹이를 먹는 과정에서 가장 작은 먹이부터 차례로 선택하는 것이 유리하기 때문에 우선순위 큐를 활용한다.for _ in range(K): while pos A[pos]가 현재 T보다 작은 경우, 즉 먹을 수 있는 먹이를 pq에 넣는다.pq.put(-A[pos])를 통해 최대 힙을 구현한다.우선순위 큐는 기본적으로 최소 힙이므로 음수로 변환하여 최대 힙 처럼 사용하는 방식을 선택한다.시간 복잡도 분석A.sort(..
백준 31825 - 알파벳과 쿼리 (Easy)
백준 31825 - 알파벳과 쿼리 (Easy)
2025.03.18https://boj.kr/31825풀이문자열 S와 쿼리 개수 Q가 주어진다.두가지 유형의 쿼리가 존재한다.연속된 다른 문자 개수 세기 (t = 1)구간 [l, r]에서 연속하는 문자 그룹을 찾아 개수를 출력.알파벳 증가 (t = 2)구간 [l, r]에서 문자들을 다음 알파벳으로 변경 (Z → A)if t == 1: count = 0 for i in range(l, r): if S[i] != S[i + 1]: # 인접한 문자가 다르면 count 증가 count += 1 print(count + 1)인접한 문자들을 비교하면서 바뀌는 부분이 있는지 체크.구간 [l, r]에서 연속된 블룩 개수 = count + 1로 출력if t == 2: for i in..