분류 전체보기
1956_운동
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번에서 1번으로 가는것은 0으로 두었었는데, 이를 그냥 설정하지 않고 코드를 진행시키고, INF가 아닌 최솟값을 찾는 코드를 구현하면 될것같아서 해..
10217_KCM Travel
https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 되게 어려운 문제였다.. 처음에는 시간을 최소로 하는 알고리즘을 찾으며 비용의 제약을 두는방식으로 하면 될것 같았으나, 생각을 해보니 당장은 시간도 비용도 손해같지만 결국 초반에 돌아가야하는 경우가 생겼다. 1 6 149 8 1 2 60 20 2 3 30 70 1 3 100 80 1 3 20 180 3 4 20 100 3 5 150 20 5 6 50 40 4 ..
경사하강법 직접구현
오늘은 경사하강법을 직접 구현해보겠다. 학교 과제로 진행하게 되었지만 정리할겸 글을 남긴다. 모델은 간단한 선형 모델을 만들어보는걸 목표로 할 것이다! 14.3,21.6 5.3,11.2 9.2,19.1 11,21.1 9.9,18.1 14.9,23.3 11.6,21.9 8,17.4 13.1,22.5 14.8,23.2 5.7,12.5 8.2,16.6 7.2,15.2 10,18.7 9.1,17.2 13,21.6 10.3,19.3 5.9,12.2 6.1,12.8 15,22.4 10.3,21.3 15,21.6 11.3,22.1 8,16.4 11.8,22.4 테스트 케이스는 위와 같다. 왼쪽이 입력, 오른쪽이 출력이다. 편의상 출생 개월과 키라고 가정해 보자. 위 테스트 케이스를 csv파일로 저장한다음, numpy..
11404_플로이드
https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 해당 문제역시 이전에 풀었던 방법을 그대로 적용해보았더니 잘 풀렸다 ㅎㅎ 최단경로를 구하는 문제나 미확인 도착지를 한번 보고 오는걸 추천한다! import sys import heapq input = sys.stdin.readline INF = int(1e9) n = int(input()) m = int(input()) graph = [ [] for _ in range(n+1)] for _ in ..
11657_타임머신(벨만포드)
https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 처음에 다익스트라 알고리즘을 살짝 변형해서 모든 간선을 뒤지도록 변형해서 풀려고 했는데 실패했다... 그래서 힌트에 있는대로 벨만 포드 알고리즘을 공부해 보았다. 아래와 같은 간선이 있다고 생각해보자. 입력케이스로 따지면 아래와 같다. 4 6 1 4 10 1 3 8 3 4 1 1 2 5 2 4 3 2 3 1 4개의 점이 있기에 3번 반복..
1504_특정한 최단경로
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 다익스트라 알고리즘을 통해 저번에 최단경로를 구했었는데 이를 활용해서 풀었다. 결국 v1,v2 두개의 점을 통과하여 통과하려면 1 -> v1 -> v2 -> N 1 -> v2 -> v1 -> N 두가지 방법이 존재한다. 즉, 1,v1,v2 에서 다른 점들로의 최단거리를 구해놓은 배열을 하나 만들고, 위 방법에 따라서 최단거리를 정해주면 된다. impor..