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의 이..
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..
15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 문제 요약 주어진 숫자들 중 M개를 골라 오름차순으로 정렬된 수열을 생성하라. 같은 수를 여러 번 사용해도 된다. 2. 접근 방법 입력받은 숫자들을 오름차순 정렬 재귀함수를 이용하여 수열 생성 3. 파이썬 from sys import stdin input = stdin.readline def solution(depth: int): if depth == M: print(' '.join(map(str, arr))) return for i in range..
15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 문제 요약 1부터 N까지의 숫자들 중 M개를 뽑아 수열을 생성하라. 같은 수를 여러 번 골라도 된다. 2. 접근 방법 대표적인 방법으로 재귀함수를 이용할 수 있습니다. 3. 파이썬 from sys import stdin input = stdin.readline def solution(depth: int): if depth == M: # print(*arr) print(' '.join(map(str, arr))) # 위 방식보다 좀 더 효율적입니다. retu..
