파이썬

백준 14938번 서강그라운드 문제 파이썬 풀이입니다. 14938번: 서강그라운드 (acmicpc.net) 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 2017 SPC에 출제 되었던 문제입니다. 한 노드에서 각 노드까지의 최단거리를 알아야하기에, 최단 경로 탐색 알고리즘인 다익스트라(Dijkstra) 알고리즘으로 풀 수 있는 문제입니다. 다익스트라 알고리즘은 N*logN 시간복잡도를 가지게 되는데, 총 N개의 노드를 시작점으로 탐색해야기에 N개 * N*logN 의 시간복잡도를 필요로 하고, N은 최대 100이기에..

백준 16202번 MST 게임 문제 파이썬 풀이입니다. https://www.acmicpc.net/problem/16202 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 문제 이름에서 대놓고 알고리즘을 알려주고 있기 때문에 MST를 푸는 방법인 Kruskal 알고리즘으로 풀 수 있었습니다. Edge의 최대가 10000개여서 O(ElogE)인 알고리즘으로 K번 돌아도 충분한 문제였습니다. 주요코드 line 10 ~ 22 : 유니온파인드 함수 lin..

백준 14217번 그래프 탐색 1 문제 파이썬 풀이입니다. https://www.acmicpc.net/problem/14217 14217번: 그래프 탐색 남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 잇는 도로들을 새로 만들거나, 안전상의 문제로 도로를 없애기도 할 계획이다. 도로 정비 계획은 두 도시와, 만들건지, 없앨건지에 www.acmicpc.net 비슷한 버전의 '그래프 탐색 2'를 풀었다면 아주쉽게 풀 수 있는 문제였습니다. 도로가 사라졌을 때는 원래 최단 거리였던 길이 없어진 경우도 있기 때문에 매번 distance 배열을 초기화 시켜야 한다는 사실만 주의하면 이전 버전 문제와 거의 유사했습니다. 주요코드 line 18 ~ 33 : 1부터 시작해서 각 node까지 BFS를 ..

백준 14218번 그래프 탐색 2 문제 파이썬 풀이입니다. https://www.acmicpc.net/problem/14218 14218번: 그래프 탐색 2 첫째 줄에는 도시의 개수 n,도로의 개수 m이 주어진다. 다음 m개의 줄에는 두 도시가 주어진다.(2≤n≤1,000,1≤m≤100,000) 다음 줄에는 도로 정비 계획에 들어가 있는 도로의 수 q가 주어지고, 다음 q www.acmicpc.net 실버1 치고는 널널한? 문제였습니다. N이 1000이라 최적화없이 대충짜도 어째저째 돌아가는 문제였습니다. INF로 초기화 시킨 distance 배열을 만들어 두고, 테스트가 들어올 때마다 node 1에서 시작해서 BFS를 돌며 최소거리로 갱신시켜 나가는 방식으로 해결할 수 있었습니다. 주요코드 line 1..

백준 5546번 파스타 문제 파이썬 풀이입니다. https://www.acmicpc.net/problem/5546 5546번: 파스타 상근이는 매일 저녁으로 파스타를 만들어 먹는다. 상근이가 만들 수 있는 파스타는 총 세 종류로 토마토 소스, 크림 소스, 바질 소스이다. 상근이는 앞으로 N일 동안 먹을 파스타를 계획하려고 www.acmicpc.net 너무나도 DP스러운 문제기 때문에 점화식을 찾아서 구현해주면 되는 문제입니다. dp 테이블는 dp[N번째 날짜에][직전에안먹은거,직전에먹은거][파스타종류] 가 되고 fix 배열에 고정된 파스타에 대한 정보를 저장합니다. 주요코드설명 더보기 line 13~20 : 1일차에 먹는 경우를 세팅해줍니다. line 22~38 : 2일차부터 N일차까지 토마토 소스, 크..