Always Be Wise

▶ 문제 : https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net ##### 문제 ##### # 입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 # 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. # N은 2, 4, 8, 16, 32, 64, 128 중 하나이..

분할 정복법은 주어진 문제를 부분 문제로 나누고(Divide), 각각의 부분 문제들을 해결/정복(Conquer)하여 본래의 문제를 해결하는 알고리즘을 의미한다. # 분할정복을 이용하여 1부터 N까지의 합 구하기 def consecutive_sum(start, end) if start == end: return start mid = (start + end) // 2 return consecutive_sum(start, mid) + consecutive_sum(mid+1, end) ▶ 관련 링크

▶ 문제 : https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net ##### 문제 ##### # 사대의 위치와 동물들의 위치가 주어졌을 때, # 잡을 수 있는 동물의 수를 출력하는 프로그램을 작성하시오. ##### 입력 ##### # 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), # 동물의 수 N (1 ≤ N ≤ 100,000), # 사정거리 L (1 ≤ L ≤ 1,000,..

▶ 문제 : https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net ##### 문제 ##### # 산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, # 이 중 두 개의 서로 다른 용액을 혼합하여 # 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에는 전체 용액의 수 N이 입력된다. # N은 2 이상 100,000 이하이다. # 둘째 줄에는 용..

▶ 문제 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ##### 문제 ##### # 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. # 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) #..

▶ 문제 : https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net ##### 문제 ##### # 적어도 M미터의 나무를 집에 가져가기 위해서 # 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. # 둘째 줄에는 나무의 높이가 주어진다. # 나무의 높이의 합은 항상 M보다 크..

▶ 문제 : https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net ##### 문제 ##### # C개의 공유기를 N개의 집에 적당히 설치해서, # 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 #공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. # ..

▶ 문제 : https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net ##### 문제 ##### # 적어도 M미터의 나무를 집에 가져가기 위해서 # 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. # 둘째 줄에는 나무의 높이가 주어진다. # 나무의 높이의 합은 항상 M보다 크..

이분 탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값(X)을 찾는 알고리즘을 의미한다. X를 찾는 과정은 다음과 같다. 우선, 배열의 중간 값을 X와 비교한다. X가 해당 중간 값보다 작으면 탐색의 대상이 되는 배열을 중간 값 기준 좌측의 데이터로, 중간 값보다 크면 우측의 데이터로 조정한다. X를 찾을 때까지 이 과정을 반복한다. 이분 탐색의 시간 복잡도는 O(logN)이다. ### 직접 구현 ### def binary_search(target, A, left, right): if left > right: return False mid = (left + right) // 2 if target == A[mid]: return True elif target < A[mid]: return binary_s..

▶ 문제 : https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net ▶ 관련 링크 2021.11.17 - [알고리즘] - 재귀 호출(Recursive Call)이란? 재귀 호출(Recursive Call)이란? 재귀 호출(Recursive Call)이란 함수 내부에서 함수가 자기 자신을 또다시 호출하는 행위를 의미한다. ▶ 재귀호출의 일반적인 형태 # 공통적으로 Base Case를 지정하고, # 조건에 맞는 경우가 아니라면 always-be-wise.tistory.com