자료구조/알고리즘

질문 Big-O, Big-Theta, Big-Omega 에 대해 설명해 주세요.

답변 포인트 Big-O는 상한, Big-Omega는 하한, Big-Theta는 상한과 하한이 같은 tight bound를 의미합니다.

질문 다른 것을 사용하지 않고, Big-O를 사용하는 이유가 있을까요?

답변 포인트 Big-O는 입력이 커질 때 증가율의 점근적 상한을 간결하게 표현하므로 구현과 하드웨어가 달라도 확장성을 비교하기 좋습니다.

Big-O 자체가 최악의 경우를 뜻하는 것은 아닙니다. 최선·평균·최악 각각을 Big-O로 표현할 수 있으며, 실무와 면접에서는 성능 보장을 설명하기 위해 최악 경우의 상한을 자주 함께 제시합니다.

질문 O(1)은 O(N^2) 보다 무조건적으로 빠른가요?

답변 포인트 아닙니다.

Big-O는 입력이 충분히 커졌을 때의 증가율이고, 작은 입력에서는 상수항과 구현 차이 때문에 O(N^2)이 더 빠를 수도 있습니다.

질문 일반 배열과, 링크드 리스트를 비교해 주세요.

답변 포인트 배열은 메모리 연속성과 인덱스 접근이 장점이고, 링크드 리스트는 크기 변경과 노드 단위 삽입/삭제가 장점입니다.

배열은 캐시 친화적이고, 링크드 리스트는 포인터 오버헤드가 있습니다.

질문 링크드 리스트를 사용해서 구현할 수 있는 다른 자료구조에 대해 설명해 주세요.

답변 포인트 스택, 큐, 덱, 해시 테이블의 체이닝, LRU 캐시의 순서 관리 등에 활용할 수 있습니다.

질문 스택 2개로 큐를, 큐 2개로 스택을 만드는 방법과, 그 시간복잡도에 대해 설명해 주세요.

답변 포인트 스택 2개 큐는 input stack과 output stack을 두고 dequeue 시 output이 비었을 때만 옮기면 amortized O(1)입니다.

큐 2개 스택은 push 때 기존 원소를 옮기거나 pop 때 옮기는 방식으로 구현하며 한쪽 연산이 O(N)이 됩니다.

질문 시간복잡도를 유지하면서, 배열로 스택과 큐를 구현할 수 있을까요?

답변 포인트 스택은 top 인덱스로 O(1) 구현이 쉽고, 큐는 원형 큐로 front/rear를 순환시키면 enqueue/dequeue를 O(1)로 유지할 수 있습니다.

질문 Prefix, Infix, Postfix 에 대해 설명하고, 이를 스택을 활용해서 계산/하는 방법에 대해 설명해 주세요.

답변 포인트 infix는 일반 수식, prefix는 연산자가 앞, postfix는 연산자가 뒤에 옵니다.

postfix 계산은 피연산자를 스택에 넣고 연산자를 만나면 두 값을 꺼내 계산합니다.

infix를 postfix로 바꿀 때도 연산자 우선순위를 스택으로 처리합니다.

질문 Deque는 어떻게 구현할 수 있을까요?

답변 포인트 양방향 링크드 리스트나 원형 배열로 구현할 수 있습니다.

양끝 삽입/삭제가 O(1)이어야 합니다.

질문 (C++ 한정) Deque의 Random Access 시간복잡도는 O(1) 입니다. 이게 어떻게 가능한걸까요?

답변 포인트 C++ deque는 하나의 연속 배열이 아니라 고정 크기 블록들을 관리하는 map 구조를 사용합니다.

인덱스를 블록 번호와 블록 내부 offset으로 계산해 O(1) 접근이 가능합니다.

질문 값이 주어졌을 때, 어떻게 하면 충돌이 최대한 적은 해시 함수를 설계할 수 있을까요?

답변 포인트 입력 값을 균등하게 분포시키고, 특정 패턴에 몰리지 않게 해야 합니다.

문자열은 다항식 해시처럼 문자의 순서와 값을 모두 반영하고, 보안이 중요한 경우 암호학적 해시나 랜덤 시드를 고려합니다.

