알고리즘, 문제해결/알고리즘 문제풀이80 [백준 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. [백준 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. [백준 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. 이전 1 ··· 9 10 11 12 13 14 다음
