분할정복
-
Problem 1 : https://www.acmicpc.net/problem/14600 14600번: 샤워실 바닥 깔기 (Small) 첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 2) 가 주어진다. 이때 바닥의 크기는 2K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x, y (1 ≤ x, y ≤ 2K) www.acmicpc.net Problem 2 : https://www.acmicpc.net/problem/14600 14600번: 샤워실 바닥 깔기 (Small) 첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 2) 가 주어진다. 이때 바닥의 크기는 2K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x..
[백준/14600/14601] 샤워실 바닥 깔기 (Python)Problem 1 : https://www.acmicpc.net/problem/14600 14600번: 샤워실 바닥 깔기 (Small) 첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 2) 가 주어진다. 이때 바닥의 크기는 2K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x, y (1 ≤ x, y ≤ 2K) www.acmicpc.net Problem 2 : https://www.acmicpc.net/problem/14600 14600번: 샤워실 바닥 깔기 (Small) 첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 2) 가 주어진다. 이때 바닥의 크기는 2K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x..
2024.01.03 -
Problem : https://www.acmicpc.net/problem/10090 10090번: Counting Inversions A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example www.acmicpc.net Difficulty : Platinum 5 Status : Solved Time : 00:..
[백준/10090] Counting Inversions (Python)Problem : https://www.acmicpc.net/problem/10090 10090번: Counting Inversions A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example www.acmicpc.net Difficulty : Platinum 5 Status : Solved Time : 00:..
2023.12.06 -
Problem : https://www.acmicpc.net/problem/2104 2104번: 부분배열 고르기 크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[j]) × min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에 i부터 j까지의 최솟값을 곱 www.acmicpc.net Difficulty : Platinum 5 Status : Solved Time : 00:42:21 문제 설명 더보기 크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[..
[백준/2104] 부분배열 고르기 (Python)Problem : https://www.acmicpc.net/problem/2104 2104번: 부분배열 고르기 크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[j]) × min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에 i부터 j까지의 최솟값을 곱 www.acmicpc.net Difficulty : Platinum 5 Status : Solved Time : 00:42:21 문제 설명 더보기 크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[..
2023.11.28 -
Problem : 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 Difficulty : Platinum 5 Status : Solved Time : 00:22:04 문제 설명 더보기 N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오. 버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법..
[백준/1517] 버블 소트 (Python)Problem : 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 Difficulty : Platinum 5 Status : Solved Time : 00:22:04 문제 설명 더보기 N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오. 버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법..
2023.11.23 -
Problem : https://www.acmicpc.net/problem/17401 17401번: 일하는 세포 출력은 N개의 줄로 구성되며, i 번째 줄에는 N개의 정수 xi1, xi2, ..., xiN를 공백으로 구분하여 출력해야 한다. xij는 0초 때 거점 i 에서 출발하여 정확히 D초 때 거점 j에 위치하게 되는 경로의 수를 1 www.acmicpc.net Difficulty : Platinum 5 Status : Solved Time : 00:17:31 문제 설명 더보기 사람의 세포 수, 약 37조 개. 세포들은 몸 속에서 오늘도 열심히 일하고 있다. 그중에서도 우리의 적혈구는 혈관을 타고 돌아다니며 산소와 영양소를 운반해주는 중요한 역할을 맡고있다. 적혈구는 심장이나 폐 같은 거점들을 돌아다..
[백준/1740] 일하는 세포 (Python)Problem : https://www.acmicpc.net/problem/17401 17401번: 일하는 세포 출력은 N개의 줄로 구성되며, i 번째 줄에는 N개의 정수 xi1, xi2, ..., xiN를 공백으로 구분하여 출력해야 한다. xij는 0초 때 거점 i 에서 출발하여 정확히 D초 때 거점 j에 위치하게 되는 경로의 수를 1 www.acmicpc.net Difficulty : Platinum 5 Status : Solved Time : 00:17:31 문제 설명 더보기 사람의 세포 수, 약 37조 개. 세포들은 몸 속에서 오늘도 열심히 일하고 있다. 그중에서도 우리의 적혈구는 혈관을 타고 돌아다니며 산소와 영양소를 운반해주는 중요한 역할을 맡고있다. 적혈구는 심장이나 폐 같은 거점들을 돌아다..
2023.11.13 -
Problem : https://www.acmicpc.net/problem/1634 1634번: 완전 이진트리 ‘k-레벨 완전 이진 트리’는 모든 노드의 분지수(차수)가 0이거나 혹은 2이고, 레벨 1에 있는 노드 수가 2^0, 레벨 2에 있는 노드수가 2^1, ... , 레벨 k에 있는 노드 수가 2^(k-1)이며, 총 노드 수는 2^k-1 www.acmicpc.net Difficulty : Gold 2 Status : Solved Time : 00:14:26 문제 설명 더보기 ‘k-레벨 완전 이진 트리’는 모든 노드의 분지수(차수)가 0이거나 혹은 2이고, 레벨 1에 있는 노드 수가 2^0, 레벨 2에 있는 노드수가 2^1, ... , 레벨 k에 있는 노드 수가 2^(k-1)이며, 총 노드 수는 2^..
[백준/1634] 완전 이진트리 (Python)Problem : https://www.acmicpc.net/problem/1634 1634번: 완전 이진트리 ‘k-레벨 완전 이진 트리’는 모든 노드의 분지수(차수)가 0이거나 혹은 2이고, 레벨 1에 있는 노드 수가 2^0, 레벨 2에 있는 노드수가 2^1, ... , 레벨 k에 있는 노드 수가 2^(k-1)이며, 총 노드 수는 2^k-1 www.acmicpc.net Difficulty : Gold 2 Status : Solved Time : 00:14:26 문제 설명 더보기 ‘k-레벨 완전 이진 트리’는 모든 노드의 분지수(차수)가 0이거나 혹은 2이고, 레벨 1에 있는 노드 수가 2^0, 레벨 2에 있는 노드수가 2^1, ... , 레벨 k에 있는 노드 수가 2^(k-1)이며, 총 노드 수는 2^..
2023.10.30