알고리즘34 LCS LCS 백준 9251번 문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 문제 2. 풀이 방법 2.1 dp 이 문제는 dp를 사용해서 풀 수 있다. 다만 주어지는 문자열이 2개이기 때문에 2개의 변수를 사용해서 점화식을 만들어야 한다. d[i][j]를 문자열_1의 i번째와 문자열_2의 j번째까지의 LCS라고 하자. 그러면 d 행렬의 가장 오른쪽 아래있는 값이 이 문제의 답이 될 것이다. 예시.. 2023. 6. 4. 크-게 만들기 크게 만들기 백준 2812번 문제 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제 2. 풀이 방법 2.1 내림차수 만들기 2.1.1 개념 주어진 숫자에서 K개를 지웠을 때 가장 큰 수가 되게 하려면 숫자의 앞자리(왼쪽)가 가장 커질 수 있는 방향으로 수를 지우면 될 것이다. 즉 특정 자릿수를 지워 숫자를 내림차순이 되는 형태로 만들면 가장 큰 수가 될 수 있다. 숫자를 내림차수로 만드는 데에는 스택을 활용할 수 있다. 다음과 같이 예시가 주어졌다고 하자 10자리, 지울 수의 개수 = 4, 숫자 = 4177252.. 2023. 5. 21. 징검다리 건너기 징검다리 건너기 2019 카카오 개발자 겨울 인턴쉽 https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 2. 풀이 2.1 풀이 방법 캐릭터들이 징검다리를 건널 때마다 징검다리의 숫자가 1씩 깎이고 징검다리의 숫자가 0이 되면 캐릭터는 그 징검다리를 뛰어넘을 수 있으며, 캐릭터는 k만큼 건너뛸 수 있다. 만약 숫자가 0인 징검다리가 연속해서 k만큼 이어져있으면 캐릭터는 징검다리를 뛰어 넘을 수 없으므로 징검다리를 건너갈 수 없다. 따라서 .. 2023. 3. 10. LCA2 LCA2 백준 11438번 문제 https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 2.1.1 LCA 트리에서 공통의 조상을 찾는 것은 LCA 알고리즘을 통해 해결할 수 있다. LCA 알고리즘은 다음과 같은 과정으로 두 노드 간의 공통 조상을 찾는다. 1. 두 노드의 깊이가 다르면 같아질 때까지 한쪽 노드의 깊이를 올린다. 2. 두 노드가 같아질때까지 깊이를 한칸씩 올린다. 다음과 같은 트리가 주어졌.. 2023. 2. 20. 이전 1 2 3 4 ··· 9 다음
