알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 간단한 그래프 문제였습니다. X -> Y 까지 가는데 거쳐가야하는 수를 구하는 문제였습니다. 예시를 통해 확인해보겠습니다. 7 -> 3 을 가는데 7 -> 2 -> 1 -> 3 으로 이동할 수 있습니다. 따라서 촌수가 3이 됩니다. M개의 line이 주어졌을때, X와 Y를 서로 양방향으로 저장해줍니다. 시작점을 queue에 넣어준 뒤, 갈 수 있는 점들을 확인..

문제 링크입니다. https://www.acmicpc.net/problem/2479 2479번: 경로 찾기 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들 www.acmicpc.net 저는 2가지 방법으로 접근해서 풀었습니다. 1. 현재 지점에서 모든 이진 코드를 확인해, 1개가 차이날 경우 해당 지점을 탐색한다. 2. 모든 이진 코드를 1의 갯수로 나눈 뒤, 1의 갯수가 1개 차이나는 곳만 확인한다. 첫번째 방법은 짜기 쉬운 대신에 시간이 오래 걸렸고, 두번째 방법은 복잡했던 대신에 시간이 짧았습니다. 먼저 첫번째 방법부터 설명하겠습니다. 이진 코드를 s..

문제 링크입니다! https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 1번 PD의 경우 1번 -> 4번 -> 3번 2번 PD의 경우 6번 -> 2번 -> 2번 -> 5번 -> 4번 3번 PD의 경우 2번 -> 3번 순으로 공연을 맡습니다. 1번을 방송하기 위해서는 선행이 없음으로 바로 방송할 수 있습니다. 2번의 경우는 6번을 먼저 방송 후 방송해야 합니다. 3번의 경우는 4번과 2번을 먼저 방송해야 합니다. 따라서 X번 -> ..

문제 링크입니다! https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 그래프를 사용한 DP 문제였습니다. 먼저 지을 수 있는 건물을 지은 다음, 해당 건물을 짓고 난 다음에 지을 수 있는 건물을 지어보는 식으로 최댓값을 찾아가는 문제였습니다. ex) 1 -> X , 2 -> X , 3 -> 2 , 4 -> 1,2 , 5 -> 1,3 (A -> B는 B를 짓고 나서 A를 지을 수 있다는 의미입니다.) 해당 경우, 1번과 2번을 먼저 짓습니..

문제 링크입니다. https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A 4 -> 8 -> 81 -> 162 이와 같은 방법으로 최소 횟수는 5입니다. 1. 주어지는 수의 범위가 10^9이기 때문에 int 범위는 넘습니다. 따라서 long long 형으로 선언해줍니다. 2. 처음에 큐에 (A,0)를 저장해서 BFS를 시작합니다. 3. X*2, X*10+1 각각 B ..