공부공간

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 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 이하의 자연수이다. 서로 다른 두 www.acmicpc.net 한 노드에서 모든 노드까지의 최단거리를 구할때 벨만포드 알고리즘O(간선개수 * 노드개수 ) 이나 간선이 모두 양수인경우 다익스트라O((간선..

https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4

https://www.acmicpc.net/problem/1325 1325번: 효율적인 해킹 첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다. www.acmicpc.net 신뢰성이 존재하는 컴퓨터 관계에서 하나의 컴퓨터를선택해서 가장많이 해킹할 수 있는 컴퓨터를 뽑는 문제이다. 문제는 단순하지만, N=10000에서 완전탐색을 고민하게되는데, 나도 DFS+DP로 접근하였었다. 바로 틀렸습니다! 가 나오길래 사이클이 있는 경우에서 DP의 값이 이상하게 갱신되는것을 알 수..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 가수의 수가 나오고, 그 뒤로는 그 가수들의 순서가 나온다. N은 1이상 1,000이하의 정수이고, M은 1이상 100이하의 정수이다. www.acmicpc.net 음악프로그램에 N명의 참가자가 일부 순서가 정해져있을때에 서로다른 M가지의 일부순서를 만족하는 하나의 전체순서를 구하는 전형적인 위상정렬문제이다. 만약 그래프에 사이클이 생겼을때에는 전체 N을 방문하지 않고 끝나므로, Indegree배열에 0이..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. www.acmicpc.net 위상 정렬 ( Topology Sort )는 그래프의 진입 차수를 기준으로 다음 올 그래프의 순서를 정하는 정렬알고리즘이다. 먼저 위상 정렬의 순서는 다음과 같다. 1. 그래프에서 진입차수가 0인 노드들을 큐에 넣는다. 2. 큐에서 하나씩 poll 하면서, 그 노드와 연결된 그래프들의 진입차수를 -1해준다 ( 큐에서 poll ..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a www.acmicpc.net 합집합의 연산을 반복하면서, 특정 두 원소가 같은 집합에 속해있는지를 묻는 문제이다. 이 문제는 "너 서로소집합 메소드 구현할줄알아?..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net 예전에 못풀어서 끙끙앓던 문제였는데 다시 생각해보니 쉬웠다. 큐에 들어가는 노드에 벽을 부수었는지? 만 체크하면 된다고 생각했..

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서 www.acmicpc.net 3차원 BFS를 통해서 S에서 시작하여 E까지 도달하는 문제이다. 한 칸움직이는 사이에 1분이 소요되므로 일반적인 BFS를 돌려주면 된..