[Algorithm] 볼링공 고르기
문제 A, B 두 사람이 볼링을 치고 있습니다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 합니다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여됩니다. 또한 같은 무게의 공이 여러개 있을 수 있지만, 서로 다른 공으로 간주합니다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재합니다. 예를 들어 N이 5이고, M이 3이며 각각의 무게가 차례대로 1, 3, 2, 3, 2일때 각 공의 번호가 차례대로 1번부터 5번까지 부여됩니다. 이때 두 사람이 고를 수 있는 볼링공 번호의 조합을 구하면 다음과 같습니다. (1번, 2번), (1번, 3번), (1번, 4번), (1번, 5번), (2번, 3번), (2번, 5번), (3번, 4번), (4번, 5번) 결과..
[Algorithm] 만들 수 없는 금액
문제 동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요. 예를 들어, N = 5 이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다. 또 다른 예시로, N = 3 이고, 각 동전이 각각 3원, 5원, 7원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다. 입력 조건 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1 return 1 2. if 리스트의 최댓값 리스트의 2번째 ..
[Python] range함수 사용법
1. range(10) >>> 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 2. range(1,11) >>> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 3. range(0, 20, 2) >>> 0, 2, 4, 6, 8, 10, 12, 14, 16, 18 4. range(20, 0, -2) >>> 20, 18, 16, 14, 12, 10, 8, 6, 4, 2
[Algorithm] 최장 증가 부분 수열(LIS)
원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. {6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 {2, 5, 8, 7} 이고, 길이는 4 {2, 5}, {2, 7} 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것은 {2, 5, 8, 7} {10, 20, 10, 30, 20, 50} 이라는 배열이 있을 경우, LIS는 {10, 20, 30, 50} 이고, 길이는 4 D[i] = arr[i]를 마지막 원소로 가지는 부분 수열의 최대길이 라고 정의할 때, 가장 긴 증가하는 부분 수열을 계산하는 점화식을 작성해보면, 다음과 같다. (DP 테이블..
