백준 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..
백준 31823 - 악질 검거 (파이썬)
백준 31823 - 악질 검거 (파이썬)
2025.03.18https://boj.kr/31823 풀이각 사람의 이름과 함께 “.” 과 “*”로 이루어진 문자열이 제공된다.각 사람의 문자열에서 연속된 “.” 의 최대값을 구하고, 이를 기반으로 중복을 제거한 다양한 값의 개수를 출력해야한다.for i in range(N): S = input().split() name.append(S[-1]) # 이름 저장 S = S[:-1] # 이름을 제외한 문자열 리스트마지막 요소는 이름이름이므로, name.append(S[-1]) 을 통해서 따로 저장한다.S[:-1]을 통해서 나머지 부분을 따로 저장한다.max_count = 0count = 0for j in range(M): if S[j] == ".": count += 1 if S[j..
백준 16466 - 콘서트 (파이썬)
백준 16466 - 콘서트 (파이썬)
2025.03.17https://www.acmicpc.net/problem/16466풀이주어진 티켓 번호 배열에서 가장 작은 사용되지 않은 티켓번호를 찾는 문제이다.머너저 주어진 티켓 번호 리스트 A를 오름차순으로 정렬한다.그리고 티켓번호는 1번 부터 시작해야 하므로, 정렬된 배열에서 (인덱스 + 1)과 다른 값이 존재하는 경우, 그 값이 비어 있는 첫번째 티켓 번호이다.마지막 까지 비어있는 번호가 없으면 N + 1을 출력한다.시간 복잡도 분석정렬 : O(N Log N)탐색 : O(N)총 복잡도 : O(N Log N)코드# 백준 16466 - 콘서트# 분류 : 정렬N = int(input())A = list(map(int, input().split()))A.sort()found = Falsefor i in range(N)..
백준 16472 - 고냥이 (파이썬)
백준 16472 - 고냥이 (파이썬)
2025.03.17https://www.acmicpc.net/problem/16472풀이1️⃣ 문제 접근N 개 이하의 종류의 문자로 이루어진 가장 긴 연속 부분 문자열을 찾아야 한다..투 포인터 (start, end) 를 활용하여 슬라이딩 윈도우 방식으로 해결할 수 있다.2️⃣ 알고리즘 흐름초기 세팅count 배열을 사용하여 각 문자의 개수를 저장한다.num_types를 사용하여 현재 윈도우 내 문자의 종류 개수를 저장한다.start와 end 두 개의 포인터를 활용하여 윈도우 크기를 조정한다.슬라이딩 윈도우 실행end 포인터를 확장하면서 문자 개수를 업데이트한다.num_types가 N 이하일 경우, answer 값을 갱신한다.num_types가 N을 초과하면 start 포인터를 이동하여 윈도우를 조정한다.시간복잡도 분석e..
백준 23305 - 수강변경 (파이썬)
백준 23305 - 수강변경 (파이썬)
2025.03.16https://www.acmicpc.net/problem/23305풀이두 개의 리스트 A와 B가 주어지고, 학생들이 수강 신청을 변경할 때 최소한 몇 명이 원하는 강의를 듣지 못하는지를 구하는 문제이다.A : 원래 신청한 강의 목록B : 변경 후 원하는 강의 목록학생들은 강의를 교환할 수도 있지만, 모든 학생이 원하는 강의를 들을 수 없는 경우도 있다.최대한 많은 학생들이 원하는 강의를 들을 수 있도록 해야 하며, 듣지 못하는 학생 수를 출력한다.count = {}for i in range(N) : if A[i] not in count : count[A[i]] = [0, 0] count[A[i]][0] += 1count라는 딕셔너리를 생성하여 각 강의의 신청 수를 저장한다. not..
백준 31923 - 마라탕후루 (파이썬)
백준 31923 - 마라탕후루 (파이썬)
2025.03.16https://www.acmicpc.net/problem/31923풀이이 문제는 두 개의 리스트 A와 B를 주어진 연산을 통해 같게 만들 수 있는지를 판별하고, 가능하면 각 원소를 변환하는 횟수를 출력하는 문제이다.입력 설명N : 배열의 길이P, Q : 변환 연산에서 사용할 두 개의 숫자A : 초기 배열B : 목표 배열연산 규칙각 인덱스 i에서 A[i]에 (Q - P)의 배수를 더하거나 빼서 B[i]로 만들 수 있는지를 확인해야 한다.풀이 과정P와 Q가 같은 경우이 경우 (Q - P) = 0이므로 변환이 불가능하다.따라서 A와 B가 이미 같은지 확인 후 같다면 YES와 함께 변환 횟수 0을 출력하고, 다르면 NO를 출력한다.P와 Q가 다른 경우 (P P > Q라면 두 값을 바꾸고 A와 B를 서로 맞바꾼다..