![]()
잡설예전에 풀었던 문제들 다시 풀어봤다. 그냥 푸는것보다 예전보다 빠르거나 숏코딩으로 짜보는 것도 재미있을 것 같아서 옛날에 짠 코드들을 비교해보면서 짜보았다.문제1895 필터풀이단순하게 3*3 기준으로 생각해보면, 가장자리를 제외한 1~n-1, 1~m-1의 좌표와 그 좌표 주변의 값들만 확인하면 된다. dx, dy를 능숙하게 다룰 수 있는 사람이라면 해당 개념을 이용해 간단하게 해결할 수 있다. 값들의 크기가 그리 크지 않아서 단순하게 매번 배열을 새로 만들던, 슬라이싱을 하던 상관 없이 해결 할 수 있다.코드n,m=map(int,input().split())a=[input().split()for i in range(n)]x=[0,0,0,1,1,1,-1,-1,-1]y=[0,1,-1,1,0,-1,1,0,..
문제KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-99, -2, -1, 4, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액의 ..
![]()
https://www.acmicpc.net/problem/17204알고리즘그래프를 그리고, 0번에서 시작하여 k번까지의 최소 거리를 찾는 문제이다.간선 사이의 거리를 1로 설정하여 다익스트라 알고리즘을 돌려준 뒤에 distance배열에서 k번째 원소의 값을 읽어와 INF면 -1을, 아니면 거리를 출력해주면 된다.코드import sysimport heapqinput = sys.stdin.readlineINF = int(1e9)n, target = map(int, input().split())graph = [[] for _ in range(n)]distance = [INF] * n for a in range(n): b = int(input()) graph[a].append((b, 1)) def..
https://www.acmicpc.net/problem/2346입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100)전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.출력각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. 문제 코드from collec..
![]()
https://www.acmicpc.net/problem/13334알고리즘 분류자료 구조 정렬 스위핑 우선순위 큐문제집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 d로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하고자 한다.양의 정수 d와 n 개의 정수쌍, (hi, oi), 1 ≤ i ≤ n,이 주어져 있다. 여기..
문제 https://www.acmicpc.net/problem/13549 Algorithm다익스트라 탐색X - 1 칸, X + 1 칸, 2 * X 칸 이동을 각 각 하나의 간선으로 생각하여 구현하면 되는 문제이다. 다만 조건에 유의해야 할 필요가 있다. N과 K의 관계를 유의하자. Codeimport heapqinput = __import__('sys').stdin.readlinedef dijkstrat(start) : q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q : dist, now = heapq.heappop(q) if distance[now] = sizeG * 2 + 1: ..
문제방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.입력첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.출력첫째 줄부..
![]()
https://www.acmicpc.net/problem/5972알고리즘 분류그래프 이론 최단 경로 데이크스트라문제농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.농부 현서에게는 지도가 있습니다. N (1 다음 지도를 참고하세요. [2]--- / | \ /1 | \ 6 / | \ [1] 0| --[3] \ | / \2 4\ | /4 [6] \ | /..
![]()
https://www.acmicpc.net/problem/1504알고리즘출발점이 1 종료지점이 n이고 v1, v2를 지나는 최단경로의 길이를 출력하는 문제이다. 가능한 경로는1 -> v1 -> v2 -> n / 1 -> v2 -> v1 -> n 두가지 경로가 존재하므로 각각의 경우를 전부 계산해서 더해준 뒤에 더 작은 값을 출력해주면 된다.출발점을 1, v1, v2 로 하여 다익스트라를 진행한 뒤에 각각의 경우를 더해서 최단경로를 계산해주었다.모든 경우마다 다익스트라를 실행하면 시간이 많이 소요되기 때문에, 각각의 경우에 대해 1번씩만 수행한 뒤에 distance배열을 리턴값으로 받아서 마지막에 더해주었다.코드import sysimport heapqinput = sys.stdin.readlineINF ..
https://www.acmicpc.net/problem/13424입력입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방의 개수 N (2 ≤ N ≤ 100), 비밀통로의 개수 M(N-1 ≤ M ≤ N(N - 1)/2)이 공백으로 구분되어 주어진다. 그 다음 줄부터 M개의 줄에 걸쳐 비밀통로의 정보(a, b, c)가 주어진다. a와 b는 비밀통로로 연결된 두 방의 번호이며 c는 a와 b를 연결하는 비밀통로의 길이이다. a와 b는 항상 다르며 c는 1 이상 1,000 이하의 자연수이다. 두 방을 연결하는 비밀통로는 반드시 하나씩만 존재한다. 또한 어떤 방에서 다른 방으로..
문제 https://www.acmicpc.net/problem/4485 Algorithm- 다익스트라 알고리즘 사용했당 Codeimport java.util.*;import java.io.*;public class Main { static class Node implements Comparable{ int x; int y; int cost; public Node(int x, int y, int cost) { this.x = x; this.y = y; this.cost = cost; } @Override public int compareTo(Node o) { return this.cost - o.cost; } } static int n; static int[][]..
문제우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.입력사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사..
