[골드 3] 백준 2616 - 소형기관차 (파이썬)
[골드 3] 백준 2616 - 소형기관차 (파이썬)
2025.04.20https://www.acmicpc.net/problem/2616풀이열차는 각 객차마자 탑승 인원이 주어져있다.한번에 K개의 객차만을 끌 수 있다.최대 3번까지 소형 기관차 운행이 가능하다.최대한 많은 승객을 운송하는 것이 목표이다.먼저 입력 및 누적합을 계산한다.N = int(input()) # 객차 수A = list(map(int, input().split())) # 각 객차에 탄 승객 수K = int(input()) # 소형 기관차가 끌 수 있는 객차 수psum = [0] * Npsum[0] = A[0]for i in range(1, N): psum[i] = psum[i - 1] + A[i]psum[i]는 0부터 i번째까지의 누적합이다.구간 합 A[i - K + 1] … + A[i]는 p..
[골드 2] 백준 1135 - 뉴스 전하기 (파이썬)
[골드 2] 백준 1135 - 뉴스 전하기 (파이썬)
2025.04.19https://www.acmicpc.net/problem/1135풀이회사에는 N명의 직원이 있고, 0번 직원이 사장이다.각 직원은 한 명의 상사를 가지고 있다. (par[i]가 i번 직원의 상사)뉴스는 각 사장(0번)부터 시작해서 전파되며, 각 직원은 동시에 한명에게만 뉴스 전달을 시작할 수 있다.모든 직원이 뉴스를 전달받기까지 걸리는 최소 시간을 구하는 문제이다.문제는 트리 형태의 구조에서, 루트 노드로부터 모든 노드에게 최대한 빠르게 뉴스를 전파하는 방식으로 시간을 최소화하는 것이다.서브트리들 간의 전파 순서에 따라 시간 차이가 발생하므로, 더 오래 걸리는 자식부터 먼저 처리하는 것이 유리하다.child = [[] for _ in range(N)]for i in range(1, N): child..
[브론즈 1] 백준 1333 - 부재중 전화 (파이썬)
[브론즈 1] 백준 1333 - 부재중 전화 (파이썬)
2025.04.19https://www.acmicpc.net/problem/1333풀이N개의 노래가 재생되고, 각 노래는 L초 동안 재생된다.각 노래가 끝난 후에는 5초의 쉬는 시간이 있다.민식이는 D초마다 전화를 걸며, 노래가 나오지 않을 때만 전화를 받는다.민식이가 전화를 받을 수 있는 가장 빠른 시간을 출력해야한다.check = [False] * 50000에서 4999초까지의 시간 동안 노래가 재생되는지 여부를 저장한다.True 라면 노래가 재생중인 상태이다.index = 0for _ in range(N) : for _ in range(L) : check[index] = True index += 1 for _ in range(5) : index += 1각 노래의 재생 ..
[실버 3] 백준 8911 - 거북이 (파이썬)
[실버 3] 백준 8911 - 거북이 (파이썬)
2025.04.19https://www.acmicpc.net/problem/8911풀이거북이는 F, B, L, R 네 가지 명령어를 받아서 움직인다.시작 위치는 (0,0), 시작방향은 북쪽이다.각 명령어를 수행한 후 거북이가 지나간 경로에서의 가장 큰 직사각형 넓이를 구하는 문제이다.directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]방향 배열을 먼저 설정한다. 각각 동, 북, 서, 남의 방향을 나타낸다.did는 현재 바라보는 방향의 인덱스이며, 처음에는 북쪽이므로 1로 지정한다.if s == "L": did = (did + 1) % 4if s == "R": did = (did + 3) % 4왼쪽 회전 : 90도 반시계 → 인덱스 + 1오른쪽 회전 : 90도 시계 → 인덱스 - ..
[골드 5] 백준 13549 - 숨바꼭질 3 (파이썬)
[골드 5] 백준 13549 - 숨바꼭질 3 (파이썬)
2025.04.18https://www.acmicpc.net/problem/13549풀이다익스트라 알고리즘을 이용해서 풀 수 있다.이 문제는 가중치가 0 또는 1인 그래프에서 최단 시간을 구하는 문제이다.문제를 확인하면 다음과 같은 정보를 확인 할 수 있다.수빈이는 현재 위치 N, 동생의 위치는 K이다.수빈이는 다음 3가지 방법으로 이동 가능하다.x - 1 = 1초x + 1 = 1초2 * x = 0초즉, 0초짜리 이동이 존재하는 가중치 0과 1의 그래프이므도, 일반 BFS보다는 0-1 BFS 또는 다익스트라가 적합하다.adj = [[] for _ in range(200001)]문제에서 최대 위치가 200000이므로, 0부터 200000까지 정점으로 보고 인접 리스트를 초기화한다.범위를 넉넉하게 잡은 이유는 2 * X 가 ..
[실버 1] 백준 1932 - 정수 삼각형 (파이썬)
[실버 1] 백준 1932 - 정수 삼각형 (파이썬)
2025.04.18https://www.acmicpc.net/problem/1932풀이정수로 이루어진 삼각형이 주어질 떄, 맨 위에서부터 아래로 내려가면서 선택한 수의 합이 최대가 되도록 경로를 찾는 문제이다.한 칸 아래로 이동할 떄는 바로 아래 또는 바로 아래 오른쪽으로만 이동할 수 있다.N = int(input()) # 삼각형의 높이A = [list(map(int, input().split())) for _ in range(N)] # 삼각형 데이터A는 삼각형 형태의 숫자 배열이다.D = [[0] * (i + 1) for i in range(N)]D[0][0] = A[0][0]D[i][j]는 i번째 줄, j번째 위치까지 올 때 최대 합을 저장하는 DP테이블이다.첫번째 숫자는 그대로 초기화한다.for i in rang..
[실버 2] 백준 11053 - 가장 긴 증가하는 부분 수열 (파이썬)
[실버 2] 백준 11053 - 가장 긴 증가하는 부분 수열 (파이썬)
2025.04.17https://www.acmicpc.net/problem/11053풀이이 문제는 조금 복잡하다… 일단 다이나믹 프로그래밍 풀이로 작성하였는데, 일반적인 풀이보다 2차원 DP를 활용한 조금은 특이한 방식이다.일단 문제는 수열 A가 주어졌을때, 증가하는 부분 수열 중 가장 길이가 긴 것의 길이를 구하는 문제이다.D = [[0] * 1001 for _ in range(N)] # N * 1001D[i][j] 는 i번째까지 고려했을때, 마지막 수가 j이하인 증가 부분 수열의 최대 길이이다.for i in range(1001): D[0][i] = 1 if A[0] 첫번째 원소만 쓸 수 있는 상황에서 j 조건을 만족하면 길이는 1로 지정한다.for i in range(1, N): for j in range..
[골드 4] 백준 1976 - 여행 가자 (파이썬)
[골드 4] 백준 1976 - 여행 가자 (파이썬)
2025.04.17https://www.acmicpc.net/problem/1976풀이N개의 도시가 있고, 어떤 도시끼리는 도로로 연결되어 있다.M개의 도시가 주어진 여행 계획에 포함되어 있다.주어진 도시들이 모두 같은 연결 요소에 속해 있다면 여행이 가능하다.연결 정보는 인접 행렬로 주어진다.이 문제는 그래프 연결 요소 판별 문제이다.BFS를 통해 각 도시가 어떤 연결 요소에 속해 있는지 visit 배열에 저장하고여행 계획에 포함된 도시들이 모두 같은 연결 요소에 속해 있는지를 확인한다.하나라도 다르면 NO, 모두 같으면 YES를 출력한다.N = int(input()) # 도시 수M = int(input()) # 여행에 포함된 도시 수adj = [[] for _ in range(N)]for i in range(N..
[브론즈 1] 백준 1526 - 가장 큰 금민수 (파이썬)
[브론즈 1] 백준 1526 - 가장 큰 금민수 (파이썬)
2025.04.17https://www.acmicpc.net/problem/1526풀이금민수란 숫자는 4또는 7로만 이루어진 수이다. 입력으로 주어지는 N이하의 수 중에서 가장 큰 금민수를 출력하는 문제이다.결국, 1~6자리의 모든 금민수를 생성하고, 그중 N이하인 것 중 가장 큰 수를 찾는다.이 문제는 6자리 이하의 숫자만 고려하면 되므로, 완전탐색으로 충분히 해결 할 수 있다.for i in range(1, 7): # 자릿수: 1~6자리 for j in range(i + 1): # 7을 넣을 자리 개수 for combination in combinations(range(i), j): kms = 0 for k in range(i): ..
[실버 3] 백준 1904 - 01타일 (파이썬)
[실버 3] 백준 1904 - 01타일 (파이썬)
2025.04.16https://www.acmicpc.net/problem/1904풀이길이가 N인 이진 문자열 중 1 또는 00만 사용해서 만들 수 있는 경우의 수를 구하는 문제이다.1 또는 00만 사용해서 N자리 수를 만들 수 있는 경우의 수 = 피보나치 수열길이가 N일때 만들 수 있는 경우의 수를 D[n]이라고 할때,D[N - 1] 뒤에 “1”을 붙으면 길이 N이 된다.D[N - 2] 뒤에 “00”을 붙이면 길이 N이 된다.즉 점화식은 다음과 같다.✅ D[N] = D[N - 1] + D[N - 2]초기값을 1, 2로 미리 초기항을 설정한다.최대 N이 1,000.000이므로 충분히 크게 초기화 하고, 중간에 나머지 연산을 해줘야 오버플로우를 방지 할 수 있기에, 매 실행시 mod로 나머지 연산을 해준다.시간 복잡도 분석..
[골드 5] 백준 15686 - 치킨 배달 (파이썬)
[골드 5] 백준 15686 - 치킨 배달 (파이썬)
2025.04.15https://www.acmicpc.net/problem/15686풀이도시에는 집(1)과 치킨집(2)가 있고, 나머지는 (0)으로 빈칸이다.최대 M개의 치킨집만 선택해서 영업해야하며, 모든 집은 가장 가까운 치킨집까지의 거리로 만족한다.모든 지들의 치킨 거리의 합이 최소가 되도록 M개의 치킨집을 선택해야한다.N, M = map(int, input().split())C = [list(map(int, input().split())) for _ in range(N)]N, M, C는 도시의 크기, 영업할 치킨집 수, 도시 지도 정보를 나타낸다.house = []chicken = []for i in range(N): for j in range(N): if C[i][j] == 1: ..
[실버 5] 백준 23253 - 자료구조는 정말 최고야 (파이썬)
[실버 5] 백준 23253 - 자료구조는 정말 최고야 (파이썬)
2025.04.15https://www.acmicpc.net/problem/23253풀이총 N개의 책을 M개의 스택에 나눠담았다. 각 스택에는 책들이 위에서부터 아래로 순서대로 쌓여있다. 이 스택들을 하나씩 꺼내 맨 위 책부터 한권씩 빼서 한 줄로 정렬할 수 있다면 Yes, 아니면 No를 출력한다.정렬 조건은 항상 앞 책 번호가 뒤 책번호보다 커야한다.즉, 각 스택마다 위에서 아래 방향으로 책 번호가 내림차순인지 확인하고, 한 스택이라도 오름차순 형태가 있으면 젠체적으로 정렬이 불가능하므로 No를 출력한다.코드# 백준 23253 - 자료구조는 정말 최고야# 분류 : 구현import sysinput = sys.stdin.readlineN, M = map(int, input().split())possible = Truefor..
[골드 4] 백준 17298 - 오큰수 (파이썬)
[골드 4] 백준 17298 - 오큰수 (파이썬)
2025.04.15https://www.acmicpc.net/problem/17298풀이주어진 수열에서, 각 원소에 대해 오른쪽에 있으면서 자기보다 큰 수 중 가장 왼쪽에 있는 수를 말한다. 없으면 -1을 출력한다.for i in range(N - 1, -1, -1): while len(stack) > 0 and stack[-1] 1: answer[i] = stack[-2]stack에는 값이 저장되고 있고, 그것을 기반으로 stack[-2]를 사용하고 있는데, 이는 오큰수를 정확히 보장하지 않는다. 왜냐하면 stack[-2]는 항상 stack[-1] 보다 작거나 같다는 보장이 없고, 해당 원소 A[i]보다 큰 가장 가까운 오른쪽 값이 아닐 수도 있다.예를 들어 A = [2, 1, 3] 일때 동작을 살..
[실버 5] 백준 7785 - 회사에 있는 사람 (파이썬)
[실버 5] 백준 7785 - 회사에 있는 사람 (파이썬)
2025.04.14https://www.acmicpc.net/problem/7785풀이이 문제는 회사에 출퇴근한 사람을 바탕으로 회사에 남아 있는 사람을 구하는 문제이다.나는 단순히 Dictionary를 생각했지만, Set으로도 풀이가 가능하다고 생각해서 두개의 버전을 작성하였다.먼저 Dict의 경우 people 딕셔너리에 사람이 들어 있지 않고, 상태가 enter인 경우에 dict에 추가하였다.그외에는 딕셔너리에서 삭제하는 방법을 생각했다.for i in range(N) : name, status = input().split() if name not in people and status == "enter" : people[name] = status else : del people..
[실버 1] 백준 1926 - 그림 (파이썬)
[실버 1] 백준 1926 - 그림 (파이썬)
2025.04.14https://www.acmicpc.net/problem/1926풀이도화지에는 0 또는 1로 된 값이 채워진 N * M 크기의 이차원 배열이 있다.1은 그림의 일부, 0은 빈 공간.그림은 상하좌우로 연결된 1들의 집합이며, 그림의 개수와 가장 넓은 그림의 넓이를 출력해야한다.즉, BFS로 1을 시작점으로 탐색하여 그림 하나를 모두 탐색하고, 이미 방문한 좌표는 visit 배열로 체크한다,각 BFS마다 count로 넓이를 측정한다.queue = deque()visit = [[False] * M for _ in range(N)]BFS용 큐를 초기화 하고, visit은 해당 좌표를 이미 방문했는지 여부를 저장하는 2차원 리스트이다.dr = [0, 0, 1, -1]dc = [-1, 1, 0, 0]상, 하, 좌,..