질문 해시값이 충돌했을 때, 어떤 방식으로 처리할 수 있을까요?

답변 포인트 대표적으로 체이닝과 오픈 어드레싱이 있습니다.

체이닝은 버킷에 리스트나 트리를 두고, 오픈 어드레싱은 다른 빈 슬롯을 탐사합니다.

질문 본인이 사용하는 언어에서는, 어떤 방식으로 해시 충돌을 처리하나요?

답변 포인트 Java HashMap은 체이닝을 사용하며, 충돌이 많고 조건을 만족하면 버킷 내부 구조를 연결 리스트에서 레드블랙트리로 바꿉니다.

질문 Double Hashing 의 장점과 단점에 대해서 설명하고, 단점을 어떻게 해결할 수 있을지 설명해 주세요.

답변 포인트 이중 해싱은 두 번째 해시 함수로 탐사 간격을 정해 clustering을 줄입니다.

단점은 두 번째 해시 함수 설계가 중요하고 계산 비용이 늘 수 있다는 점입니다.

테이블 크기와 탐사 간격이 서로소가 되게 설계해야 합니다.

질문 Load Factor에 대해 설명해 주세요. 본인이 사용하는 언어에서의 해시 자료구조는 Load Factor에 관련한 정책이 어떻게 구성되어 있나요?

답변 포인트 load factor는 저장된 원소 수를 버킷 수로 나눈 값입니다.

Java HashMap은 기본 load factor가 0.75이고, 임계치를 넘으면 resize와 rehashing을 수행합니다.

질문 다른 자료구조와 비교하여, 해시 테이블은 멀티스레드 환경에서 심각한 수준의 Race Condition 문제에 빠질 위험이 있습니다. 성능 감소를 최소화 한 채로 해당 문제를 해결할 수 있는 방법을 설계해 보세요.

답변 포인트 전체 락보다 버킷 단위 락, segment lock, striped lock, CAS 기반 구조, ConcurrentHashMap 같은 동시성 자료구조를 고려합니다.

읽기/쓰기 비율에 따라 read-write lock도 선택할 수 있습니다.

질문 그래프와 트리의 차이가 무엇인가요?

답변 포인트 트리는 그래프의 특수한 형태입니다.

일반적으로 연결되어 있고 사이클이 없으며, N개의 정점에 N-1개의 간선을 가집니다.

질문 이진탐색트리에서 중위 탐색을 하게 되면, 그 결과는 어떤 의미를 가지나요?

답변 포인트 BST의 중위 순회 결과는 오름차순 정렬된 값입니다.

질문 이진탐색트리의 주요 연산에 대한 시간복잡도를 설명하고, 왜 그런 시간복잡도가 도출되는지 설명해 주세요.

답변 포인트 탐색, 삽입, 삭제는 트리 높이에 비례합니다.

균형이면 높이가 log N이고, 편향되면 N입니다.

질문 이진탐색트리의 한계점에 대해 설명해주세요.

답변 포인트 입력 순서에 따라 편향될 수 있고, 이 경우 성능이 O(N)으로 악화됩니다.

이를 보완하기 위해 AVL, Red-Black Tree 같은 균형 트리를 사용합니다.

질문 이진탐색트리의 값 삽입, 삭제 방법에 대해 설명하고, 어떤식으로 값을 삽입하면 편향이 발생할까요?

답변 포인트 삽입은 탐색 경로를 따라 적절한 leaf 위치에 넣습니다.

삭제는 자식 수에 따라 leaf 삭제, 자식 하나 연결, successor/predecessor 대체로 처리합니다.

정렬된 값이 순서대로 들어오면 편향됩니다.

질문 이진탐색트리와 동일한 로직을 사용하면, 삼진탐색트리도 정의할 수 있을까요? 안 된다면, 그 이유에 대해 설명해 주세요.

답변 포인트 단순히 자식이 세 개라고 BST가 되는 것은 아닙니다.

