프로그래머스5 [PS를 위한 자료구조 6강] 세그먼트 트리의 응용 (Orderstatic Tree) PS를 위한 자료구조 1-6강 # 다양한 세그먼트 트리 테크닉 (Orderstatic Tree) # 에 대해 알아보겠습니다. Orderstatic tree는 한국말로 딱히 번역이 되어있는 것은 없는 것으로 알고 있습니다. 아래의 문제를 볼까요? [가운데를 말해요] https://www.acmicpc.net/problem/1655 이 문제를 어떻게 해결할 수 있을까요? 다음과 같은 자료구조를 생각해봅시다. (1) 정렬 순서을 유지한채로 삽입하는 것이 O(n)보다 작은 시간복잡도로 가능 (2) 정렬된 자료구조의 특정 인덱스 접근울 O(n)보다 작은 시간복잡도로 가능 언뜻보면 별거 아닐 것 같지만, 절대 평범한 리스트로는 수행할 수 없습니다. 이분탐색으로 삽입할 위치를 O(logN)에.. 2022. 3. 24. [PS를 위한 자료구조 5강] 세그먼트 트리의 구현(비재귀) PS를 위한 자료구조 1-5강 # 비재귀 세그먼트 트리의 구현 # 에 대해 알아보겠습니다. 지금까지 세그먼트 트리를 모두 재귀 방식으로 구현해왔습니다. 하지만 재귀 호출를 사용하지 않고 세그먼트 트리를 구현할 수 있다니, 믿겨지십니까? 재귀 세그먼트 트리는 비교적 직관적이고 이해가 쉽지만, 비재귀 세그먼트 트리는 이해하기 어렵고 비트연산을 많이 사용해아합니다. 그럼에도 불구하고 왜 비재귀 세그먼트 트리를 사용할까요? 1. 구현이 짧습니다. 2. 동일한 알고리즘 수행의 경우, 함수호출의 횟수가 적은 비재귀가 더 빠릅니다. 3. 그것이 낭만이니까. 웬만해서는 어렵다는 말은 잘 하지 않지만 이번만큼은 조금 어려울 수 있습니다. 그럼 설명을 시작해보겠습니다. 재귀 세그먼트 트리에서는 항상 루트.. 2022. 3. 24. [PS를 위한 자료구조 3강] 세그먼트 트리의 구현(재귀) 2 PS를 위한 자료구조 1-3강 # 세그먼트 트리의 구현(재귀) 최적화 # 에 대해 알아보겠습니다. 지난 시간까지 세그먼트 트리에 대한 대략적인 이해를 모두 마쳤을 것이라 생각합니다. 이제 세그먼트 트리를 최적화해봅시다. 앞에서 알아본 노드의 설계도를 가져오겠습니다. Class 노드: int 구간의 합 int 왼쪽, 오른쪽 # 구간의 왼쪽, 오른쪽 경계 노드 LEFT, RIGHT # 노드는 자료형입니다. 노드의 설계도에서 무려 앞으로 필요없는 값이 있습니다. 바로 구간의 왼쪽, 오른쪽 경계입니다..!! 이게 왜 필요없는지 분명 의아하실 겁니다. 그 이유에 대해 설명하겠습니다. 1. 원소는 업데이트만 될 뿐 추가나 삭제되지 않는다. -> 원소가 추가되는 경우는 세그먼트 트리 자료구조를 이용할 .. 2022. 3. 24. [PS를 위한 자료구조 2강] 세그먼트 트리의 구현(재귀) PS를 위한 자료구조 1-2강 # 세그먼트 트리의 구현(재귀) # 에 대해 알아보겠습니다. 우선 세그먼트 트리의 구조에 대해 좀 더 이해해봅시다. 앞선 강의의 그림을 그대로 가져오겠습니다. 위 그림에서 볼 수 있는 특징을 정리하겠습니다. 1. 계층이 존재한다. 2. 한 층 내려갈 때마다 구간이 절반으로 쪼개진다. 3. 이 방식을 계층의 구간이 단 하나의 원소가 될 때 까지 반복된다. 이 특징을 정리해보면 아이디어가 하나 떠오를 겁니다. 바로 '재귀'입니다. 2번 특징은 현재 내가 쪼개고 있는 구간이 무엇인지 상관이 없죠. 그저 쪼개기만 하면 됩니다. 이것을 재귀로 간단하게 나타내면 다음과 같이 쓸 수 있습니다. def 함수(시작 : int, 끝 : int) -> None: if 시작 =.. 2022. 3. 24. 이전 1 2 다음
