백준 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를 서로 맞바꾼다..
백준 31844 - 창고지기 (파이썬)
백준 31844 - 창고지기 (파이썬)
2025.03.16https://www.acmicpc.net/problem/31844풀이문제 이해를 하면 다음과 같다문자열 S를 입력받기변수 robot과 goal을 각각 -1로 초기화하고, order 리스트를 생성문자열을 순회하며 다음을 수행'@', '#', '!' 문자일 경우, 이를 order 리스트에 추가'@'이면 robot에 해당 인덱스를 저장'!'이면 goal에 해당 인덱스를 저장두 번째로 등장한 문자가 '#'인지 확인하고, 맞다면 robot과 goal 사이의 거리에서 1을 뺀 값을 출력아니라면 -1을 출력한다.코드# 백준 31844 - 창고지기# 분류 : 구현S = input()robot = -1goal = -1order = []for i in range(len(S)) : if S[i] in ['@', '#..
백준 17219 - 비밀번호 찾기
백준 17219 - 비밀번호 찾기
2025.03.15https://www.acmicpc.net/problem/17219풀이이것도,, 실버 4 문제라고 하기엔 문제가 있을지도,, 정말 간단한 구현 문제이다.N, M 의 정수를 입력 받고, 비밀번호 딕셔너리를 하나 만들어서, 들어온 사이트와 비밀번호를 바로 딕셔너리에 저장한다.그리고, M만큼 입력받으면서 바로 딕셔너리에서 접근한다.간단한 문제지만, C, JAVA 등을 사용한다면 아마 시간 접근에서 오답이 생길 가능성이 높은 문제인것 같다.해당 문제의 시간 제한은 5초이다. 파이썬으로 100,000개의 데이터를 처리할 때, O(N)을 해도 충분히 넉넉한 시간이다.코드# 백준 17219 - 비밀번호 찾기# 분류 : 구현N, M = map(int, input().split())password_lists = {}fo..
백준 9375 - 패션왕 신해빈 (파이썬)
백준 9375 - 패션왕 신해빈 (파이썬)
2025.03.15https://www.acmicpc.net/problem/9375풀이이 문제는 조합을 활용하여 해결 할 수 있는 문제이다.주어진 의상의 종류별로 착용할 수 있는 경우의 수를 계산하여 모든 조합을 구하는 방식이다.쉽게 설명하기 위해서, 예시를 바탕으로 분석을 진행한다.23hat headgearsunglasses eyewearturban headgear3mask facesunglasses facemakeup face첫 번째 테스트 케이스count = { "headgear": 2, "eyewear": 1}경우의 수 : (2 + 1) * (1 + 1) - 1 = 5두 번째 테스트 케이스count = { "face": 3}경우의 수: (3+1) - 1 = 3시간 복잡도 분석N개의 의상을 입력받고 ..
백준 21758 - 꿀 따기 (파이썬)
백준 21758 - 꿀 따기 (파이썬)
2025.03.14https://www.acmicpc.net/problem/21758풀이누적합 배열을 사용하며, 벌과 꿀통의 배치를 최적화하여 최대 꿀 수확량을 계산하는 문제이다.먼저 누적합 계산을 위해서 초기화를 진행한다.psum = [0] * Nfor i in range(N): if i == 0: psum[i] = A[i] else: psum[i] = psum[i - 1] + A[i]첫번째 경우 (벌이 양 끝, 꿀통이 중간한 가정)첫번째 벌은 0번 위치 (A[0])두번째 벌은 N - 1번 위치 (A[N - 1])꿀통은 중간에 있는 최대 꿀량의 벌통max(A[1:-1]) → (첫 번째와 마지막을 제외한 부분에서 최댓값)answer = psum[N - 2] - psum[0] + max(..
백준 1302 - 베스트셀러 (파이썬)
백준 1302 - 베스트셀러 (파이썬)
2025.03.13https://www.acmicpc.net/problem/1302풀이진짜 어마어마 하게 쉬운문제이다.N개의 책 제목이 주어질 때, 가장 많이 팔린 책의 제목을 출력하되, 여러 개라면 사전순으로 가장 앞서는 제목을 출력하는 문제이다.시간 복잡도 분석N개의 책 제목을 입력받으면서 딕셔너리에 저장하는 과정 → O(N)count.items()를 순회하면서 최대값을 찾는 과정 → O(M)최악의 경우 O(N + M) 이기에 매우 효율적코드# 백준 1302 - 베스트셀러# 분류 : 문자열, 정렬N = int(input())count = {}for _ in range(N) : title = input() if title not in count : count[title] = 0 count[t..
백준 1092 - 배 (파이썬)
백준 1092 - 배 (파이썬)
2025.03.12https://www.acmicpc.net/problem/1092풀이크레인을 이용해서 박스를 옮기는 문제이다.각 크레인은 특정한 무게까지의 박스를 들 수 있으며, 최소 시간 내에 모든 바스를 옮기는 것이 목표이다.먼저 A, B 를 입력 받고, 각 박스를 각각 내림차순으로 정렬하여, 가장 무거운 박스를 가장 무거운 크레인부터 배치할 수 있도록 변경한다.if A[0] 그리고 만약 가장 강한 크레인이 가장 무거운 박스를 들 수 없다면, 모든 박스를 옮기는 것이 불가능 하므로, -1을 출력한다.count = 0while len(B) > 0 : for a in A : if len(B) > 0 and a 각 크레인은 들 수 있는 가장 무거운 박스를 찾고 제거한다.그리고 모든 크레인이 한 번씩 돌고..
백준 2075 - N번째 큰 수 (파이썬)
백준 2075 - N번째 큰 수 (파이썬)
2025.03.11https://www.acmicpc.net/problem/2075풀이문제의 핵심은 메모리 초과이다 N * N 크기의 행렬을 모두 메모리에 저장만 하더라도 메모리 초과가 일어나기 때문이다.이를 효율적으로 처리하기 위해 우선순위 큐를 사용해 효율적으로 해결한다.행령을 읽어, 읽어온 각 숫자를 처리하며, 각각의 방식으로 힙을 유지한다.힙 크기가 N보다 작은 경우그냥 heapq.heappush()로 추가힙 크기가 N과 같거나 큰 경우만약 현재 힙의 최솟값 보다 큰 숫자가 들어오면, heapq.heappush()를 통해 추가한 후, heapq.heappop()으로 가장 작은 수를 제거하여 힙 크기를 N개로 유지한다.시간 복잡도입력이 N*N이므로 총 N^2개의 숫자를 처리해야한다,각 숫자에 대해 heappush()..
백준 16439 - 치킨치킨치킨
백준 16439 - 치킨치킨치킨
2025.03.11https://www.acmicpc.net/problem/16439풀이N명의 사람들이 M가지의 치킨을 평가한 점수표가 주어진다.각각의 사람은 M가지 치킨에 대한 선호도를 숫자로 나타낸다.3가지 치킨을 선택했을 때, 사람들이 가장 좋아하는 치킨 중 최대값을 모두 합한 값이 최대가 되도록 해야 한다.브루트포스 알고리즘을 사용해서 해결 할 수 있다.가능한 모든 3가지 치킨 조합을 확인하고, 각 조합에 대해 점수를 계산하여 최대 값을 찾는다.모든 M개의 치킨 중 3개를 선택하는 조합을 combination으로 가져온다.N명의 사람들에 대해, 선택된 3개의 치킨 중 가장 높은 점수를 max_like에 저장하고, 이를 sum에 추가한다.모든 조합을 돌면서 최대 sum값을 max_sum에 저장한다.코드# 백준 164..
백준 17255 - N으로 만들기 (파이썬)
백준 17255 - N으로 만들기 (파이썬)
2025.03.10https://www.acmicpc.net/problem/17255풀이문제의 핵심은 주어진 숫자 N을 만들 수 있는 가능한 순서열을 모두 찾아 그 개수를 세는 것이다.여기서는 재귀적 브루트포스 기법을 활용하여 주어진 숫자 N을 만들 수 있는 모든 경우를 탐색하는 방식을 사용한다.재귀 함수를 구현하였고, 해당 재귀함수의 기능은 다음과 같다.n이 현재까지 만들어진 숫자 문자열N을 만들수 있는 모든 방법을 재귀적으로 탐색한다.n == N 을 통해서 현재 n이 N과 같다면 하나의 유효한 방법을 찾은 것이므로 1을 반환한다.N.find(n) == -1 을 통해서 n이 N에 포함되지 않는 부분 문자열이면 더 탐색할 필요가 없기에 0을 반환한다.n의 앞 또는 뒤에 숫자 i(0~9)를 추가한 left와 right을 만..
백준 13164 - 행복 유치원 (파이썬)
백준 13164 - 행복 유치원 (파이썬)
2025.03.10https://www.acmicpc.net/problem/13164풀이N명의 원생이 있고, 키가 오름차순으로 주어진다.이 원생들을 K개의 조로 나누려고 한다.각 조에서 가장 키가 큰 원생과 작은 원생의 차이가 해당 조의 비용전체 비용의 합을 최소화 하는것이 문제 풀이의 요점그리디 알고리즘을 이용해서 해결할 수 있다.키 차이 계산원생들은 이미 정렬되어 있다.연속한 원생들끼리의 키 차이를 구한다.D[i] = A[i + 1] - A[i] (N - 1개의 차이 값)큰 차이부터 제거처음 모든 원생을 하나의 그룹으로 묶었을 때, 비용은 전체 키 범위인 A[N - 1] - A[0] 이다.조를 K개로 나누려면, K - 1번 끊어야한다.따라서 키 차이 배열 D에서 가장 큰 값부터 (K - 1)개를 제거하면 비용이 최소화..
백준 17951 - 흩날리는 시험지 속에서 내 평점이 느껴진거야 (파이썬)
백준 17951 - 흩날리는 시험지 속에서 내 평점이 느껴진거야 (파이썬)
2025.03.09https://www.acmicpc.net/problem/17951풀이이분 탐색을 활용해서 시험지 점수 리스트 A를 K개의 그룹으로 나눌 때, 각 그룹의 최소 점수 합 중 최대값을 찾는 문제이다.문제를 이해하면,N개의 시험지 점수가 주어진다.이 점수들은 연속된 그룹으로 K개 이상으로 나눠야한다.그룹의 최소 점수 합이 최대한 커지도록 만든다.일반적인 풀이로는 시간이 많이 걸리므로, 이분 탐색을 활용해 효율적으로 풀이한다.이분 탐색 대상mid 값은 각 그룹의 최소 점수 합 중 최댓값을 의미한다.low = 0, high = 20 * 100000 / 시험지 개수 최대값이 10^5이므로, 가능한 최대 점수로 정의한다.이분 탐색 과정mid 값을 기준으로 그룹을 나눈다.그룹의 개수가 K이상이면, mid값을 더 크게 ..