세 구간으로 값을 나누려면 노드가 두 개의 기준 값을 가져야 하며, 이는 B-tree류 구조에 가깝습니다.

질문 힙을 배열로 구현한다고 가정하면, 어떻게 값을 저장할 수 있을까요?

답변 포인트 0-based 배열이면 부모는 (i-1)/2, 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2로 계산합니다.

완전 이진트리라 배열에 빈 공간 없이 저장할 수 있습니다.

질문 힙의 삽입, 삭제 방식에 대해 설명하고, 왜 이진탐색트리와 달리 편향이 발생하지 않는지 설명해 주세요.

답변 포인트 삽입은 마지막 위치에 넣고 위로 올리는 sift-up, 삭제는 루트와 마지막 원소를 바꾼 뒤 아래로 내리는 sift-down을 합니다.

완전 이진트리 형태를 강제하므로 구조적 편향이 생기지 않습니다.

질문 힙 정렬의 시간복잡도는 어떻게 되나요? Stable 한가요?

답변 포인트 힙 구성은 O(N), 이후 N번 삭제가 각 O(log N)이라 전체 O(N log N)입니다.

일반적인 힙 정렬은 stable하지 않습니다.

질문 Red Black Tree는 어떻게 균형을 유지할 수 있을까요?

답변 포인트 노드 색상과 규칙을 이용해 어떤 경로도 지나치게 길어지지 않도록 합니다.

삽입/삭제 후 recoloring과 rotation으로 규칙을 복구합니다.

질문 Red Black Tree의 주요 성질 4가지에 대해 설명해 주세요.

답변 포인트 노드는 red 또는 black입니다.

루트는 black입니다.

red 노드의 자식은 black입니다.

어떤 노드에서 leaf까지 가는 모든 경로의 black 노드 수가 같습니다.

구현에 따라 NIL leaf는 black으로 봅니다.

질문 2-3-4 Tree, AVL Tree 등의 다른 BBST 가 있음에도, 왜 Red Black Tree가 많이 사용될까요?

답변 포인트 AVL보다 균형 조건이 느슨해 삽입/삭제 시 회전이 상대적으로 적고, 조회 성능도 충분히 O(log N)을 보장하기 때문입니다.

질문 Quick Sort와 Merge Sort를 비교해 주세요.

답변 포인트 Quick Sort는 평균 O(N log N), in-place 구현이 가능하고 캐시 효율이 좋지만 최악 O(N^2)입니다.

Merge Sort는 항상 O(N log N)이고 stable하게 구현하기 쉽지만 추가 메모리가 필요합니다.

질문 Quick Sort에서 O(N^2)이 걸리는 예시를 들고, 이를 개선할 수 있는 방법에 대해 설명해 주세요.

답변 포인트 이미 정렬된 배열에서 피벗을 맨 앞/뒤로 고르면 편향 분할이 발생합니다.

랜덤 피벗, median-of-three, introsort로 개선할 수 있습니다.

질문 Stable Sort가 무엇이고, 어떤 정렬 알고리즘이 Stable 한지 설명해 주세요.

답변 포인트 같은 키를 가진 원소의 상대 순서가 유지되는 정렬입니다.

Merge Sort, Insertion Sort, Bubble Sort는 stable하게 구현 가능하고, Quick Sort, Heap Sort는 일반적으로 stable하지 않습니다.

질문 Merge Sort를 재귀를 사용하지 않고 구현할 수 있을까요?

답변 포인트 가능합니다.

bottom-up merge sort는 길이 1짜리 구간부터 시작해 반복문으로 구간 크기를 두 배씩 늘리며 병합합니다.

질문 Radix Sort에 대해 설명해 주세요.

답변 포인트 비교 기반 정렬이 아니라 자릿수별로 정렬하는 알고리즘입니다.

각 자리 정렬에 stable sort를 사용하며, 정수나 고정 길이 문자열 등에 적합합니다.

질문 Bubble, Selection, Insertion Sort의 속도를 비교해 주세요.

답변 포인트 평균/최악은 모두 대체로 O(N^2)입니다.

