JUINTINATION

문제 https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 풀이 루트 없는 트리가 주어진다. 트리의 루트를 1이라고 정했을 때 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력하는 문제입니다. 접근 이진트리라는 조건도 없고 자식노드가 부모노드보다 숫자가 크거나 작다는 조건이 없기 때문에 일반적인 이진탐색트리 관련 알고리즘으로는 문제를 해결할 수 없었습니다. 그래서 DFS와 BFS를 이용하여 그래프를 순회하며..

문제 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 화면에 이모티콘 1개가 입력되어 있는 상태인 영선이가 효빈이에게 다음 규칙에 맞춰 이모티콘을 s개 보내야 하는 문제입니다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 모든 연산은 1초가 걸리고 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 됩니다. 클..

문제 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 수빈이는 현재 점 n(0 ≤ N ≤ 100,000)에 있고, 동생은 점 k(0 ≤ K ≤ 100,000)에 있을 때 수빈이는 걷거나 순간이동할 수 있습니다. 수빈이의 위치가 x일 때 걷는다면 1초 후에 x-1 또는 x+1로 이동하게 되고 순간이동을 하는 경우에는 1초 후에 2x의 위치로 이동하게 될 때 동생을 찾을 수 있는 가장 빠른 시간과 가장 빠..

문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 수빈이는 현재 점 n(0 ≤ N ≤ 100,000)에 있고, 동생은 점 k(0 ≤ K ≤ 100,000)에 있을 때 수빈이는 걷거나 순간이동할 수 있습니다. 수빈이의 위치가 x일 때 걷는다면 1초 후에 x-1 또는 x+1로 이동하게 되고 순간이동을 하는 경우에는 1초 후에 2x의 위치로 이동하게 될 때 동생을 찾을 수 있는 가장 빠른 시간을 구하는 문제입니다...

문제 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 알고리즘은 정점끼리 어떤 순서로 연결돼있는지에 따라 방문 순서..