![]()
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이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사..
https://www.acmicpc.net/problem/2583입력첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다. 출력첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다. 문제 코드from collections import dequ..
![]()
https://www.acmicpc.net/problem/31575알고리즘좌측상단에서 우측하단까지의 길을 찾는 문제이다. 2차원인 배열을 1차원으로 바꾸어 그래프에 적용하였다. 현재 위치가 1인 상태에서 오른쪽이 1이면 이동가능이므로 그래프에 추가, 아래가 1이면 이동가능이므로 그래프에 추가한 뒤에 dfs를 실행한다.마지막 위치의 visited배열을 검사하여 True면 이동이 가능하므로 Yes를 출력해준다.dfs로 해결했지만, dp로도 풀 수 있는 문제인 것 같다.코드import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**6)def dfs(graph, v, visited): visited[v] = True for i in graph[v]:..
![]()
https://school.programmers.co.kr/learn/courses/30/lessons/87694 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr알고리즘 유형깊이/너비 우선 탐색(DFS/BFS)문제 설명다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다. 지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다. 만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다. 단, 서로 다른 두 직사각형의 x축 좌표 또는 y..
문제 https://www.acmicpc.net/problem/16713 Algorithm누적합누적합이 아니라 매번 모든 쿼리를 계산하면 시간 초과가 난다.또한 베타적 논리합(XOR, ⊻)이 결합법칙이 성립함을 알고 있어야 한다.예를 들어 (a1 ⊻ a2 ⊻... a10) = (a1 ⊻ a2) ⊻ (a3 ⊻ a4 ⊻ ... a10) 이다.그리고 A ⊻ B = C 일 때, C ⊻ A = B, C ⊻ B = A 이다.추가적으로 0 ⊻ N = N 임을 알고 있어도 도움이 된다. Codeinput = __import__('sys').stdin.readlineN, Q = map(int, input().rstrip().split())a_list = list(map(int, input().rstrip().spl..
