본문 바로가기

백준 문제풀이 코드저장소

 (99)
Baekjoon 1562. 계단 수 / Python 1562. 계단 수난이도 : 골드 1소요 시간 : 20분날짜 : 2024.12.21언어 : 파이썬알고리즘 유형 : 비트마스킹, 비트집합, 다이나믹프로그래밍설명 보기전에 문제 풀어보러 가기1. 문제 설명계단수 = 인접 한 수 끼리의 차이가 1은 수길이 N인 계단 수의 개수를 구하는 문제0으로 시작하면 안된다.2. 해결 방식비트와 dp를 사용한다.dp[i][j][k]의 값은 i자리, j로 끝나는, 비트 k 를 가진 수 이다.이 때, 비트 k라는 것은, 10자리의 비트로써, 0부터 9까지의 수를 체크하는 역할이다. -> 모두 1인 1111111111이 되어야 계단수의 조건을 만족한다.3. 정답 코드import syssys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/i..
Baekjoon 7453. 합이 0인 네 정수 / Python 7453. 합이 0인 네 정수난이도 : 골드 2소요 시간 : 40분날짜 : 2024.12.20언어 :Python알고리즘 유형 : 이분탐색, 투포인터, 정렬설명 보기전에 문제 풀어보러 가기1. 문제 설명숫자를 담은 배열 A, B, C, D가 주어진다.A에서 숫자 하나(a), B에서 숫자 하나(b), C에서 숫자 하나(c), D에서 숫자하나(d)를 골라서합(a + b + c + d)이 0이 되는 쌍의 개수를 찾는다.2. 해결 방식우선 숫자의 개수는 최대 4000개이다.완탐 시간복잡도 O(n^4) : 4000^4 = 256,000,000,000,000 -> 약 250만 초가 걸린다.......투포인터 알고리즘을 사용해서 해결했다.우선 a + b와 c + d 의 순서쌍을 모두 찾는다. (시간복잡도 O(2 * n..
Baekjoon 2623. 음악프로그램 / Python 2623. 음악프로그램난이도 : 골드 3소요 시간 : 30분날짜 : 2024.12.19언어 : Python알고리즘 유형 : 위상정렬, 그래프이론, 방향비순환 그래프설명 보기전에 문제 풀어보러 가기1. 문제 설명순서가 주어진 리스트 여러개가 주어진다.이 순서를 유지하면서 주어진 모든 수를 정렬한다.2. 해결 방식위상정렬의 아주 대표적인 문제이다.위상정렬알고리즘의 풀이방식을 그대로 사용한다.연결리스트 자료구조를 만들어 풀이할 수도 있을 것 같아서 해봤다. (사실 더 효율적이어서 한건 아니고, 이런 자료구조를 만드는 것에 익숙해지기 위해서 했다.)3. 정답 코드풀이 1 -  위상정렬import syssys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt"..
Baekjoon 9328. 열쇠 / Python 9328.열쇠설명 보기전에 문제 풀어보러 가기1. 문제 설명'.'은 이동가능한 곳'*'은 이동 불가능한 곳'$'는 문서가 있는 곳'소문자 알파벳'은 열쇠'대문자 알파벳'은 잠긴 문건물 밖에서 안으로 돌아다닐 수 있으며, 문서를 가장 많이 챙길 수 있을 때, 문서의 개수를 구하는 문제2. 해결 방식기본적인 bfs문제에다 문/열쇠의 개념이 추가되었다.우선 빌딩 을 '.'안에 넣는 방식으로 건물 외부에 대한 배열을 추가했다.새로운 열쇠를 얻을 때 마다, 방문했던 잠긴 문을 열 수 있는 가능성이 생기므로 이를 해결해주는 것이 중요하다.새로운 열쇠를 얻게 되면, 방문했던 잠긴 문들 중에 얻은 열쇠로 열리는 문이 있다면 큐에 추가하는 방식으로 해결했다.3. 정답 코드import sys# sys.stdin = ope..
Baekjoon 1197. 최소 스패닝 트리 / Python https://www.acmicpc.net/problem/11972024.12.16 - [알고리즘/알고리즘 정리] - 알고리즘 유형공부 02 - 최소신장트리 (MST) 알고리즘 유형공부 02 - 최소신장트리 (MST)최소신장트리, 최소스패닝트리 - Minimum Spanning Tree개요신장트리란 무엇일까?신장트리(Spanning Tree)란 - 그래프에서 모든 정점을 포함하며, 모든 정점에 대한 최소한의 연결만을 가진 그래프이다.그developer-traxer.tistory.com알고리즘 설명은 위 글을 참고하면 좋다.문제는 그냥 이 최소스패닝트리를 구현하는 것이다.1. PRIM 알고리즘이 경우에는 시간초과가 난다. 그 이유는 프림알고리즘의 시간복잡도는 I(V * ElogV)이므로 O(10^11)이기..
Baekjoon 1167. 트리의 지름 / Python https://www.acmicpc.net/problem/1167 문제 설명트리의 지름의 최댓값을 구하는 문제이다.문제 풀이트리의 임의의 한 점에서 각 노드로 가는 최댓값을 구한다. → 트리의 지름에 해당하는 두 노드를 a와 b라고 했을 때, 임의의 한 노드에서 다른 임의의 한 노드까지의 거리의 최댓값에 해당하는 노드는 항상 a이거나 b이다.bfs를 두 번 돌린다. → a혹은 b를 찾고 → 다시 최대 경로를 구해서 지름을 구한다.풀이 코드from collections import deque as dqimport sys; input = sys.stdin.readlinedef bfs(v, arr, s): q = dq() q.append((s, 0)) visit = [-1] * (v + 1) ..
Baekjoon 1194. 달이 차오른다, 가자. import sys;input = sys.stdin.readlinefrom collections import deque as dqn, m = map(int, input().split())arr = [list(map(str, input().rstrip())) for _ in range(n)]for i in range(n): for j in range(m): if arr[i][j] == '0': sx, sy = i, j arr[i][j] = '.'def bfs(x, y): q = dq([(x, y, 0, 0)]) visit = [[[0] * (1
Baekjoon 32069. 가로등 / Python 문제 링크 문제 설명수직선 도로 위에 여러 개의 가로등이 위치하고 있습니다.각 위치의 어두운 정도를 그 위치로부터 가장 가까운 가로등까지의 거리로 정의합니다.제일 밝은 곳부터 어두운 정도를 k개 출력하는 문제코드 설명가로등이 k보다 많으면 0을 k번 출력하고 종료가로등에 대해서, 거리를 1씩 늘려가면서 가로등과의 거리 계산import sys; input = sys.stdin.readlinel, n, k = map(int, input().split())arr = list(map(int, input().split()))# 만약 가로등의 개수가 k 이상이면, 어두운 정도는 항상 0이 최소 k개 이상이다.if n >= k: # 모든 어두운 정도는 0이기 때문에 0을 k번 출력하고 종료 print('0..
Baekjoon 11265. 끝나지 않는 파티 / Python https://www.acmicpc.net/problem/11265문제설명문제는 놀이동산 "민호월드"의 여러 파티장에서 일방통행 도로를 통해 다른 파티장으로 이동할 때, 특정 시간 내에 도착할 수 있는지를 판단하는 것입니다.각 파티장은 다른 모든 파티장과 직접적으로 연결된 도로가 있습니다.각 도로는 일방통행이며, 각 도로를 통해 이동하는 시간이 주어집니다.M개의 쿼리에서 출발 파티장, 도착 파티장, 그리고 시간 제한이 주어지며, 주어진 시간 내에 도착할 수 있는지를 판단해야 합니다.코드 설명사용된 알고리즘 : 다익스트라결과 리스트 res를 만들어 중복을 관리한다.이미 계산된 결과를 res 리스트에서 바로 사용하기 위함이다.처음 계산하는 값이라면,다익스트라 함수를 통해 res에 최단 경로를 계산한다.우선순..
Baekjoon 7662. 이중 우선순위 큐 / Python https://www.acmicpc.net/problem/7662문제 설명연산들을 수행하고 최종적으로 큐에 남아있는 데이터 중 최대, 최솟값을 출력한다.비어있다면 EMPTY를 출력한다.코드 설명최대 힙, 최소 힙을 모두 사용한다.find 배열을 사용해 해당 인덱스의 숫자의 유효성을 체크한다.시간복잡도삽입 : O(log n) (최악)삭제 : O(log n) (최악)전체 : O(n log n)import sysinput = sys.stdin.readlinefrom heapq import heappop, heappush# 테스트 케이스 수 입력T = int(input())for _ in range(T): # 연산의 개수 입력 n = int(input()) # 최대 힙과 최소 힙 q..

티스토리툴바