Selection은 교환 횟수가 적고, Insertion은 거의 정렬된 데이터에서 빠르며, Bubble은 실무 활용도가 낮습니다.

질문 값이 거의 정렬되어 있거나, 아예 정렬되어 있다면, 위 세 알고리즘의 성능 비교 결과는 달라질까요?

답변 포인트 Insertion Sort는 거의 정렬된 경우 O(N)에 가까워질 수 있습니다.

Bubble도 swap 여부 최적화가 있으면 좋아질 수 있지만, Selection Sort는 비교 횟수가 거의 줄지 않습니다.

질문 본인이 사용하고 있는 언어에선, 어떤 정렬 알고리즘을 사용하여 정렬 함수를 제공하고 있을까요?

답변 포인트 Java는 객체 배열 정렬에 TimSort, primitive 배열에는 Dual-Pivot QuickSort를 사용합니다.

컬렉션 정렬은 stable한 TimSort 기반입니다.

질문 정렬해야 하는 데이터는 50G 인데, 메모리가 4G라면, 어떤 방식으로 정렬을 진행할 수 있을까요?

답변 포인트 external sort를 사용합니다.

메모리에 들어갈 만큼 chunk를 나눠 정렬해 파일로 저장하고, 이후 k-way merge로 병합합니다.

질문 각 방법에 대해, "두 정점이 연결되었는지" 확인하는 시간복잡도와 "한 정점에 연결된 모든 정점을 찾는" 시간복잡도, 그리고 공간복잡도를 비교해 주세요.

답변 포인트 인접 행렬은 연결 확인 O(1), 이웃 탐색 O(V), 공간 O(V^2)입니다.

인접 리스트는 연결 확인이 보통 차수만큼, 이웃 탐색 O(degree), 공간 O(V+E)입니다.

질문 정점의 개수가 N개, 간선의 개수가 N^3 개라면, 어떤 방식으로 구현하는 것이 효율적일까요?

답변 포인트 단순 그래프라면 간선 수는 최대 N(N-1) 또는 무방향 기준 N(N-1)/2라 N^3 간선은 불가능합니다.

멀티그래프라면 중복 간선을 어떻게 다룰지에 따라 표현 방식을 다시 정해야 합니다.

질문 사이클이 없는 그래프는 모두 트리인가요? 그렇지 않다면, 예시를 들어주세요.

답변 포인트 아닙니다.

사이클이 없어도 연결되어 있지 않으면 forest입니다.

트리는 연결 그래프이면서 사이클이 없어야 합니다.

질문 트리에서는 어떤 방식으로 최단거리를 구할 수 있을까요? (위 방법을 사용하지 않고)

답변 포인트 트리는 두 정점 사이 경로가 유일하므로 DFS나 LCA를 이용해 거리 합을 구할 수 있습니다.

가중치가 없는 트리에서 두 정점 u, v의 거리는 depth(u) + depth(v) - 2 * depth(LCA(u, v))입니다. 단순 깊이 차이는 한 정점이 다른 정점의 조상일 때만 맞습니다.

질문 다익스트라 알고리즘에서, 힙을 사용하지 않고 구현한다면 시간복잡도가 어떻게 변화할까요?

답변 포인트 인접 행렬과 선형 탐색으로 다음 정점을 고르면 O(V^2)입니다.

힙과 인접 리스트를 쓰면 보통 O((V+E) log V)입니다.

질문 정점의 개수가 N개, 간선의 개수가 N^3 개라면, 어떤 알고리즘이 효율적일까요?

답변 포인트 단순 그래프에서는 N^3 간선이 불가능합니다.

밀집 그래프에 가깝다면 O(V^2) 다익스트라나 Floyd-Warshall 선택을 비교할 수 있고, 모든 쌍이 필요한지 단일 시작점인지가 중요합니다.

질문 A* 알고리즘에 대해 설명해 주세요. 이 알고리즘은 다익스트라와 비교해서 어떤 성능을 낼까요?

답변 포인트 A*는 실제 비용 g(n)과 휴리스틱 추정 비용 h(n)을 함께 사용해 목표 방향으로 탐색합니다.

