본문 바로가기

🔅코딩테스트 공부🔅213

[백준] 14938번 서강그라운드(python) https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 1. 난이도 골드4 (🥇) 2. 문제 해결 방법 플로이드 워셜 알고리즘과 다익스트라 모두 사용할 수 있다. 플로이드의 시간복잡도가 더 크지만, n의 범위가 1부터 100까지라 문제 없을 것 같다고 판단해 플로이드로 풀었다. 1. 플로이드 알고리즘을 이용해 모든 정점에서 다른 정점으로 가는 최단 거리를 구한다. 2. 수색범위보다 작거나 같을 때, 다른 정점으로 이동하며 아이템의 개수를 더해준다. (이걸 .. 2023. 2. 26.
[백준] 2468번 안전 영역(python) https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 1. 난이도 실버1 (🥈) 2. 문제 해결 방법 rain의 경우 1보다 적게 내리면 아무 지역도 잠기지 않는다. 1. 따라서 0부터 1씩 증가하며 map의 value가 잠길 경우 visit, maps를 모두 -1로 바꿔주었다. for i in range(n): for j in range(n): if maps[i][j] 2023. 2. 26.
[백준] 1865번 웜홀(python) https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 1. 난이도 골드3 (🥇) 2. 문제해결 과정 인터넷에 있는 많은 글들이 dist[v] != INF을 검사하지 않으면 정답 처리 된다고 했다. 그러나 벨만포드에 대한 이해도가 부족한 나는 그 말이 도무지 😭이해 되지않아 백준 질문게시판 + 이 문제와 관련된 모든 글들을 정독했다. 문제 해결에 가장 큰 힌트가 된 글을 jh05013님이 백준 질문게시판에 올려주신 "풀이 및 논란 완전히 .. 2023. 2. 26.
[백준] 1956번 운동(python) https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 1. 난이도 골드4 (🥇) 2. 문제 해결 과정 (보완 필요해서 4번에 추가해놨음) 사이클을 이루는 도로를 찾기 위해서는 1. 플로이드 워셜 알고리즘을 이용해 모든 지점에서 다른 지점까지의 최단 경로를 구한다. 2. 출발 장소 -> 도착장소 , 도착장소 -> 출발장소로 가는 두 경로 모두 INF가 아닐 경우의 값 중 최솟값을 구한다. (cycle이 이뤄지지 않았을.. 2023. 2. 25.
[백준] 1238번 파티(python) https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1. 난이도 골드3 (🥇) 2. 문제 해결 방법 우선 이 문제는 다익스트라로 풀면 되며, 학생은 n개로 구분된 마을에 한 명씩 살고있다는 조건이 있다. 예시를 보면 마을은 1,2,3,4,5번 5개가 있고, 파티의 장소는 2번이다. 따라서 아래와 같이 파티로 가는 길과 파티를 끝내고 집으로 돌아가는 길을 각각 다익스트라로 돌린 후 1,2,3,4,5번 중 가장 오래 걸린.. 2023. 2. 25.
[백준] 1389 케빈 베이컨의 6단계 법칙(python) https://www.acmicpc.net/problem/1389 1. 난이도 실버1 (🥈) 2. 문제 해결 방법 BFS로도 해결가능하고 플로이드-워셜로도 해결 가능하지만 플로이드워셜을 활용해서 이 문제를 해결했다. 인접행렬을 양방향 리스트로 만들어주고, 친구를 거쳐서 도달한 횟수 중 최솟값을 인접행렬에 넣는다. 행렬의 각 행을 더한 후, 제일 작은 값의 index를 출력하면 된다. 3. 내가 작성한 코드 n,m = map(int, input().split()) #n 유저 m 친구관계 INF = int(1e9) graph = [[INF] * (n+1) for _ in range(n+1)] result = [] #케빈 베이컨 수 입력력 for i in range(1,n+1): for j in range(1.. 2023. 2. 24.
[백준] 5972번 택배 배송(python) https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 1. 난이도 골드5 (🥇) 2. 문제해결 방법 전형적인 다익스트라 문제이다. 다익스트라 알고리즘을 사용하고 distance의 마지막 위치를 return 해주면 된다. 3. 내가 작성한 코드 import heapq INF = int(1e9) n,m = map(int,input().split()) #n헛간 m소 graph = [[] for _ in range(n+1)] distance = [INF] * (n+.. 2023. 2. 24.
[백준] 11403번 경로 찾기(python) https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 난이도 실버1 (🥈) 2. 문제 해결 방법 플로이드 워셜 알고리즘을 이용하면 된다. 출발 -> 경유지까지 이어져 있고(True), 경유지->도착까지 이어져있으면(True) 출발-> 도착이 이어져있기 때문에 graph[출발][도착]에 1을 넣어주면 된다. 3. 내가 작성한 코드 n = int(input()) #정점 graph = [] for _ in range(n): graph.append(list(map(int, input().spl.. 2023. 2. 24.
[백준] 11404번 플로이드(python) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 1. 난이도 골드4 (🥇) 2. 문제 해결 방법 문제의 이름에서 보이듯 이 문제는 플로이드 워셜 알고리즘을 사용해야 한다. 그러나 이 문제는 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. 라는 함정이 있다. 테스트 케이스를 살펴보면 1 4 1 1 4 2 와 같이 1에서 4로 가는 노선이 두 개가 있는데, 뒤에 오는 값인 graph[1][4] = 2가 들어가게 되고, 이는 최단경로.. 2023. 2. 24.

티스토리툴바