본문 바로가기

전체207

[백준 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.
[백준 9251번] LCS 난이도: 골드 5 문제 링크:www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이전 글 (링크)에서 소개한 LCS 알고리즘을 이용하여 푸는 문제입니다. 자세한 내용은 링크에 거의 그대로 설명이 되어 있습니다. 코드를 늘 직관적이고 읽기 쉽게 작성하려고 노력하고 있습니다. 혹시나 제 코드 중 의미 전달이 불명확한 경우가 있다면 피드백을 주시면 감사하겠습니다. 2020. 11. 15.
Longest Common Subsequence/Substring (LCS) Algorithm Dynamic Programming 카테고리의 알고리즘입니다. 두 개의 문자열이 있다고 가정합시다. 각각 subject, target이라고 부르겠습니다. subject = ACAYKP, target = CAPCAK이라고 합니다. 이 때, subject = ACAYKP의 부분 수열이라 함은 다음을 가리킵니다. 0, A, CAY, CYP, ACAYKP... 등등. 가장 작은 부분 수열은 공집합이며, 가장 큰 부분 수열은 문자열 그 자신입니다. 여기서 중요하게 짚고 넘어가야 할 점이 있습니다. LCS라는 표현을 쓸 때, longest common SUBSEQUENCE인지, longest common SUBSTRING인지 잘 확인해야 합니다. 번역하면 최장 공통 수열, 최장 공통 문자열이 되겠습니다. 이 둘의 .. 2020. 11. 15.
[백준 17501번] 수식 트리 난이도: 골드 1 문제 링크: www.acmicpc.net/problem/17501 17501번: 수식 트리 수식 트리는 루트가 있는 이진 트리로 2N-1개의 노드가 있습니다. 1번부터 N번까지 노드는 피연산자 노드이며 다른 노드들은 연산자 노드이고 2N-1번 노드가 루트입니다. 연산자 노드는 항상 두 개 www.acmicpc.net 제겐 아직 너무나도 생소한 bfs를 이용하는 문제입니다. DFS는 그래도 문제 한 두 개 풀어봐서 기억이라도 하는데, BFS는 자료구조 책에서만 접해봐서 너무 생소했어요. 접근 방법을 열거하자면... 시작에 앞서, tree_node 구조체를 만든다. 이 구조체는 연산자, 왼쪽 자식 노드, 오른쪽 자식 노드, count 변수를 멤버로 가진다. 전역 array num, sub,.. 2020. 11. 8.
[백준 17498번] 폴짝 게임 난이도: 골드 5 문제 링크: www.acmicpc.net/problem/17498 17498번: 폴짝 게임 첫 번째 줄에 행의 개수 N과 열의 개수 M (2 ≤ N×M ≤ 200,000, 2 ≤ N) 그리고 최대 점프 거리 정수 D (1 ≤ D ≤ 10) 가 주어집니다. i+1 번째 줄에는 i (1 ≤ i ≤ N) 번째 행에 있는 쓰여있는 정수 ai,1, ai,2, www.acmicpc.net 어제 풀었으나 시간 제한에 걸려서 실패했던 문제입니다. (링크) 다이나믹 프로그래밍에 대해 알아보고, 메모이제이션 기법을 활용하여 접근하였더니 성공적으로 풀었습니다. 메모이제이션 개념을 간단히 설명하자면, 중복적으로 계산이 이루어질 법한 상황에, 계산의 값을 미리 담아 둔 배열을 활용하여, 이미 계산이 이루어진 .. 2020. 11. 7.

티스토리툴바