Python
경사하강법 직접구현
오늘은 경사하강법을 직접 구현해보겠다. 학교 과제로 진행하게 되었지만 정리할겸 글을 남긴다. 모델은 간단한 선형 모델을 만들어보는걸 목표로 할 것이다! 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..
1753_최단경로
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 처음에 문제를 접하고 나서 든 생각은 graph를 하나두고 시작점을 기준으로 한 배열을 하나두고 그 배열을 채워나가면 될 것 같았다. 이때 시작점을 기준으로 한배열의 경우 0번째 index는 시작점 --- 0 번 노드 사이의 간격 1번째 idnex는 시작점 --- 1 번 노드 사이의 간격 식으로 채울 생각이었다. import sys from collection..
1707_이분그래프
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이전에 그래프를 사용했다면 응용해서 풀면 된다. 결국 말은 어렵지만, 단순하게 생각해보자. 1,2,3번 3개의 점만 있다고 생각해보고 우리는 이를 빨강팀과 파랑팀으로 나눌 것이다. 1번과 2번이 연결되어있다면 1,2번은 무조건 다른팀이어야 한다. 즉, 1번이 빨강팀이라면 2번은 파랑팀이어야 한다. 그 후에 만약 2번이 3번과 연결되어 있다면 3번은 빨강팀이 될 수 밖에없다. 이런상황에서 1번과 3..