2024.04.08(월) TIL

오늘 한 일 분할 정복 개념 정리 분할정복은 동적계획법과 함께 문제를 해결하는 알고리즘 패러다임 중에 하나다. 문제가 최적부분구조이고 큰 문제를 작은 문제로 쪼갤 때 그 해결책들을 쌓아서 큰 문제를 해결할 수 있을 경우 분할정복 알고리즘을 사용할 수 있다. 분할 정복 알고리즘을 사용할 경우, 해답 간의 재귀형태를 찾아야한다. 병합정렬, 이진탐색의 경우 분할정복 알고리즘을 해결할 수 있다. 동적계획법 정리 다이나믹 프로그래밍 동적계획법은 분할 정복 알고리즘과 함께 문제를 해결하는 알고리즘 패러다임 중에 하나다. 문제가 최적부분구조이고 큰 문제에서 하위문제 해결책이 중복해서 호출이 될 경우에는 동적계획법을 사용하는 것이 효율적이다. 동적계획법은 하위 문제의 연산 결과를 별도로 저장한 후 큰 문제에서 작은 문..

• format_list_bulleted 기록/정글
• · 2024. 4. 8.

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.

2024.04.03(수)

백준 4344: 평균은 넘겠지 백준 4344: 평균은 넘겠지 배열을 활용한 문제였다. 입력값을 매직넘버로 바꿔서 오류가 계속 났다. 문제를 다 푼 후에 다른 사람들은 어떻게 풀었는지 인터넷에서 확인했다. 내 코드보다 간결하고 구조도 잡혀 있었다. 문제와 별로 관련 없는 부분들은 별도의 변수를 사용하지 않은 대신에 주석으로 의미를 설명했다. 같은 기능의 코드라도 길이가 더 짧으니 읽는 데에도 부담이 덜어졌다. 코드가 구조화되어 있으니 각각의 코드블럭이 어떤 의미를 가지는지도 파악하기가 쉬웠다. 좋은 코드가 뭔지는 내 수준으로 명확하게 정의하기에는 주제를 넘는 것 같다. 그래도 이번 문제를 통해 확인한 것이 있다면 ① 돌아가는 코드 ② 동일 기능에서 짧은 코드 ③ 구조화 되어 있는 코드 인 것 같다. 자료구..

• format_list_bulleted 기록/정글
• · 2024. 4. 4.

최소신장트리 문제

MST 개념 MST 개념의 유래 같은 기능의 제품일 때 재료가 더 적은 쪽이 가성비가 좋습니다. 회로를 설계할 때도 마찬가지입니다. 핀의 개수가 동일할 때 전선의 길이가 짧은 회로가 더 좋은 회로입니다. 핀을 정점, 전선을 간선이라고 할 때 모든 정점을 연결한 비순환적 그래프 형태를 최소신장트리라고 합니다. 비순환적이기 때문에 트리이고 그래프를 펼치는(span) 형태이기 때문에 신장트리라고 합니다. 간선의 가중치가 최소가 되게끔 트리를 만드는 것이기 때문에 최소신장트리입니다. 최소신장트리란? 그래프에서 모든 노드를 연결할 때 간선들의 가중치의 합이 최소가 되는 트리를 최소신장트리라고 합니다. 간선의 개수는 노드의 개수보다 1개 작습니다. 최소신장트리 문제 그래프를 최소신장트리로 펼치는 문제를 최소신장트리..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 4. 3.

Union-Find(합집합 찾기)

개념 서로소 집합과 자료구조 서로소 집합이란 공통 원소가 없는 집합입니다. 서로소 집합 자료구조란 서로소 부분 집합들로 나눠진 원소들의 데이터를 처리하기 위한 자료구조입니다. 서로소 집합 자료구조는 합치기(union)연산과 찾기(find)연산으로 조작할 수 있습니다. 서로소 집합 찾기의 메커니즘 1. 노드의 집합을 확인합니다. 2. 부모테이블을 갱신합니다. 3. 부모테이블의 결과를 출력합니다.서로소 찾기 로직을 구현해서 그래프에 적용하면 각 노드에 대해 트리 구조를 활용해 루트 노드를 파악할 수 있습니다. 루트노드가 다르면 서로소 집합입니다. 각 노드에 대해 루트노드 정보를 담은 부모테이블을 갱신하면 그 결과를 통해 서로 다른 집합을 특정 지을 수 있습니다. 구현 # 서로소 집합 알고리즘 """ 필요함수..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 4. 3.