알고리즘39 IOIOI(KMP 알고리즘) IOIOI 백준 5525번 문제https://www.acmicpc.net/problem/5525 5525번: IOIOIN+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇www.acmicpc.net 1. 문제 2. 풀이2.1 KMP 알고리즘2.1.1 아이디어이 문제는 주어진 문장열에서 특정 문자열이 몇 개나 있는지를 찾는 문제이다.이 문제는 다음과 같이 단순하게 문자열의 단어를 처음부터 비교하는 것으로 해결할 수 있다.주어진 각 문자열이 다음과 같다고 하자. [ 단어 찾기 그_1] [ 단어.. 2024. 6. 10. 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. 이전 1 2 3 4 5 ··· 10 다음
