본문 바로가기

알고리즘/알고리즘_ps

(6)
2463_비용 https://www.acmicpc.net/problem/2463 2463번: 비용 첫 번째 줄에 정점의 수 N (1< ≤ N ≤ 100,000)과 간선의 수 M (1 ≤ M ≤ 100,000)이 빈칸을 사이에 두고 주어진다. 다음 M개의 각 줄에 간선 하나에 대한 정보를 나타내는 세 개의 양의 정수 x,y,w가 빈칸 www.acmicpc.net 문제 이해 ) 그래프가 주어지고 Cost(u, v)를 구하는 문제. Cost(u, v)에 경로가 없을 때까지 더 해진 그래프에 가중치의 최솟값들. 하지만 U
5214_환승 https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 하이퍼링크를 이용하여 1에서 n 까지의 최단 경로를 구하여라. 접근 1. 다이나믹프로그래밍 각 노드의 값을 m 의 최대값으로 초기화 하고 1번 부터 연결될 모든 노드의 값을 최솟값으로 갱신하면 되겠다고 생각함. 하지만 하이퍼 링크을 이용하여 각 노드를 연결하기 위해서는 1000^3의 간선이 생겨서 다른 방식으로 다시 접근. 접근 2. 완선 탐색 기존의 BFS 기법을 이용..
1107_리모컨 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 브루트포스 모든 경우를 탐색. 접근1 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다. 버튼을 이용하여 만들 수 있는 경우에 수를 재귀적으로 탐색하며 버튼 사용의..
10974_모든 수열 https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 브루트 포스 모든 경우의 수를 다 해보는 방법. 모든 수열 모든 수열을 사전순으로 출력하는 문제 ! (2,3,4,5,6) 이라는 수열이 있다고 한다면 맨처음의 수열은 (2,3,4,5,6) 이고 그 다음 수열은 (2,3,4,6,5,) 이다 . 규칙을 만족하면서 만들어지는 마지막 수열은 (6,5,4,3,2)이다. 접근1 처음부터 하나씩 수열을 만들다보면 하나의 규칙을 찾을 수 있는데 처음 수열은 오름차순 , 마지막 수열은 내림차순. 따라서 수열의 오름차순까지 정렬된 i 값을 찾고 i 이후의..
15650_N 과 M(2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 접근1 N과 M(1) 과 매우 흡사한 구조로 수열을 만들어 내는 규칙에서 오름차순으로 만드는 방법만 추가하면 된다!!. 중복을 제거 하기 위하여 a 라는 배열을 사용함. 수열이 오름차순이라서 굳이 필요없지만 관성적으로 사용....
15649_N 과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 브루트포스 모든 경우의 수를 순서대로 탐색하는 알고리즘. 문제에서 브루트포스로 접근이 가능한지의 유무는 시간복잡도를 계산하여 대략적으로 알 수 있다. 접근1 브루트포스를 이용한 방식으로 접근하여 이 문제를 해결하면 생각보다 간단하게(?) 구현 가능하다. N개의 자연수 중에서 중복없이 M개를 고르는 방법. ex) N = 3 , M = 1 -> (1) ,(2) ,(3) N = 3 , M = 2 ->..