22988번: 재활용 캠페인 첫 번째 용기와 두 번째 용기를 가져가서 용량이 $\left(0+1+\frac{13}{2}\right)$㎖ $=$ $7.5$㎖ 남은 용기를, 세 번째 용기와 네 번째 용기를 가져가서 용량이 $\left(2+3+\frac{13}{2}\right)$㎖ $=$ $11.5$㎖ 남은 용 www.acmicpc.net 1. 문제 요약 헤어에센스 용기의 수 n, 용기의 용량 x, 각 용기에 현재 들어있는 양의 수열 arr이 주어진다. 용기 2개를 갖다 주면, 두 용기에 남아있는 잔량 + x/2 만큼 채워진 헤어에센스를 준다. 단, 용기의 용량보다 넘치게 주지는 않는다. 현재 가지고 있는 용기를 이용하여 가득 찬 헤어에센스를 최대 몇 병 만들 수 있는지 구하시오. 2. 접근 방법 이미 가득 ..
3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 1. 문제 요약 자연수 수열이 주어지고 해당 수열의 수들 중, 두 수를 합하여 x와 같은 경우의 수를 구하라. 2. 접근 방법 - 투 포인터 배열을 오름차순으로 정렬합니다. 성능 향상 : x보다 작은 수들만 사용하도록 필터링 i = 0, j = 수열의 크기 - 1 arr[i] + arr[j] == x 일 경우 answer += 1 i += 1, j -= 1 (정렬을 했기 때문에, 해당 수들을 더했을 때, x..
9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 문제 요약 최장 공통 부분 수열의 길이를 구하시오. 2. 접근 방법 LCS는 굉장히 잘 알려진 유명한 알고리즘입니다. 범위를 지정하여 끝의 문자를 비교하는 방식입니다. m = "ACAYKP" n = "CAPCAK" 문자를 하나씩 비교하여 같을 경우는 dp[i][j] = [i-1][j-1] +1 이 됩니다. ACA와 CA를 비교할 경우 A가 같습니다. A를 떼놓고 비교한다면 AC와 C를 비교한값 + 1(A가 같으므..
2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 1. 문제 요약 전깃줄의 좌표가 주어지고 전깃줄이 꼬여있지 않도록 하기 위해 제거해야 할 전깃줄의 최솟값을 구하시오. 2. 접근 방법 A전봇대를 기준으로 정렬한 뒤, B전봇대 값으로 LIS를 사용하면 쉽게 답을 구할 수 있습니다. 백준 - 11053 가장 긴 증가하는 부분 수열 [LIS] 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30,..
11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 1. 문제 요약 수열 A가 주어졌을 때, 최장 증가 부분 수열의 길이를 구하시오. 2. 접근 방법 배열을 순회하며, 현재 숫자의 이전 인덱스의 숫자들 중, 현재 숫자보다 작은 경우, 현재 dp와 찾은 숫자의 dp를 비교하여, 더 큰 값을 현재 dp에 저장한다. 현재 숫자의 이전 숫자가 없는 경우 1을 저장한다. 2 이전 숫자들 중, 1이 가장 작으므로 데려오며, +1을 해준다. 1의 이..
1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. 문제 요약 M * N 의 지도가 주어지고, 해당 지도에는 각 칸의 높이가 표시되어 있다. 현재 위치에서 상, 하, 좌, 우 한 곳으로 이동할 수 있으며, 현재 위치보다 낮은 위치로만 이동할 수 있다. 세준이는 0, 0의 위치에서 시작하여 지도의 가장 우측하단까지 이동하는 방법은 모두 몇 가지인가? 2. 접근 방법 0, 0 에서 가능한 모든 경우의 수를 탐색합니다. 재귀로 구현합니다. def solution(y, x): # 목적지 도착 여부 if y == M-1 ..
1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 1. 문제 요약 N * N 의 대나무 숲이 주어지고, 해당 숲에는 대나무의 양이 적혀있다. 판다는 현재 위치에서 상, 하, 좌, 우 한 곳으로 이동할 수 있으며, 이동한 곳의 대나무 양은 이전 위치보다 많아야 한다. 판다가 가장 많이 이동할 수 있는 횟수는 몇번인가? 2. 접근 방법 모든 대나무 숲을 방문합니다. 재귀 함수로 구현합니다. # 재귀함수로 구현 def solution(y, x): move = 0 for dy, dx in [[y-1, x],..
1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 1. 문제 요약 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 빨강, 초록, 파랑으로 집을 칠할 때, 연속되지 않게 칠할 수 있으며, 최소 비용을 구하라. 2. 접근 방법 먼저 가장 완벽한 알고리즘인 완전탐색으로 구현해 보았습니다. N = int(input()) rgb = [list(map(int, input().split())) for _ in range(N)] answer = 1..
11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 1. 문제 요약 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하시오. 2. 접근 방법 숨어있는 규칙을 찾아봅시다. i : 방법 1 -> 1 2 -> 2 3 -> 3 4 -> 5 5 -> 8 6 -> 13 7 -> 21 자세히 살펴보면 규칙을 발견할 수 있습니다. 현재 인덱스의 방법은 이전의 두 인덱스의 방법의 합과 같습니다. 즉, n = (n-1) + (n-2) 가 됩니다. 이는 피보나치 수열의 형태입니다. 이를 토대로 재귀함수를 이용합니다. def solut..
