(자료구조와 알고리즘을 직접 구현하지 않더라도) 개발자로서 접하고 활용할 수 있는 기술들을 제대로 이해할 수 있었습니다. 예를 들어서 가비지컬렉터가 참조되고 있는 객체를 선별하기 위한 Mark의 그림을 보았을 때, 객체들을 노드로 지정하고 참조 관계를 DFS로 탐색하겠구나 라는 이해를 할 수 있었습니다. 이외에도 알고리즘, 특히 자료구조에 대한 지식이 프레임워크나 API의 내부 구현을 이해하는 데 도움이 된다고 생각합니다.
배열은 연속된 메모리 공간에 할당되고 연결리스트는 그렇지 않습니다. 따라서 다음 노드를 가리키는 레퍼런스 필드를 추가로 가져야 합니다. 랜덤 조회, 삽입, 삭제 시간복잡도도 다릅니다.
배열은 조회는 상수 시간에 할 수 있지만, 삽입과 삭제를 하기 위해 다른 원소들을 밀고 당겨야 하기 때문에 선형 시간이 소모됩니다. 반면, 링크드리스트는 조회하는데 선형 시간이 소모되지만 삽입과 삭제에 상수 시간이 소모됩니다.
데이터의 삽입과 삭제가 빈번히 발생하면 연결리스트, 삽입/삭제보다 조회가 더 많이 발생하면 배열이 더 유리합니다.
다음 노드에 대한 포인터만을 가지고 있는 것이 일반 연결리스트입니다. 마지막 노드가 첫 번째 노드를 가리키고 있다면 순환 연결 리스트, 다음 노드 뿐만이 아닌 이전 노드도 가리키고 있다면 양방향 연결리스트라고 합니다.
내부 구현은 배열로 되어있습니다. capacity에 다다르면 새로운 크기의 배열을 할당해서 기존 요소들을 복사합니다.
여러 데이터를 저장하는 자료구조라는 것은 동일하지만, 스택은 나중에 삽입한 원소일 수록 먼저 꺼내지는 Last-In-First-Out, 큐는 들어온 순서대로 꺼내지는 First-In-First-Out이라는 점이 대표적인 차이점입니다.
JVM의 스택 프레임을 저장하는 데 사용되거나, 브라우저에서 뒤로가기를 할 때 사용됩니다.
CPU 스케줄링을 할 때 큐를 사용합니다.
삽입/삭제를 할 때 마다 front, rear가 가리키는 인덱스가 뒤로 가기 때문에 공간을 제대로 활용하지 못할 수 있습니다. 그래서 배열을 개념적으로 순환되게 하는 circular array를 사용합니다.
사이클이 없으면서 커넥티드한 그래프를 트리라고 합니다. 이 때 모든 정점이 하나 이상의 정점과 연결되어 있음을 의미합니다. 일반적으로 사용하는 트리는 루티드 트리로써, 루트 노드를 가진 계층형 트리 형태를 말합니다.
해당 Node에서 도달할 수 있는 Leaf Node로의 Path 길이 중 최댓값
Depth는 루트에서 해당 노드까지의 Path의 길이입니다. 트리의 Depth는 그 중 가장 큰 값을 말합니다. Level은 Depth에 1을 더한 것이라서 루트 노드의 레벨은 1입니다.
풀 바이너리 트리는 모든 노드가 0개 또는 2개의 자식을 가지고 있는 트리입니다. 퍼펙트 바이너리 트리는 풀 바이너리 트리이면서, 리프노드들의 Depth가 모두 동일한 트리입니다. 컴플리트 바이너리 트리는 맨 마지막 레벨을 제외한 트리의 형태가 퍼펙트 바이너리 트리이면서, 마지막 레벨은 왼쪽에서부터 빈 공간 없이 노드로 채워진 트리입니다.
전위, 중위, 후위 순회가 있습니다. 각각 루트노드를 어떤 순서에 들리느냐에 따라 다릅니다.
그래프에서의 순회 중에 특정 정점에서 시작해서 같은 엣지를 두 번 이상 반복하지 않고 처음으로 돌아올 수 있는 경로가 있다면 사이클이 있다고 표현합니다.
이진탐색을 트리 자료구조를 이용해서 할 수 있도록 가이드 하는 트리입니다. 부모 노드의 왼쪽 자식 노드는 부모 노드의 키 값보다 작고, 오른쪽 자식 노드는 부모 노드의 키 값보다 큽니다. 이진 탐색은 로그 시간에 탐색을 하기 위한 알고리즘인데, 트리의 모양이 편향되어 링크드 리스트 형태가 되기 때문에 탐색시간이 선형시간에 가까워진다는 특징이 있습니다.
AVL트리, 레드블랙 트리와 같이 삽입과 삭제가 빈번하게 발생되어도 밸런싱 작업을 통해 트리의 높이를 스스로 조절할 수 있는 자가 균형 트리들을 사용합니다.
트리의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1 이상 나지 않게 하기 위해 밸런싱 작업을 동작시킵니다. 삽입 또는 삭제한 노드의 조상 노드 중 이 특성을 어기는 서브 트리 구조를 찾습니다. 그리고 싱글 로테이션 또는 더블 로테이션 작업을 통해 트리를 회전시켜서 균형을 유지합니다.
그래프에서 만들 수 있는 부분그래프의 한 종류입니다. MST에 속한 모든 노드들은 연결되어 있어야 하고, 엣지들의 가중치 합은 모든 경우의 수 중 최소가 되어야 합니다.
둘다 그리디 알고리즘에 기반하지만, 크루스칼 알고리즘은 MST 셋에 속한 엣지들을 하나씩 늘려가고, 프림 알고리즘은 정점을 하나씩 늘려가는 방식으로 동작합니다.
현재 선택하지 않은 엣지들 중, MST 셋에 추가해도 사이클이 생기지 않는 엣지 중 가중치가 가장 작은 엣지를 선택하는 알고리즘입니다.
크루스칼 알고리즘은 사이클이 생기는 것을 방지하기 위해 이미 연결되어 있는지 판단하는 방법으로 DFS를 사용합니다. 이것 때문에 O(N^2)의 시간복잡도를 가집니다. 유니온 파인드를 사용하면 시간복잡도를 줄일 수 있습니다.
정점들이 연결되어 있는지 판단하기 위해 유니온파인드를 사용합니다. 새로운 엣지를 추가할 때 유니온 연산을 실행하고, 파인드 연산을 실행했을 때 서로 같은 루트를 가리키고 있다면 이미 연결되어 있는 것이라고 판단합니다.
MST 셋에 인접한 정점들 중에 연결된 엣지의 가중치가 가장 작은 정점을 MST 셋에 추가하는 알고리즘입니다.
인접한 정점을 연결하는 엣지의 가중치가 가장 작은 것을 찾기 위해 선형시간이 소모됩니다. 정점의 개수를 N, 엣지의 개수를 M이라고 했을 때 O(NM)의 시간복잡도가 소모됩니다.
모든 엣지셋을 처음에 우선순위큐에 넣어두고 팝하는 방식을 사용하면 시간복잡도를 줄일 수 있습니다.
엣지 수가 많으면 인접행렬로 표현하는 것이 유리합니다. 인접행렬로 표현할 때에는 정점의 제곱개 만큼의 메모리를 할당하는데, 엣지가 적으면 이것이 메모리 낭비가 되기 때문입니다. 인접리스트는 엣지 수 만큼의 메모리만 차지하지만, 특정 두 정점이 연결되어 있는지 판단하기에는 조금 느립니다.
다익스트라 알고리즘과 같은 경우에서 시간복잡도를 줄이기 위해 사용하고, 운영체제에서도 SJF를 구현하기 위해 사용할 것 같습니다.
특별한 형태의 컴프리트 바이너리 트리입니다. 최대힙과 최소힙으로 나눌 수 있는데, 최대힙은 부모 노드가 자식 노드보다 키 값이 크다는 특징을 가지고 있습니다. 따라서 루트 노드는 트리 상의 모든 노드 중 가장 큰 값을 가집니다.
보통 트리는 링크드리스트 형태로 많이 구현하는데, 힙은 배열로 구현합니다. 컴플리트 바이너리 트리이기 때문에 배열로 구현해도 낭비되는 공간이 없어서 효율적입니다.
컴플리트 바이너리 트리이기 때문에 삽입과 삭제 모두 마지막 노드 자리에 추가하거나 삭제한 뒤 힙 성질을 유지하기 위해 노드들을 스왑하는 과정을 거칩니다. 삽입의 경우에는 마지막 자리에 추가한 뒤 부모 노드와 비교하고 스왑하는 과정을 반복하고, 삭제의 경우에는 마지막 원소를 루트 노드 자리에 넣은 뒤 자식 노드와 비교해서 스왑하는 과정을 반복합니다.
힙에 원소들을 전부 넣은 뒤 다시 원소를 전부 꺼내서 나온 순서대로 원소를 정렬하는 알고리즘입니다. 원소를 정렬하기 위해 힙이라는 추가 공간을 사용하기 때문에 Out-Of-Place 알고리즘 입니다.
힙소트를 In-Place 알고리즘으로 구현하기 위한 방법입니다. 힙도 배열이기 때문에, 모든 원소가 힙 성질을 만족할 수 있도록 스왑을 진행시켜주면 됩니다. 모든 논리프 노드들에 대해 레벨 오더의 역순으로 재귀적으로 내려가면서 히피파이를 진행합니다.
해시 함수를 이용해서 데이터를 키-값 쌍으로 저장하는 자료구조입니다. 이 때, 키가 정수형 데이터가 아니더라도 인덱스로 변환하기 위해 사용하는 변환 함수를 해시 함수하고, 이를 저장하는 배열을 해시테이블이라고 합니다.
소수가 아니라 2의 배수라고 가정해보겠습니다. 해시 테이블의 사이즈가 10이라고 했을 때, 키 값이 0부터 10일 경우 해시 함수의 값은 0 또는 1로만 나오게 됩니다. 해시 함수의 결과 값이 특정 값으로 집중되는 것을 막고, 고른 결과를 얻기 위해 소수를 사용합니다.
서로 다른 키의 해시 함수 값이 동일하게 나타나서, 하나의 해시테이블에 두 개의 값을 저장해야 하는 상황일 때를 의미합니다. 좋은 해시함수는 모든 키 값에 해당하는 해시 함수 값이 1대1 대응되는 함수입니다. 하지만 이런 해시 함수는 존재하지 않기 때문에 최대한 충돌이 발생하지 않는 해시 함수를 구현하는 것이 중요합니다.
해시 함수로 변환한 키값에서 충돌이 발생할 때 사용할 수 있는 방법으로, 리니어 프루빙과 체이닝 기법이 있습니다. 리니어 프루빙은 변환된 키값에서 인덱스를 증가시켜가며 비어있는 테이블 레코드에 값을 삽입하는 것입니다. 체이닝은 해당 테이블 레코드를 연결리스트로 구현해서 변환된 키값에 해당하는 원소들을 연결리스트로 관리합니다.
실제 해시테이블에 값이 삽입될 때에는 특정 인덱스들에 데이터가 집중되는 경향이 있다고 합니다. 그래서 특정 인덱스에 존재하는 어떠한 값을 찾기 위해서는 연결리스트를 탐색해야 한다는 단점이 있습니다.
입력 사이즈에 비례해서 얼마나 시간이 소요되는지 측정하는 알고리즘의 성능 척도입니다.
재귀함수를 이용하면 프로그램의 계산을 조금 더 직관적으로 이해할 수 있습니다. 반복문을 이용하면 함수의 호출/반환 로직이 없기 때문에 대신 더 빠른 동작을 얻을 수 있습니다.
디피는 기본적으로 재귀함수에서 적용될 수 있는 알고리즘입니다. 전체 문제의 답을 찾기 위해 부분 문제들을 이용하는데, 똑같은 부분 문제를 반복해서 계산하는 것을 막기 위해 메모이제이션 기법을 사용합니다.
바꿀 수 있습니다. 탑다운으로 구현된 재귀 함수는 기저 조건과, 기저 조건에 가까워지는 재귀 호출을 이용하는데요, 이 부분을 반복문으로 바꿔주면 바텀업 방식으로도 구현할 수 있습니다.
DP와 분할정복 모두 전체 문제의 답을 찾기 위해 부분 문제들을 이용한다는 것은 동일합니다. 하지만 DP는 부분 문제를 중복해서 구하는 것을 방지하기 위해, 메모이제이션을 사용한다는 것이 핵심입니다. 분할정복은 문제가 중복되지 않게 영역을 나누어 호출하기 때문에, 우연히 값이 동일할 때를 제외하면 부분 문제가 겹치는 일은 없습니다.
순차탐색은 배열을 순서대로 탐색하면서 값을 찾는 것이고, 이진탐색은 정렬된 배열에서 값의 범위를 반씩 줄여가면서 찾는 것입니다.
문제를 해결하는 과정에서 현재 상태에서 선택할 수 있는 최적의 해를 골라가는 알고리즘입니다.
배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어서, 각 단계마다 정렬되지 않은 원소를 인접한 원소와 계속 스왑하면서 정렬된 부분에서의 자기 자리를 찾도록 만드는 알고리즘입니다. 거의 정렬되어 있는 배열에 삽입 정렬을 수행할 경우, swap 시간이 짧기 때문에 빠르게 동작합니다.
단계마다 정렬되지 않은 원소들 중 가장 작은 원소를 찾아내서 한번 위치를 스왑하는 알고리즘입니다. order of N 제곱의 시간복잡도를 가집니다.
인접한 두 엘리먼트 간의 값을 비교하면서 스왑하는 형태의 정렬 알고리즘입니다. 버블 소트는 항상 order of N제곱의 시간복잡도를 가집니다.
분할정복을 이용한 정렬 알고리즘입니다. 분할할 때는 배열을 절반으로 나누고, 합칠 때 두 개의 배열 포인터를 이용해서 새로운 배열에 정렬된 순서대로 합치는 알고리즘입니다. 이 과정에서 추가적인 메모리 공간을 요구하는 Out of place 알고리즘입니다.
분할정복을 이용한 정렬 알고리즘입니다. 분할할 때 피벗 원소를 기준으로 배열을 분할해서 이 과정에서 정렬이 발생하고, 합칠 때에는 순서대로 합치기만 하는 알고리즘입니다. 이때문에 피벗 원소를 잘 선택하는 것이 퀵소트의 성능과 관련이 있습니다.
피벗 원소가 최소/최대로 치우친 값일 경우 배열을 분할했을 때 배열 안의 원소 개수의 차이가 심해집니다. 그래서 피벗 원소를 최대한 배열의 중간 값으로 설정하는 것이 중요한데, 이를 미디언 오브 미디언즈 알고리즘을 통해 구할 수 있습니다.
배열을 5등분해서 각 부분 배열의 중간 값을 구하고, 이 중간값들 중의 중간값을 구해서 그것을 피벗으로 선정하는 알고리즘입니다. 이론상으로는 order of N 시간에 구할 수 있지만, 배열을 등분해서 정렬하는 것이 실험적으로는 매우 큰 시간을 소모하기 때문에 실질적으로는 사용하지 않는다고 들었습니다.
정렬할 때 기준이 되는 키 값이 동일한 두 개의 원소가 있을 때, 정렬 알고리즘을 수행해도 해당 원소들의 순서가 변하지 않으면 스테이블하다고 합니다.
인플레이스 알고리즘은 정렬 과정에서 사용하는 추가적인 메모리가 입력 배열 크기에 상관없이 무시할 만한 수준일 때를 의미합니다. 대표적으로 머지 소트는 정렬 과정에서 해당 배열의 크기만큼 계속해서 메모리를 할당하기 때문에 Out-of-Place Sort 알고리즘입니다.
DFS, BFS가 있습니다. 시작 정점에서 도달할 수 있는 모든 노드들을 탐색하는 알고리즘으로, 방문 순서에 따라 DFS와 BFS로 나뉩니다.
기본적으로 BFS가 사용하는 탐색 방식이 트리에서의 Level Order 순회 방식과 동일하기 때문입니다. 이를 이용하면 도달할 수 있는 거리가 최소인 노드들의 순서대로 방문하게 되는데, 이 과정에서 목적지를 찾으면 그것까지의 거리가 최소라고 할 수 있습니다.
BFS, 다익스트라, 플로이드와샬, 벨만포드에 대해 알고있습니다.
엣지에 가중치가 존재하며, 그것이 0 이상일 때 사용하는 그리디 알고리즘 기반의 최단 거리 알고리즘입니다.
도달하고자 하는 목적지의 최단 경로를 얻을 때 까지 다른 모든 정점으로의 거리를 지속적으로 업데이트합니다. 업데이트 과정은 다음과 같은데요. 현재 방문하지 않은 정점들 중, 시작 정점에서의 최단 경로가 가장 짧은 정점을 우선 방문합니다. 그리고 나머지 모든 정점들에 대해, 저장된 최단 경로 길이가 현재 방문한 정점으로의 최단거리 플러스 엣지의 길이보다 작다면 업데이트합니다.
벨만포드 알고리즘은 가중치가 있는 그래프에서 최단경로를 찾을 수 있는 다이나믹 프로그래밍 기반 알고리즘입니다. 주요한 특징으로는 가중치가 음수인 엣지가 존재해도 동작할 수 있다는 장점이 있습니다.
사이클의 가중치 합이 음수인, 네거티브 사이클이 존재할 때에는 동작하지 않습니다. 그 경우에는 해당 사이클을 돌 때 마다 가중치가 작아지기 때문에 사이클을 무한하게 돌게됩니다.
플로이드 와샬 알고리즘은 모든 정점으로부터 모든 정점까지의 최단거리를 구할 수 있는 알고리즘입니다.
위상 정렬은 사이클이 없는 방향그래프에서 그래프 간의 참조관계를 통해 정점을 정렬할 수 있는 알고리즘입니다.
특정 정점으로 들어오는 방향의 간선 개수를 In-Degree라고 하는데, 인 디그리가 0인 정점을 출력한 뒤, 해당 정점에서 뻗어나가는 간선을 제거하는 과정을 반복합니다.
특정 그래프가 사이클이 있을 경우에는, 사이클을 제외한 모든 정점을 제거하더라도 인디그리가 0인 정점이 나오지 않습니다. 또한 사이클의 경우에는 어떤 정점을 출발로 할 지 확정할 수 없기 때문에 동작하지 않습니다.