Programming/백준
백준 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값을 더 크게 ..
백준 2503 - 숫자 야구 (파이썬)
백준 2503 - 숫자 야구 (파이썬)
2025.03.09https://www.acmicpc.net/problem/2503풀이각 숫자는 1~9까지의 서로 다른 세 자리 수로 이루어진다.상대가 제시한 숫자에 대해 스트라이크(Strike)와 볼(Ball)의 개수를 보고 정답을 유추해야 한다.스트라이크: 같은 자리에서 같은 숫자가 있을 때 증가.볼: 다른 자리에 있지만 존재하는 숫자가 있을 때 증가.브루트포스 알고리즘 이용가능한 모든 세 자리 숫자 조합(순열, permutation) 을 만든다.입력된 모든 질문(qna)과 비교하여 조건을 만족하는 경우만 카운트한다.count = 0for permutation in permutations(range(1, 10), 3): good = True for i in range(len(qna)): stri..
백준 17944 - 퐁당퐁당 1 (파이썬)
백준 17944 - 퐁당퐁당 1 (파이썬)
2025.03.08https://www.acmicpc.net/problem/17944 풀이특정 규칙을 따라 숫자가 증가하고 감소하는 패턴을 이루는 수열에서 특정 위치의 값을 찾는 문제이다.예를 들어, N = 3 일 때, 수열의 형태는 다음과 같다.1, 2, 3, 4, 5, 6, 5, 4, 3, 2이 패턴은 아래와 같이 형성1부터 2N 까지 증가2N-1 부터 2까지 감소시간 복잡도 분석리스트 A 의 길이는 4N - 2 이므로, 리스트 생성에 O(N) 의 시간이 소요이후의 연산(인덱스 조회 및 나머지 연산)은 O(1) 이므로, 전체 시간 복잡도는 O(N)하지만 T 의 크기가 클 경우에도 나머지 연산을 통해 효율적으로 값을 찾을 수 있어 T 가 커질 때도 성능이 저하되지 않는다.코드# 백준 17944 - 퐁당퐁..
백준 17952 - 과제는 끝나지 않아! (파이썬)
백준 17952 - 과제는 끝나지 않아! (파이썬)
2025.03.07https://www.acmicpc.net/problem/17952풀이문제 이해교수님이 과제를 주는데, 과제 수행 도중 새로운 과제가 주어질 수도 있다.학생은 현재 수행 중인 과제를 잠시 미뤄두고 새로운 과제를 시작해야 한다.한 번의 작업이 끝나면, 수행 중이던 과제를 이어서 해야 한다.만약 과제가 끝나면 점수를 얻게 된다.모든 과제가 끝난 후 얻은 총 점수를 출력하는 문제이다.과제 수행 로직info[0] == 1 → 새로운 과제 주어짐과제 점수 a, 소요 시간 t를 입력받는다.만약 t == 1이면 즉시 완료되므로 score에 a를 추가한다.그렇지 않다면 (a, t-1)을 스택에 저장한다.info[0] == 0 → 현재 진행 중인 과제 수행스택이 비어 있지 않다면, 가장 최근의 (a, t)를 pop()t..
백준 19598 - 최소 회의실 개수 (파이썬)
백준 19598 - 최소 회의실 개수 (파이썬)
2025.03.06https://www.acmicpc.net/problem/19598풀이N = int(input())courses = []for _ in range(N): start, end = map(int, input().split()) courses.append((start, end))courses.sort()N개의 회의 일정이 주어지므로, (시작 시간, 종료 시간) 튜플을 리스트 courses에 저장시작 시간을 기준으로 정렬하여, 빠른 시간에 시작하는 회의를 먼저 처리from queue import PriorityQueuepq = PriorityQueue()pq.put(courses[0][1]) # 첫 번째 회의의 종료 시간을 큐에 삽입count = 1 # 필요한 회의실 개수최소 힙(우선순위 큐)을 ..
백준 1300 - K번째 수 (파이썬)
백준 1300 - K번째 수 (파이썬)
2025.03.06https://www.acmicpc.net/problem/1300풀이문제 조건N×N 크기의 배열 A가 있음.A[i][j] = i × j 로 채워져 있음.이 배열을 일차원 배열로 변환하고 정렬했을 때, K번째로 작은 수를 찾아야 함.mid 값 기준으로 몇 개의 원소가 작은지 확인mid 값보다 작거나 같은 원소 개수를 구해 count 값으로 활용.특정 수 X보다 작은 원소의 개수를 구하는 방법A[i][j] = i * j 이므로 i번째 행에서 X 이하의 수 개수 = min(N, (X - 1) // i)모든 i (1~N)에 대해 누적하여 개수를 세면 된다.K와 비교하여 mid 조정count count >= K 이면 mid가 충분히 크므로 high를 줄임.시간 복잡도 분석이분 탐색의 탐색 범위: 1 ~ N*N →..
백준 1303 - 전쟁 - 전투 (파이썬)
백준 1303 - 전쟁 - 전투 (파이썬)
2025.03.06https://www.acmicpc.net/problem/1303풀이이 문제는 BFS로 해결이 가능하다.주어진 전장 지도에서 각 팀의 전투력을 계산하는 문제이며, 전투력은 같은 팀의 병사가 상하좌우로 연결된 병사들의 수의 제곱으로 계산된다.방문 여부를 저장하는 visit 리스트같은 병사가 중복 탐색되지 않도록 하기 위해 사용BFS를 활용하여 같은 색상의 병사를 탐색queue에 시작 병사의 좌표를 넣고 탐색같은 색상이면서 방문하지 않은 병사들을 queue에 추가하면서 탐색을 확장탐색이 끝나면 해당 병사의 그룹의 크기를 count * count로 계산하여 result에 추가시간 복잡도 분석각 병사를 한 번만 방문하므로O(N * M), 즉 주어진 전장의 크기만큼 수행BFS로 탐색하여 같은 팀 병사들을 묶으므로..
백준 14719 - 빗물 (파이썬)
백준 14719 - 빗물 (파이썬)
2025.03.05https://www.acmicpc.net/problem/14719풀이주어진 블록 배치에서 빗물이 고이는 양을 구하는 문제이다.문제에서는 2차원 격자를 생성해서 풀어야 하기 떄문에 다음과 같이 선언하였다.B = [[0] * W for _ in range(H)]블록을 채우기 위해서 다음과 같이 수행한다.for i in range(H) : for j in range(A[i]) : B[H - 1 - j][i] = 1각 열(i)에서 블록의 높이만큼(A[i]) 1을 채운다.(H - 1 - j, i) 위치를 1로 설정해서 바닥부터 쌓이도록 만든다.빗물을 계산하기 위해서 다음과 같이 수행한다.count = 0for i in range(H): for j in range(W): if ..
백준 17086 - 아기 상어 2 (파이썬)
백준 17086 - 아기 상어 2 (파이썬)
2025.03.04https://www.acmicpc.net/problem/17086풀이입력 처리N, M = map(int, input().split())A = [[] for _ in range(N)]for i in range(N): A[i] = list(map(int, input().split()))N, M을 통해서 맵의 크기를 입력 받고,A배열에는 N * M 크기의 2차원 리스트를 생성하여, 각 좌표에 대한 정보를 저장하기 위해 사용BFS 탐색을 위한 초기 설정visit = [[False] * M for _ in range(N)]dist = [[-1] * M for _ in range(N)]queue = deque()visit : 방문 여부를 저장하는 2차원 리스트 (True : 방문함, False : 방문 안 ..