본문 바로가기

🔅코딩테스트 공부🔅213

[백준] 1504번 특정한 최단 경로(python) https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 1. 난이도 골드4 (🥇) 2. 문제 해결 방법 다른 최단 경로 문제들과 다른 점은 1. 방향성이 없는 그래프이다(=양방향 모두 들릴 수 있다). 2. 두 정점을 반드시 거쳐야 한다. 1번은 graph에 append 할 때 for i in range(e): a,b,c = map(int, input().rstrip().split()) graph[a].ap.. 2023. 2. 24.
[백준] 1916번 최소비용 구하기(python) https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 1. 난이도 골드5 (🥇) 2. 내가 작성한 코드 한 지점에서 한 지점까지의 최단경로 + 가중치가 모두 음이 아님을 만족하기 때문에 다익스트라 알고리즘을 이용하면 된다. import heapq import sys n = int(input().rstrip()) #도시의 개수 m = int(input().rstrip()) #버스의 개수 INF = int(1e9) gr.. 2023. 2. 24.
[알고리즘] 최단경로(다익스트라, 플로이드워셜, 벨만포드) 1. 다익스트라 알고리즘 O(ElogV) 한 지점에서 다른 특정 지점까지의 최단 경로를 구할 때 사용 음의 경로가 있으면 사용할 수 없음(=가중치가 양수일 때만 사용 가능) heap(우선순위 큐)를 이용함으로써 시간복잡도를 줄일 수 있음 2. 다익스트라 알고리즘 코드 import heapq INF = int(1e9) n,m = map(int, input().split()) #n은 노드의 개수 m은 간선의 개수 start = int(input()) #출발점 graph = [[] for _ in range(n+1)] distance = [INF] * (n+1) for _ in range(m): a,b,c = map(int, input().split()) graph[a].append((b,c)) #a노드에서 .. 2023. 2. 24.
[백준] 1753번 최단경로(python) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 난이도 골드4 (🥇) 2. 내가 작성한 코드 import heapq import sys input = sys.stdin.readline INF = int(1e9) v,e = map(int,input().rstrip().split()) #v는 정점, e는 간선 start = int(input().rstrip()) #시작 정점 번호 distance = [IN.. 2023. 2. 24.
❗문제 메모 - 그래프❗ 해결한 문제의 양이 증가하면서 좋은 문제를 양치기만 하고 끝내면 안 될 것 같다는 생각이 들었다. 이 게시물에 푼 문제들에 대한 간단한 기록을 남겨보고자 한다. ## 노란색 복습 필요 x ## 초록색 복습 필요 o ## 빨간색 복습 진행 했으나 아직도 어려움 ## 보라색 개중요 ## 회색 잘 풀었는데 다시 보면 좋을 듯? 깊이 우선 탐색 / 넓이 우선 탐색 백준 2468번 안전영역 (실버1) / 2667번 단지번호 붙이기(실버1) 문제를 풀며 단지번호 붙이기와 유사하네? 라는 생각이 들었다. 우선 안전영역 문제는 비가 점점 차오른다고 가정했을 때, 각자 떨어져 있는 안전영역의 개수를 세고 -> 비가 점점 차오르던 각각 시기의 안전영역 개수 중 가장 큰 값을 return 하는 문제이다. 단지번호 붙이기는 .. 2023. 2. 23.
[백준] 2206번 벽 부수고 이동하기(python) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1. 난이도 골드3 (🥇) 아 진짜 넘나리 어려웠는데 막상 이해하니 해볼만 한 것 같다. 3차원 list를 이용해서 벽을 부순적이 있는 지 없는 지를 확인해주면 된다. 2. 코드 분석 1. n,m, maps는 다른 문제와 동일하게 입력을 받는다. 2. 방문 여부를 확인하기 위해 visit 리스트를 만든다. 이때, 같은 행과 열의 크기를 가진 2층짜리 3차원 리스트를 만든다.. 2023. 2. 23.
[백준] 1874번 스택수열(python) https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 1. 난이도 실버2 (🥈) 도대체 이게 무슨 문제인가 한참을 고민하다가 풀었다. 결론적으로 말하자면 stack을 적절하게 이용해서 input 의 순서와 같은 수열을 만들어 내는 것이다! 예제 입력 1을 보면 4-3-6-8-7-5-2-1 순서로 입력되는데, stack에서 pop한 값이 이 순서대로 나오면 된다. 2. .. 2023. 2. 23.
[백준] 4963번 섬의 개수(python) https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 1. 난이도 실버2 (🥈) 2. 내가 작성한 코드 from collections import deque import sys input = sys.stdin.readline def bfs(k): queue.append(k) visit[k[0]][k[1]] = 1 dx = [1, 1, 0, -1, -1, -1, 0, 1] dy = [0, 1, 1, 1, 0, -1, -1, -1] while qu.. 2023. 2. 22.
[백준] 11724번 연결 요소의 개수(python) https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 1. 난이도 실버2 (🥈) 2. 내가 작성한 코드 import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline n, m = map(int, input().rstrip().split()) graph = [[] for _ in range(n+1)] for _ in range(m):.. 2023. 2. 20.

티스토리툴바