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 ..
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..
15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 문제 요약 주어진 숫자들 중 M개를 뽑아 조합(Combination)을 만드는 문제입니다. 고른 수열은 오름차순이어야 합니다. 2. 접근 방법 입력받은 숫자들을 오름차순 정렬 재귀함수를 이용하여 조합 생성 3. 파이썬 from sys import stdin input = stdin.readline def solution(start: int, depth: int): if depth == M: print(' '.join(map(str, arr))) re..
15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 문제 요약 주어진 숫자들 중 M개를 뽑아 순열(Permutation)을 생성하는 문제입니다. 출력 시 오름차순으로 정렬하여야 합니다. 2. 접근 방법 순열을 생성하는 대표적인 방법으로 재귀함수를 이용할 수 있습니다. 입력받은 숫자들을 오름차순 정렬 재귀함수를 이용하여 순열 생성 3. 파이썬 from sys import stdin input = stdin.readline def solution(depth: int): if depth == M: prin..
15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 문제 요약 1부터 N까지의 자연수를 사용하여 길이가 M인 수열을 생성하라 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 2. 접근 방법 재귀 함수를 사용합니다. 15650(조합) 과 15651 을 적절히 섞으면 됩니다. 3. 파이썬 from sys import stdin input = stdin.readline def soluti..
1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 해당 문제는 주어진 숫자가 소수인지 판별하는 문제입니다. 낮은 난이도이기에 어떠한 방식으로 풀어도 통과가 됩니다. 대표적인 3가지 방법으로 풀어보겠습니다. 1. 일반적인 방법 가장 일반적인 방법으론 2부터 1씩 늘려가며 해당 숫자가 나누어 떨어지는지 보는 방법입니다. // Java static boolean isPrime(int number) { if (number
