어흥

문제 링크: www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 1. 주의할 점 - Automata 혹은 정규표현식 사용법에 대해 알고 있어야 한다 2. 구현 - 위에서 언급한 조건을 정규표현식으로 나타낸다. 단, 이때 (100+1+|01)+가 아닌 [100+1+|01]+로 할 경우, 오답이 발생한다([]의 경우, 1개만 만족해도 True를 반환하기 때문) - matches() 함수를 사용하여 패턴과 일치하는지 Boolean값으로 Return받고 삼항..

문제 링크: www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 1. 주의할 점 - 두 포인터로 접근한다 - 아래 TC와 같은 케이스에 대해 정확히 처리한다 더보기 TC #1 5 3 4 1 2 4 2. 구현 - 입력받는 수들을 Arr[] 배열에 저장한다 - 두 포인터 L,R을 이용하여 L~R까지에 대한 처리를 진행한다 - R이 Num과 같을 때까지 진행한다 - Arr[]값이 나타난 수를 Check[] 배열에 저장하며, 만약 Check[]의 값이 True면 중복된 경우가..

문제 링크: www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 1. 주의할 점 - 모든 강의에 대한 정보와, 현재 진행중인 강의를 어떻게 정렬할 것인지 잘 계획한다 2. 구현 - 모든 강의를 우선순위 PQ에 담는다. PQ의 경우, 시작시간이 빠른순으로 정렬하며, 시작시간이 같은 경우 종료 시간이 빠른 순으로 정렬한다. 종료시간을 1순위로 할 경우, 아래 TC에서 오답을 받게된다 TC #1 6 1 9 2 11 3 11 4 11 12 15 9 17 Answer: 4 - 현재 강의중인 강의실을 PQ2로 설정하고,..

문제 링크: www.acmicpc.net/problem/2982 2982번: 국왕의 방문 지난주에 상그니 아라비아의 국왕 고둘라 창지즈 영사우드가 한국에 도착했다. 고둘라는 매우 중요한 사람이다. 따라서, 경찰은 그가 타고 있는 차량이 길에 진입했을 때, 그가 길에 있는 동안 www.acmicpc.net 1. 주의할 점 - 국왕의 현재 위치를 알고 있어야 한다 or 각 도로가 통제되는 시간을 알고 있어야 한다 - 조건에 맞게 구현을 정확히 해야한다 2. 구현 - 교차로의 수만큼 Dist[] 배열을 초기화한다 - 교황이 방문하는 교차로를 Loc 벡터에 담는다 - 모든 도로에 대한 정보를 V[] 벡터와 도로의 길이를 Road[][] 배열에 담는다 - rSum[] 배열에는 교황이 순서대로 방문하는 교차로까지 ..

문제 링크: www.acmicpc.net/problem/13907 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 1. 주의할 점 - 세금이 오를때마다 다익스트라 알고리즘을 수행하지 않는다 2. 구현 - 기존 다익스트라 알고리즘에서 사용하던 Dist[] 배열을 변형시킨다 - Dist[][] 배열을 통해 [각 지점][각 지점까지 도달하는데 거친 Node수] 형태를 만족하며 최단경로 값을 저장한다 - dijkstra() 함수를 통해 Dist[..

문제 링크: www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 1. 주의할 점 - 다익스트라 혹은 플로이드 와샬 알고리즘에 대해 알고 있어야 한다 2. 구현 - 모든 간선에 대한 정보를 TC마다 초기화한다 - 간선에 대한 정보를 Arr[][] 배열에 입력받는다 - floydWarshall() 함수를 통해 각 노드사이의 최단거리를 구한다 - 친구들이 위치한 방을 V벡터에 받은 후, 1~Node번방까지 모두 모임의 방이라고 가정하며 모임방↔친구들이 위치한 방까지의..

문제 링크: www.acmicpc.net/problem/2307 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸 www.acmicpc.net 1. 주의할 점 - 다익스트라 알고리즘에 대해 알고 있어야 한다 - 최단경로를 구했을 때, 경로를 구하는 방법을 알고 있어야 한다 2. 구현 - 종종 나오는 다익스트라의 심화문제라고 할 수 있다 - Dist[] 배열을 통해 1번 Node부터 각 Node까지의 최단거리를 저장한다 - Pre[A] 배열을 통해 Dist[A]의 값이 갱신되었다면(최단거리로) 어떤 Node에서 왔는지 저장한다 - V[] 벡터를 통..

문제 링크: www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 1. 주의할 점 - 최단거리가 지름길을 안탈수도 있는 경우가 있다 2. 구현 - Dist[]를 통해 0부터 각 지점까지의 길이를 미리 저장한다 - 지름길에 대한 정보를 받을 때, 지름길의 도착지점이 목표지점을 넘어가거나, 사실상 지름길이 아닌 경우는 제외한다 - 0부터 도착지점까지 Dist[] 배열을 갱신하며, 만약 해당 지점에 지름길이 있는 경우, 지름길의 반대편까지의 거리를 기존 길이..