http://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net # 조건 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제 예 ACAYKP와 CAPCAK의 LCS는 ACAK # 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져있으며, 최대 1000글자로 이루어져 있다. ..

http://www.acmicpc.net/problem/23083 23083번: 꿀벌 승연이 첫째 줄에 \(N\), \(M\)이 공백으로 구분되어 주어진다. 다음 줄에는 구멍 칸의 개수 \(K\)가 주어진다. 이어서 \(K\)개 줄에 구멍 칸의 정보 \(x_i\), \(y_i\)가 공백으로 구분되어 주어진다. 이는 \(i\)번째 www.acmicpc.net # 조건 승연이가 사는 벌집은 조금 특이한 구조로 되어있다. 벌집은 N행 M열의 격자로 이루어져 있고, 각 칸은 정육각형 모양 같은 행에 위치한 두 칸을 비교했을 때, 짝수번째 열의 칸은 홀수 번째 열의 칸보다 반 칸 아래에 위치 두 육각형 칸이 하나의 변을 공유하고 있다면 서로 인접하다. 벌집 내에서는 아래쪽, 오른쪽 위, 오른쪽 아래 칸으로만 이동..

http://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net # 조건 위 그림은 크기가 5인 정수 삼각형 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하여라 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택 가능하다. 삼각형의 크기는 1 이상 500이하 # 접근 방법 DP를 이용하여 각 수에 누적합을 구해주고 가장 큰 수를 출력해주면 된다. 입력을 층마다 받기 때문에 2차원 리스트를 사용한다 ..

백준 1149_RGB 거리 조건 집이 N개가 있고, 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각 집을 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하라. 1번 집의 색은 2번 집의 색과 같지 않아야한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i (2

http://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net # 조건 수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열을 구하라 # 접근 방법 이전의 하위 문제처럼 DP를 이용하여 이전 값들을 모두 순회한다면 수열 A의 크기 1,000,000 이하 이므로 시간초과가 난다. 따라서, 현재 값들을 dp테이블에 추가해주며, dp에서 가장 큰 수보다 크다면 append, 아니라면 들어갈 수 있는 자리를 찾아서 넣어준다. 찾는 모듈은 bisect를 이용해준다. im..

http://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 = {10, 20, 10, 30, 20, 50} 인 경우 가장 긴 증가하는 부분 수열은 10, 20, 30, 50 이고 길이는 4이다. # 접근 방법 dp를 이용해준다. 현재 인덱스의 숫자를 기준으로 이전의 숫자를 모두 훑어 준다. 1번부터 채워가..

http://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net # 조건 n가지 종류의 동전이 있고 각각의 동전이 나타내는 가치는 다르다. 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶을 때, 그 경우의 수를 구하시오 각 동전은 몇 개라도 사용 가능하다. 동전의 구성이 같은데, 순서만 다른 것은 같은 경우 # 접근 방법 다이나믹 프로그래밍을 이용해서 풀어주면 될 것 같다. 가치의 합 +1 만큼의 dp테이블을 만들어 주고 각 가치를 만들 수 있는 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # 조건 가장 왼쪽 위, 집의 좌표 (1,1) 가장 오른쪽 아래, 학교의 좌표 (m,n) 격자의 크기 m,n과 물이 잠긴 지역의 좌표 담은 2차원 배열 puddles가 매개변수 오른쪽과 아래쪽으로만 움직일 수 있으며 학교까지 갈 수 있는 최단 경로의 개수를 1,000,000,007로 나눈 나머지를 return 하여라 # 접근 방법 현재 칸에 올 수 있는 경로의 수 -> 왼쪽과 위쪽칸의 합과 같다...

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 조건 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임 계단을 밟으면 해당 계단에 쓰여 있는 점수를 얻게 된다. 아래 규칙을 지켜서 얻을 수 있는 점수의 최댓값을 구하라 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다..