백준 2495 - 연속구간 (파이썬)
백준 2495 - 연속구간 (파이썬)
2025.04.02https://www.acmicpc.net/problem/2495풀이이 문제는 0과 1로 이루어진 문자열이 세 줄 주어졌을 때, 각 줄에서 같은 숫자가 연속으로 등장하는 가장 긴 길이를 구하는 문제이다.예를 들어, “0001000”이라는 문자열에서는 0이 최대 3번 연속으로 등장하므로 정답은 3이 된다.문자열을 앞에서부터 한 글자씩 확인하면서, 이전 문자와 같은지 비교한다.만약 현재 문자가 이전 문자와 같다면, 현재 연속 길이(count)를 1 증가시킨다.반대로 다르다면, 연속이 끊긴 것이므로 count를 1로 초기화한다.매 반복마다 지금까지의 최대 연속 길이(max_count)를 갱신다.문자열을 모두 확인한 후, 해당 줄의 최대 연속 길이를 출력한다.시간 복잡도 분석각 줄에 대해 한번 씩 문자열을 순회..
백준 2456 - 나는 학급회장이다 (파이썬)
백준 2456 - 나는 학급회장이다 (파이썬)
2025.04.01https://www.acmicpc.net/problem/2456풀이투표는 여러 명의 학생들이 진행하며, 각 사람은 1번, 2번, 3번 후보에게 1~3점 중 하나씩 점수를 준다.가장 총점이 높은 사람이 회장이 됨.동점일 경우에는 다음 우선순위로 결정.3점을 더 많이 받은 후보2점을 더 많이 받은 후보그래도 같으면 무효처리 (0)코드# 백준 2456 - 나는 학급회장이다# 분류 : 구현N = int(input())score = [0] * 3count_3 = [0] * 3count_2 = [0] * 3for _ in range(N) : s = list(map(int, input().split())) for i in range(3) : score[i] += s[i] if s..
백준 2491 - 수열 (파이썬)
백준 2491 - 수열 (파이썬)
2025.03.31https://www.acmicpc.net/problem/2491풀이어떤 수열이 주어졌을 때, 연속적으로 커지거나 같거나, 혹은 작아지거나 같은 부분 수열 중 가장 긴 길이를 구하는 문제이다.비내림차순 수열의 최대 길이 계산비오름차순 수열의 최대 길이 계산위 두 결과 중 최대값을 출력A[: : -1] 로 뒤집어서 감소하거나 같은 부분 수열을 구할 수 있도록 바꾼다.시간복잡도 분석비내림차순 수열의 계산 → O(N)비오름차순 수열의 계산 → O(N)즉, O(N)코드# 백준 2491 - 수열# 분류 : 구현N = int(input())A = list(map(int, input().split()))max_count = 1count = 1for i in range(1, N) : if A[i- 1]
백준 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..
프로그래머스 - 배달 (파이썬)
프로그래머스 - 배달 (파이썬)
2025.03.30https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이N개의 마을(1번부터 N번), roads는 [마을 A, 마을 B, 걸리는 시간] 형태의 리스트고, 음식 배달은 1번 마을에서 시작한다.K시간 이하로 배달 가능한 마을 수를 구해야한다.1번 마을을 시작점으로 해서 모든 마을까지의 최단 거리를 구한다. 여기서는 다익스트라 알고리즘을 사용한다.구한 거리 중에서 K이하인 마을 개수를 세면 정답이다.시간 복잡도 분석도로수 E, 마을 수 N즉, O((N + E) Log N)코드import heapqfr..
프로그래머스 - 마법의 엘리베이터 (파이썬)
프로그래머스 - 마법의 엘리베이터 (파이썬)
2025.03.29분류 : 그리디링크 : https://school.programmers.co.kr/learn/courses/30/lessons/148653풀이엘리베이터가 버튼을 눌러 층을 이동하는데,위층으로 1칸, 아래층으로 1칸 이동이 가능하고, +10, +100 등도 가능하다.목표층에서 0층으로 이동하는 최소 버튼 횟수를 구하는 문제이다.즉, 각 자릿수를 기준으로 반올림 또는 내림하여 효율적인 방법으로 움직이는 그리디 알고리즘 문제이다.while storey > 0 : digit = storey % 10 next_digit = (storey // 10) % 10현재 숫자를 1의 자리부터 확인하면서, 다음 자릿수가 4 이상인지 여부에 따라 반올림 할지 내릴지 결정한다.if digit > 5 or (digit..
백준 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())..
[프로그래머스] 달리기 경주
[프로그래머스] 달리기 경주
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..