LCS 문제

LCS 문제 LCS란 Longest Common Subsequence 혹은 Longest Common String 의 약자다. LCS 문제는 특정 문자가 같은 지 여부에 따라 테이블에 기록하는 형식으로 길이와 부분 문자열을 구할 수 있다. 즉, 동적계획법을 활용하여 문제를 풀 수 있다. 문제접근법 LCS 문제는 동적 프로그래밍 접근법에 따라 해결한다. 1. 문재의 해를 분석한 후 부분문제로 분할한다. 2. 부분문제의 해를 보고 큰 문제와의 관계식을 세운다.(점화식 설계) 3. 적당한 순서로 dp table을 채운다. 4. table에서 해를 계산한 후에 정확성을 증명한다.동적계획법에서 중요한 부분은 큰문제와 작은문제의 관계로부터 재귀형태를 찾아 dp table을 채우는 것이다. 정확성 증명은 테이블 채우..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 4. 8.

다이나믹 프로그래밍

다이나믹 프로그래밍이 필요한 이유공간을 희생해서 시간을 벌자.현실의 문제들 중에 그대로 컴퓨터로 해결하기에는 어려운 것들이 많다. 해를 구하는데 시간이 오래 걸리거나 메모리 공간을 매우 많이 필요한 경우가 그러하다. 그래도 메모리공간을 담보로 연산속도를 향상 할 수 있는 방법들이 존재한다. 다이나믹 프로그래밍이 그 중에 하나다.적용조건1. 큰 문제를 작은 문제로 나눌 수 있다.2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.기본 아이디어Memoization, DP table피보나치 수열을 예를 들자. 피보나치 수열은 연속 된 두개의 항이 그 다음 항의 합인 수열이다.f(n) = f(n-1) + f(n-2), f(1) = 1, f(2) = 1피보나치 수열은 재귀함수로 구현할 수 있다..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 4. 5.

[파이썬] 백준 4344: 평균은 넘겠지

문제 출처 https://www.acmicpc.net/problem/4344 나의 코드 import sys input = sys.stdin.readline c = int(input()) cases = [[x for x in map(int, input().strip().split())] for _ in range(c)] for case in cases: population = case[0] scores = case[1 : len(case)] score_avg = sum(scores) / population above_avg = 0 for score in scores: if score > score_avg: above_avg += 1 result = above_avg * 100 / population pri..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 4. 3.

[백준] 5639: 이진 검색 트리 파이썬

문제요약 이진탐색트리의 전위순회환 결과를 토대로 해당 트리를 후위순회한 결과를 출력하는 문제입니다. 나의 접근법 1) 전위순회를 통해 이진검색트리를 재현하기 2) 이진검색트리를 후위순회하여 그 순서를 출력하기 활용한 개념 1) 이진탐색트리 코드의 구현 이진탐색트리 def add(self, data: int): """데이터 추가하기""" if self.root is None: self.root = Node(data) return current = self.root while True: if current.value < data: if current.right is None: current.right = Node(data) break current = current.right elif current.valu..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 3. 30.