JUINTINATION

문제 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 여러 섬으로 이루어진 나라에서 한 섬과 다른 섬을 잇는 다리 하나를 만든다고 할 때 가장 짧은 다리의 길이를 구하는 문제입니다. 이때 섬은 동서남북으로 붙어있는 땅을 의미합니다. 접근 어떤 섬과 다른 섬 사이를 잇는 다리를 만들어야 하므로 각 섬이 다른 섬이라는 것을 표시해야 합니다. 여러 가지 알고리즘을 사용할 수 있지만 저는 dfs 알고리즘을 이용하여 각 섬에 번호를 정해주었습니다. 입력..

문제 https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 풀이 지난 BFS 스페셜 저지 문제에 이어 정점에 1부터 n까지 번호가 매겨져 있는 양방향 그래프를 표현한 트리가 있을 때 어떤 수열이 DFS 알고리즘을 이용했을 때 해당 수열의 순서대로 방문할 수 있는지 확인하는 문제입니다. 이때 정점을 방문하는 순서는 중요하지 않습니다. 접근 BFS, DFS 알고리즘은 정점끼리 어떤 순서로 연결돼있는지에 따라 방문 순서..

문제 https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 풀이 정점에 1부터 n까지 번호가 매겨져 있는 양방향 그래프를 표현한 트리가 있을 때 어떤 수열이 BFS 알고리즘을 이용했을 때 해당 수열의 순서대로 방문할 수 있는지 확인하는 문제입니다. 이때 정점을 방문하는 순서는 중요하지 않습니다. 접근 BFS, DFS 알고리즘은 정점끼리 어떤 순서로 연결돼있는지에 따라 방문 순서가 달라집니다. 하지만 이 문제에서는 방문 방문가 먼저 나온 뒤에 이 순서대로 출력이 가능한지 확인해야 합니다. 그래서 저는 정점에 연결된 다른 정점들을 ArrayList 배열인 list로 표..

문제 https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 풀이 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 하고 두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수일 때 1개의 순환선과 각 역과 순환선 사이의 거리를 구하는 문제입니다. 접근 dfs를 이용하여 방문한 적이 있는 역으로 다시 돌아왔다면 해당 역을 기준으로 순환선이 만들어지고 그 안에 있는 모든 역에 순환선이라..

문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 두 전봇대 a와 b 사이에 설치된 전깃줄 중에 몇 개의 전깃줄을 없애 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 문제로 LIS(Longest Increasing Subsequence)를 응용하여 해결했습니다. 코드 자바 탑다운 방식을 이용한 코드입니다. poleA 배열은 전봇대 a에 설치된 전깃줄의 위치를 의미하며 arr 배열은 임의의 수 x..

문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 11053번과 11722번 문제에서 사용했던 LIS(Longest Increasing Subsequence)와 LDS(Longest Decreasing Subsequence)를 동시에 사용해서 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족하는 바이토닉 수열 중 가장 긴 수열의 길이를 구하는 문제입니다. 예를 들어, {10, 2..