트리 동적 계획법: 다지 트리 배낭 문제와 최대 경로 합
다지 트리 배낭 문제 (Multi-ary Tree Knapsack Problem)
이전에는 이진 트리를 기반으로 한 문제를 다루었지만, 이제는 난이도를 높여 다지 트리(multi-ary tree) 구조에 적용되는 동적 계획법(DP)을 살펴보겠습니다. 다지 트리는 각 노드가 여러 자식 노드를 가질 수 있는 형태입니다. 이 경우, 단순한 이진 트리 DP 방식으로는 해결하기 어렵습니다. 대신, 배낭 문제(kn ...
7월 28일 08:58에 게시됨
MX-S 모의고사 풀이 노트
T1: 메시지 필터링
문제 개요
총 n개의 채팅방을 순서대로 확인하며, 각 메시지에 bie 부분 문자열이 포함되어 있고 아직 전송한 적 없는 경우에만 전송한다. 전송할 메시지가 없는 채팅방은 특정 문구를 출력한다.
해결 방법
문자열 탐색과 중복 체크가 핵심이다. bie 존재 여부는 단순 순회로 확인하고, 중복 방지를 위해 해싱 기법을 활용한다. 더블 해싱을 적용해 충돌 ...
7월 26일 03:02에 게시됨
이진 트리 완전 정복: 순회, 판별, 고급 알고리즘
이 문서에서는 이진 트리의 핵심 개념과 다양한 문제 해결 기법을 심층적으로 다룹니다. 노드 구조 정의부터 재귀/비재귀 순회, 그리고 여러 트리 유형 판별 알고리즘과 고급 주제까지 단계별로 살펴봅니다.
1. 이진 트리 노드 구조
이진 트리의 기본 단위는 노드(Node)이며, 각 노드는 데이터와 왼쪽, 오른쪽 자식 노드를 가리키는 포인터로 구성됩니다.
...
7월 7일 02:00에 게시됨
9월 6일 알고리즘 대회 풀이
$$100 + 90 + 65 + 0 = 255$$점, 학내 $$rk7$$. 링크
T1
분류: 가볍게 풀 수 있는 문제 (노란색 난이도)
문제의 핵심은 반전 연산의 특성이다. 두 위치가 서로 다르다면, 그 중 하나만 바꾸는 것이 아니라, 인접한 두 위치가 서로 순서가 잘못되어 있을 때에만 동시에 교환하는 것이 최적임을 알 수 있다. 따라서 단순한 그리디 시뮬레이션으로 해결 가능하며, 시간 복잡도 ...
5월 29일 13:16에 게시됨