본문 바로가기

알고리즘, 문제해결103

[백준 2014번] 소수의 곱 난이도: 골드 2 문제 링크: www.acmicpc.net/problem/2014 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 언뜻 봐서는 어려워 보이는 수 관련 문제입니다. 문제 분류는 수학, 자료 구조, 정수론, 우선순위 큐라고 하네요. 얼핏 생각하면 다소 어려운 문제이긴 합니다. 숫자에 곱셈을 하는 정해진 횟수가 존재하지 않다 보니, 2, 2*2, 2*2*2, 2*2*2*....*2 등도 존재할 수 있기 때문에, 곱을 얼마나 해야 할지 감이 오질 않았어요. 고민 끝에 제가 .. 2020. 11. 21.
[백준 9935번] 문자열 폭발 난이도: 골드 4 문제 링크: www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문자열을 다루는 문제입니다. 처음에는 정말로 단순하게 접근했다가, 답은 잘 나오는데 시간 초과가 떠 버리는 바람에 (...) 결국 다시 생각해서 접근했습니다. 제가 직접적으로 스택을 사용하지는 않았지만, 문제 분류 중에 스택이 적혀 있습니다. 실제로 많은 분들이 스택을 이용해서 문제를 해결하셨더라구요. 제가 접근한 방법은 아래와 같습니다. 결과 문자열을 담기 위한 c.. 2020. 11. 21.
[백준 1958번] LCS 3 난이도: 골드 3 문제 링크: www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. (각 문자열의 길이는 100보다 작거나 같다) www.acmicpc.net 앞에서 몇 번 다루었던 LCS 문제입니다. 차이점이라면 이번에는 문자열 3개를 비교한다는 점! 따라서 dynamic programming 기법을 이용하기 위한 array 역시 3차원을 사용합니다. 기본적인 LCS algorithm에 대한 설명은 이 글을 참고하시기 바랍니다. 주의할 점은 문제에서 LCS가 Longest Common Subsequence를 뜻한다고 명시하고 있습니다. 즉, 연속된 문자만을 인정한다는 의미입니다... 2020. 11. 15.
[백준 15483번] 최소 편집 난이도: 골드 4 문제 링크: www.acmicpc.net/problem/15483 15483번: 최소 편집 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. www.acmicpc.net LCS와 유사한, 다이나믹 프로그래밍을 이용하는 문제입니다. (LCS algorithm에 대한 설명은 여기로) 두 개의 string: subject, target가 있다고 합시다. subject = 'for', target = 'whileforif' 로 하겠습니다. subject에 적절한 연산을 통해, target과 같게 만들고자 합니다. 여기서 연산이란, 삽입, 삭제, 수정 3가지를 의미합니다. 접근 방법은 다음과 같습니다: 2-dimensio.. 2020. 11. 15.
[백준 5582번] 공통 부분 문자열 난이도: 골드 5 문제 링크: www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net LCS algorithm을 이용하여 푸는 문제입니다. 다만 이전에 소개했던 longest common substring이 아닌, longest common subsequence의 길이를 구하는 문제입니다. 즉, 연속을 허용하지 않는다는 의미입니다. 자세한 내용은 알고리즘 설명 글에 다루었습니다. 제가 접근한 방법은 아래와 같습니다: 공통 부문 문자열의 최대 길이를 담기 .. 2020. 11. 15.
[백준 9252번] LCS 2 난이도: 골드 5 문제 링크: www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 앞의 문제 9251: LCS와 더불어, 이전에 설명한 (링크) LCS 알고리즘을 이용하여 푸는 문제입니다. 자세한 내용은 링크에 거의 그대로 설명이 되어 있습니다. 코드를 늘 직관적이고 읽기 쉽게 작성하려고 노력하고 있습니다. 혹시나 제 코드 중 의미 전달이 불명확한 경우가 있다면 피드백을 주시면 감사하겠습니다. 2020. 11. 15.

티스토리툴바