좋은 admissible heuristic이 있으면 다익스트라보다 적은 노드를 탐색할 수 있습니다.

질문 음수 간선이 있을 때와, 음수 사이클이 있을 때 각각 어떤 최단거리 알고리즘을 사용해야 하는지 설명해 주세요.

답변 포인트 음수 간선은 Bellman-Ford로 처리할 수 있고, 음수 사이클도 감지할 수 있습니다.

음수 사이클이 경로에 포함되면 비용을 무한히 낮출 수 있어 최단거리가 정의되지 않습니다.

질문 재귀 함수의 동작 과정을 Call Stack을 활용해서 설명해 주세요.

답변 포인트 함수가 호출될 때마다 지역 변수, 매개변수, 복귀 주소 등이 stack frame으로 쌓이고, 종료 조건에 도달하면 가장 마지막 호출부터 반환되며 stack frame이 제거됩니다.

질문 언어의 스펙에 따라, 재귀함수의 최적화를 진행해주는 경우가 있습니다. 어떤 경우에 재귀함수의 최적화가 가능하며, 이를 어떻게 최적화 할 수 있을지 설명해 주세요.

답변 포인트 꼬리 재귀처럼 재귀 호출 결과를 그대로 반환하는 경우 현재 stack frame을 재사용할 수 있습니다.

다만 Java는 일반적인 tail call optimization을 보장하지 않습니다.

질문 Kruskal 알고리즘에서 사용하는 Union-Find 자료구조에 대해 설명해 주세요.

답변 포인트 서로소 집합을 관리하는 자료구조입니다.

find로 대표 노드를 찾고, union으로 두 집합을 합칩니다.

path compression과 union by rank/size로 거의 상수 시간에 가깝게 동작합니다.

질문 Kruskal 과 Prim 중, 어떤 것이 더 빠를까요?

답변 포인트 그래프 특성에 따라 다릅니다.

Kruskal은 간선 정렬 때문에 보통 O(E log E)이고 희소 그래프에 적합합니다.

Prim은 힙과 인접 리스트 사용 시 O(E log V)이고 밀집 그래프에서는 인접 행렬 기반 O(V^2)도 고려합니다.

질문 Kruskal 과 Prim 알고리즘을 통해 얻어진 결과물은 무조건 트리인가요? 만약 그렇다면 증명해 주세요. 그렇지 않다면, 반례를 설명해 주세요.

답변 포인트 그래프가 연결되어 있다면 결과는 트리입니다.

모든 정점을 연결하고 사이클을 만들지 않으며 간선 수가 V-1개이기 때문입니다.

그래프가 연결되어 있지 않으면 MST가 아니라 최소 신장 forest가 됩니다.

질문 배열의 길이를 알고 있다면, 조금 더 빠른 Thread Safe 한 연산을 만들 순 없을까요?

답변 포인트 고정 크기 배열이라면 인덱스별 락, striped lock, atomic array, CAS 기반 업데이트를 사용할 수 있습니다.

전체 락보다 충돌 범위를 줄이면 성능을 높일 수 있습니다.

질문 사용하고 있는 언어의 자료구조는 Thread Safe 한가요? 그렇지 않다면, Thread Safe 한 Wrapped Data Structure 를 제공하고 있나요?

답변 포인트 Java의 기본 ArrayList, HashMap은 thread safe하지 않습니다.

Collections.synchronizedList, ConcurrentHashMap, CopyOnWriteArrayList, Vector 등 대안이 있지만 사용 목적에 맞게 골라야 합니다.

질문 Trie는 어떤 경우에 유리한가요?

답변 포인트 자동완성, 사전 검색, 접두사 기반 검색처럼 prefix 질의가 많을 때 유리합니다.

대신 노드와 포인터가 많아 메모리 사용량이 큽니다.

질문 KMP는 왜 빠른가요?

답변 포인트 실패 함수로 이미 비교한 정보를 재사용해 패턴을 불필요하게 되돌리지 않습니다.

그래서 전체 검색이 O(N+M)입니다.

질문 Rabin-Karp는 어떤 장단점이 있나요?

