지난 시간까지 교과과정에서 배우는 자료구조를 알아보았습니다.

이번 시간에는 기타 유명한 자료구조들과 문제들을 알아보겠습니다.

0) 설명에 앞서

알고리즘의 깊이가 무궁무진하듯,

자료구조 또한 그 개수가 엄청 많습니다.

본 페이지에 작성된 자료구조와 문제들은,

알고리즘 문제를 해결하는데 많이 쓰이는 자료구조, 또는
그 자료구조를 사용하는 유명한 문제입니다.

1) 스택 응용

(1) 히스토그램에서 가장 큰 직사각형

강사가 생각하는
스택을 사용하는 문제 중 가장 유명한 문제입니다.

다른 풀이 방법(세그먼트 트리, 분할 정복) 또한 매우 유익하기에,

만약 이 문제를 풀게 된다면
여러 방법으로 풀어보시기 바랍니다.

(2) 볼록 껍질

다각형을 만드는 과정에서 스택이 사용됩니다.

2) 큐 응용

(1) BFS(너비 우선 탐색)

큐를 이용하는 그래프의 탐색 방법입니다.

지난번에 배운 적이 있습니다.

(2) 덱

스택과 큐를 일반화한 자료구조입니다.

양방향에서 삽입과 삭제가 가능합니다.

3) 트리 응용

(1) 이진 탐색 트리

집합에 수를 넣는 쿼리와,
집합에 수의 존재 여부를 확인하는 쿼리를
빠르게 수행하는 트리입니다.

(2) 힙

집합에 원소를 넣는 쿼리와,
그 집합에서 가장 우선순위가 높은 원소를 꺼내는 쿼리를
빠르게 수행하는 트리입니다.

(3) 세그먼트 트리

수열의 특정 인덱스의 수를 변경하는 쿼리와,
특정 구간에 대한 값을 구하는 쿼리를
빠르게 수행하는 트리입니다.

본 페이지에 있는 자료구조와 알고리즘 중,
공부하는 것을 가장 추천하는 자료구조입니다.

이것만 알아도, 골드~플레티넘 급의 어려운 문제를
여러 개 풀 수 있기 때문입니다.

4) 그래프 응용

(1) 다익스트라

두 정점 간의 최단 경로를 구하는 알고리즘입니다.

(2) 벨만-포드

위의 다익스트라와 용도는 같지만,
간선의 가중치가 음수인 경우에도 사용할 수 있습니다.

(3) 이분 매칭

인접한 정점을 서로 다른 색으로 칠했을 때,
그래프의 모든 정점을 두 가지 색으로 칠할 수 있는 그래프를
이분 그래프 라고 합니다.

이분 매칭은, 이분 그래프에서
각 정점이 최대 1개의 간선만 가지도록 하여
최대한 많은 간선으로 정점을 연결하는 알고리즘입니다.

(4) 네트워크 플로우

그래프에서 최대한 많이 유량을 흘려보낸 결과를 찾는 알고리즘입니다.

이 외에도 셀 수 없이 많은 자료구조와 알고리즘이 있지만,

여기에 모두 적을 수는 없습니다.

그러므로 여러분이 직접, 자료구조 여행을 떠나보시기 바랍니다.

학교 선배가 알려주는! 2024-2 gbsw 부트캠프 자료구조반 강의를
지금까지 수강해주셔서 감사합니다.

앞으로 여러분이 나아갈 PS 생활,
세상에서 가장 유익한 게임을 즐기시기 바랍니다.