본문 바로가기

백준 문제풀이 코드저장소/Gold

 (74)
Baekjoon 16946. 벽 부수고 이동하기 4 / Python 16946. 벽 부수고 이동하기 4난이도 : 골드 2소요 시간 : 40분날짜 : 2024.12.24언어 : 파이썬알고리즘 유형 : bfs, 그래프설명 보기전에 문제 풀어보러 가기1. 문제 설명벽을 부수고 이동할 수 있는 곳으로 변경한다.그 위치에서 이동할 수 있는 칸의 개수를 센다.2. 해결 방식시간 줄이기*맵의 크기가 최대 1000 * 1000 이기 때문에 그냥 bfs를 돌리면 시간복잡도가 10^12로 시간초과가 난다.시간을 줄이기 위해 집합과 인덱싱을 사용한다.인덱싱 -> 유니온파인드 알고리즘과 유사한 방법풀이벽인 곳을 찾는다.벽의 상하좌우에서 벽이 아닌 곳을 찾는다.벽이 아닌 곳에서 bfs를 돌린다.이 때, bfs를 돌려서 이동가능한 공간에 인덱스 번호를 부여하고,인덱스 번호에 맞는 리스트를 만들어..
Baekjoon 2143. 두 배열의 합 / Python 2143. 두 배열의 합난이도 : 골드 3소요 시간 : 25분날짜 : 2024.12.23언어 : 파이썬알고리즘 유형 : 이분탐색, 누적 설명 보기전에 문제 풀어보러 가기1. 문제 설명정수 t와 배열 a, 배열 b 가 주어진다.배열 a와 배열 b에서 각각 모든 원소가 연속된 배열을 선택한다.선택된 배열들의 숫자의 합이 t 가 되는 경우의 수를 구한다.2. 해결 방식배열a 와 배열 b 에서 나올 수 있는 모든 합을 구해서 딕셔너리형태로 저장했다.배열a 를 순회하여 그 값(key)과 개수(value)를 구하고 배열 b에서 t - key의 value(개수)를 찾아서 곱한 후, 결과에 누적한다.3. 정답 코드import syssys.stdin = open("C:/Users/ghtjd/Desktop/tmp/pyth..
Baekjoon 15681. 트리와 쿼리 / Python 15681. 트리와 쿼리난이도 : 골드 5소요 시간 : 10분날짜 : 2024.12.23언어 : 파이썬알고리즘 유형 : dfs, dp 트리, 그래프설명 보기전에 문제 풀어보러 가기1. 문제 설명트리 구조의 그래프가 주어지고, 루트 노드가 지정된다. 각 노드 u를 루트로 하는 서브트리의 정점 수를 계산한다. 2. 해결 방식자기 자신을 포함 자식노드를 탐색하고 결과를 누적시킨다. 3. 정답 코드import syssys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt", "r")sys.setrecursionlimit(1e10)# input = sys.stdin.readlinen, r, q = map(int, input().split()) # 2 ≤..
Baekjoon 2098. 외판원 순회 / Python 2098. 외판원순회난이도 : 골드 1소요 시간 : 45분날짜 : 2024.12.22언어 : 파이선알고리즘 유형 : 비트마스킹, dp, dfs설명 보기전에 문제 풀어보러 가기1. 문제 설명n 개의 도시가 주어진다.도시의 연결은 비용으로 연결된 비대칭그래프이다.최소의 비용으로 모든 도시를 순회하고 돌아와야 한다.2. 해결 방식비트마스킹과 DP....(그리고 dfs)DP 배열 설명 : dp는 2차원 배열로써 dp[i][j] 는 도시 i에 도달했고, 방문 상태 j 일 때의 최소비용을 나타낸다.비트마스킹 : 방문 상태 j 는 비트마스킹으로 나타낸다. n의 범위가 2 dfs에서의 가지치기 3-1. 모든 도시를 방문 한 경우 : 최소값을 갱신할 수 있다. 3-2. 최소비용이 이미 있는 경우 : 그 값을 재사용한다...
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) ..

티스토리툴바