답변 포인트 rolling hash로 구간 해시를 빠르게 갱신해 여러 패턴 검색에 유리할 수 있습니다.

단 해시 충돌 가능성이 있어 최종 확인이 필요합니다.

질문 Lower Bound, Upper Bound 는 무엇이고, 이를 어떻게 구현할 수 있을까요?

답변 포인트 lower bound는 특정 값 이상이 처음 나오는 위치, upper bound는 특정 값보다 큰 값이 처음 나오는 위치입니다.

이진탐색에서 조건을 만족하는 최소 인덱스를 찾는 방식으로 구현합니다.

질문 이진탐색의 논리를 적용하여 삼진탐색을 작성한다고 가정한다면, 시간복잡도는 어떻게 변화할까요? (실제 존재하는 삼진탐색 알고리즘은 무시하세요!)

답변 포인트 탐색 범위를 3등분하면 단계 수는 log3 N이지만 각 단계에서 비교가 더 늘 수 있습니다.

Big-O로는 여전히 O(log N)입니다.

질문 기존 이진탐색 로직에서 부등호의 범위가 바뀐다면, (ex. <= 라면 <로, <이라면 <= 로) 결과가 달라질까요?

답변 포인트 달라질 수 있습니다.

특히 중복 값이 있는 경우 lower bound와 upper bound처럼 경계 조건에 따라 반환 위치가 달라집니다.

질문 그렇다면, 어떤 경우에 각각의 기법을 사용할 수 있을까요?

답변 포인트 그리디는 현재 최선의 선택이 전체 최적해로 이어진다는 greedy choice property가 증명될 때 사용합니다.

DP는 부분 문제들이 반복되고, 부분 문제의 최적해로 전체 최적해를 구성할 수 있을 때 사용합니다.

질문 그렇다면, 동적 계획법으로 풀 수 있는 모든 문제는 재귀로 변환하여 풀 수 있나요?

답변 포인트 많은 DP는 top-down 재귀와 memoization으로 표현할 수 있습니다.

다만 stack depth, 순환 의존성, 상태 전이 순서 때문에 반복문 tabulation이 더 적합한 경우도 있습니다.

질문 그래프의 사이클은 위상 정렬 과정에서 어떻게 알 수 있나요?

답변 포인트 Kahn 알고리즘에서 처리한 정점 수가 전체보다 적으면 사이클이 있습니다. DFS에서는 방문 중인 정점으로 향하는 간선을 발견하면 사이클입니다.

질문 사전순으로 가장 앞선 위상 정렬 결과를 구하려면 어떻게 하나요?

답변 포인트 Kahn 알고리즘에서 진입 차수가 0인 정점 집합을 일반 큐 대신 최소 힙으로 관리합니다. 매 단계에 선택할 수 있는 정점 중 가장 작은 정점을 꺼내면 사전순으로 가장 앞선 결과를 얻습니다.

간선 처리는 O(E), 정점의 힙 삽입과 삭제는 O(V log V)이므로 전체 시간복잡도는 O(E + V log V)로 설명할 수 있습니다.

질문 가능한 모든 위상 정렬 결과를 구할 수 있나요?

답변 포인트 각 단계에서 진입 차수가 0인 모든 정점을 후보로 두고 하나씩 선택한 뒤 상태를 되돌리는 backtracking으로 구할 수 있습니다. 후보가 여러 개인 분기마다 서로 다른 순서가 만들어집니다.

가능한 순서의 수 자체가 지수적으로 커질 수 있으므로 모든 결과를 출력하는 알고리즘도 최악에는 지수 시간이 필요합니다.

질문 위상 정렬 결과만 있으면 의존 작업을 최대한 병렬로 실행할 수 있나요?

답변 포인트 하나의 위상 순서는 실행 가능한 직렬 순서만 보장합니다. 같은 시점에 진입 차수가 0인 작업들은 병렬 실행 후보가 될 수 있지만, 실제 병렬도는 작업 시간, 자원 제한과 추가적인 실행 제약에 따라 달라집니다.

