프로그래머스 - 택배 상자 꺼내기 (파이썬)
프로그래머스 - 택배 상자 꺼내기 (파이썬)
2025.03.26https://school.programmers.co.kr/learn/courses/30/lessons/389478?language=python3 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이다른 사람 풀이를 보고 한숨을 쉬었던 문제이다..def solution(n, w, num): m1 = num%(w*2) m2 = ((w*2+1) - m1)%(w*2) # num 이상 n 이하의 수들 중 2*w로 나눈 나머지가 m1,m2인 것들의 수를 세면 된다. return len(range(num,n+1,w*2)) + len(range(num + (m2-m1)%(w*2), n+1, w*2..
백준 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())..
[프로그래머스] 달리기 경주
[프로그래머스] 달리기 경주
2025.03.24https://school.programmers.co.kr/learn/courses/30/lessons/178871 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr오랜만에 프로그래머스 풀이를 진행하였다..풀이이문제는 단순하게 덤볐다가 시간초과가 나는 문제이다..Python 내장 함수 index는 시간 복잡도가 O(N)이기 때문에 조심해서 사용해다 한다는 점을 다시한번 생각하게 되는 문제이다.처음에 시간 초과가 난 코드는 단순하게 index의 위치를 탐색해 SWAP 하는 코드를 짰지만 68점 밖에 얻을 수 없었다.조금더 시간을 효율적으로 사용하기 위해서, dictionary를 통해 구현을 진행하였다.기존과..
백준 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..