YANGORITHM

문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 나무 높이의 범위가 엄청 넓으므로 이분 탐색을 통해 절단기의 높이를 정한다. 절단기의 최소 높이는 0이고 최대 높이는 나무들 중에 최대값과 같다. 이 사이에서 절단기의 높이를 찾으면 된다. 이분 탐색을 이용하므로 중간점을 절단기의 높이로 설정하면서 문제 조건 M을 만족하는지 확인한다. 1. 만약 중간점으로 잘랐을 때 가져가는 나무의 길이가 M보다 ..

문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 문제 조건 중 "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고" 를 만족하기 위해 인접 리스트 형식으로 입력을 받은 후 정렬을 해줘야 한다. 그 후 dfs와 bfs를 진행 하면 된다. 코드 python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..

문제 www.acmicpc.net/problem/17977 17977번: Triangulation A regular n-sided polygon P can be partitioned into n − 2 triangles by adding non-crossing line segments connecting two vertices of P. For example, a square can be partitioned into two triangles, a regular pentagon can be partitioned into three triangles www.acmicpc.net 풀이 각 정다각형에서 다음과 같은 답이 나온다. 1. 정육각형의 경우 내부에 정삼각형이 있어야 거리가 최소가 된다. 이때 최대거리..

문제 www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 다음과 같은 점화식을 만든다. 1. dp[i][0] = 수열에서 i번까지 선택했을 때 연속합의 최대값, 중간에 삭제를 진행하지 않음 2. dp[i][1] = 수열에서 i번까지 선택했을 때 연속합의 최대값, 이전에 삭제를 진행했다 or 현재 값을 삭제한다. n개의 수열 중에서 dp[n][0]와 dp[n][1] 까지 모두 구했을 때, 그 중에서 최대값을 찾으면 된다. 1번을 구하기 위한 점화식은 다음과 같다..

문제 www.acmicpc.net/problem/8895 8895번: 막대 배치 높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자. www.acmicpc.net 풀이 다음과 같은 점화식을 만든다. dp[n][l][r] = n개의 막대가 있을 때, 왼쪽에서 l개 오른쪽에서 r개 막대가 보인다. 그리고 길이 1인 막대가 왼쪽에 있을 때, 오른쪽에 있을 때, 가운데 있을 때로 나누어서 생각해 본다. 1. 길이 1인 막대가 왼쪽에 있을 때 : 이 막대가 사라졌을 때 왼쪽에서 보이는 막대가 1개 사라지므로 점화식은 다음과 같다. dp[n-1][l-1][r] 2...

문제 https://www.acmicpc.net/problem/6603 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 www.acmicpc.net 풀이 집합 S에 저장된 숫자들에 대해서 6개를 선택해서 만들 수 있는 조합을 출력하는 문제이다. 순열을 이용해서 조합을 구할 때는, 몇 개를 선택해서 조합을 이룰건지 알아야 한다. 이 때, 선택한 수들은 같은 숫자로 바꾸고 그 외 숫자들도 같은 수로 바꿔서 순열을 구하면 조합을 구할 수 있다. 예를 들어, 1 2 3 4 에서 3개를 선택해서 조합을 이루는 수를 구한다고 하면..

문제 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 풀이 모든 도시를 방문하고, 도시의 방문 순서를 다르게 하는 문제이다. 도시의 수는 최대 10개이다. 그러므로 가능한 방문 순서의 수는 10! 이 되고, 이를 순열을 이용해 나타낸다. d 배열을 이용해 도시를 저장하고, next_permutation() 함수를 이용해 d..

문제 https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 www.acmicpc.net 풀이 그래프 탐색과 이분 탐색을 이용해서 해결하는 문제이다. 이분 탐색을 통해 중량 값을 찾고, 그래프 탐색을 통해 해당 중량 값으로..

문제 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수 또는 0이다. 마 www.acmicpc.net 풀이 주사위의 6면을 상하좌우앞뒤로 구분을 해서 생각한다. dice[6]에서 0:상, 1:뒤, 2:우, 3:좌, 4:앞, ..

문제 https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net 풀이 수열의 왼쪽에 있는 수가 오른쪽에 있는 수보다 몇 개가 더 큰지 알아내면 된다. 그 수 만큼 버블 정렬에서 swap이 일어나기 때문이다. 수열 1 3 5 2 4 의 경우 3은 2보다 크고, 5는 2와 4보다 크므로 버블 정렬에서 swap이 총 세번 일어난다. 병합 정렬을 이용해 왼쪽에 있는 수가 오른쪽에 있는 수보다 몇 개가 더 큰지 구할 수 있다. R 배열의 값을 새로운 정렬..