전체 완료 시간을 최소화하려면 단순 위상 순서뿐 아니라 DAG의 critical path와 작업별 비용도 함께 고려해야 합니다.

질문 값 변경과 구간 합 질의가 모두 많다면 누적 합만으로 충분한가요?

답변 포인트 한 값이 바뀌면 뒤쪽 누적 값을 다시 계산해야 하므로 충분하지 않습니다. Fenwick Tree나 Segment Tree로 갱신과 질의를 O(log N)에 처리할 수 있습니다.

질문 2차원 배열에서도 누적 합을 사용할 수 있나요?

답변 포인트 가능합니다. P[r][c]를 왼쪽 위부터 해당 위치까지의 합으로 정의하고, 겹쳐 더한 영역을 빼는 포함-배제로 전처리합니다.

전처리는 O(RC)이고, 네 개의 누적 합 값을 조합하면 임의 직사각형 영역 합을 O(1)에 계산할 수 있습니다.

질문 차분 배열로 구간을 갱신한 직후 특정 인덱스의 값을 바로 조회할 수 있나요?

답변 포인트 차분 배열에 갱신 표시만 해둔 상태라면 해당 위치까지 누적해야 하므로 단순 구현의 조회는 O(N)일 수 있습니다. 모든 갱신이 끝난 뒤 한 번 복원하는 사용 방식에서 장점이 가장 큽니다.

구간 갱신과 점 조회를 온라인으로 처리해야 한다면 차분 값의 누적 합을 Fenwick Tree로 관리해 두 연산을 O(log N)에 수행할 수 있습니다.

질문 배열에 음수가 있어도 누적 합을 사용할 수 있나요?

답변 포인트 구간 합 계산 자체에는 문제가 없습니다. 누적 합의 차 공식은 원소의 부호와 관계없이 성립합니다.

다만 누적 합 배열이 단조 증가한다고 가정해 이진탐색이나 two pointer를 적용하는 로직은 음수가 있으면 깨질 수 있으므로 별개의 조건을 확인해야 합니다.

질문 Lazy Propagation은 왜 필요한가요?

답변 포인트 구간 전체 갱신을 모든 리프에 즉시 적용하면 한 번의 갱신에도 O(N)이 걸릴 수 있습니다. 완전히 포함되는 노드에는 갱신 결과와 lazy 값을 기록하고 자식 방문을 미룹니다.

나중에 해당 자식 구간이 필요할 때 보류한 값을 전파하면 지원되는 구간 갱신과 질의를 보통 O(log N)에 처리할 수 있습니다. 대입과 덧셈처럼 lazy 연산이 여러 종류라면 합성 순서도 정확히 정의해야 합니다.

질문 점 갱신과 구간 합만 필요하다면 어느 구조가 적합한가요?

답변 포인트 Fenwick Tree가 구현과 메모리 측면에서 유리한 경우가 많습니다. 다양한 결합 연산이나 구간 갱신이 필요하면 Segment Tree가 더 유연합니다.

질문 Fenwick Tree로 구간 갱신과 구간 합 질의를 모두 처리할 수 있나요?

답변 포인트 합 연산에서는 차분 관계를 이용해 Fenwick Tree 두 개를 관리하면 구간 덧셈과 prefix 합을 각각 O(log N)에 처리할 수 있습니다. 두 prefix 합의 차로 구간 합도 구할 수 있습니다.

이 기법은 합의 역연산과 수식에 의존하므로 임의의 연산에 그대로 일반화할 수는 없습니다.

질문 Segment Tree의 결합 연산에 결합 법칙이 필요한 이유는 무엇인가요?

답변 포인트 같은 구간을 트리 구조에 따라 여러 방식으로 나누더라도 부분 결과를 합친 최종 값이 같아야 하기 때문입니다. 결합 법칙이 깨지면 노드 경계와 질의 분할 방식에 따라 결과가 달라질 수 있습니다.

연산이 교환 법칙까지 만족할 필요는 없지만, 교환 불가능한 연산이라면 왼쪽과 오른쪽 결과를 합치는 순서를 보존해야 합니다.