2022학년도 봄학기 자료구조(문병로 교수님) github 저장소입니다.
어떤 재료로 집을 지을 것인가? 각 재료들은 어떤 장단점이 있으며, 어떻게 활용해야 하는가?
이 과목에서는 컴퓨터에 의한 문제 해결을 위해 필요한 개념이나 대상물의 표현을 위한 자료 구조와 문제해결을 위한 체계적 사고 방법을 학습한다. 배열, 연결 리스트, 큐, 스택, 우선순위 큐 등의 기본적인 자료구조를 배우고, 검색 트리, 해시 테이블, 균형 잡힌 검색 트리 등 자료의 색인을 위한 자료구조와 그들의 효율성을 배운다. 정렬, 그래프 알고리즘 등 문제 해결에 유용한 도구와 생각하는 방법에 관한 내용도 제공한다. 프로그래밍 과제가 부여되며 이를 위한 최소한의 가이드가 제공된다.
“JAVA의 기초 문법을 학습한 뒤, 배열을 활용하여 큰 수의 연산을 수행하는 프로그램을 구현한다.”
“선형 자료구조를 구현하는 가장 기초적인 자료구조, 연결 리스트를 자바로 구현하고 이를 이용하여 간단한 영화 DB를 구현한다.”
“연결 리스트를 활용하여 큐, 스택을 구현하는 방법을 배우고 스택을 활용한 계산기를 만든다.”
“기초적인 수준의 정렬 알고리즘, 빠른 성능을 가진 정렬 알고리즘, 특수한 상황에서 공간복잡도를 희생하여 더 나은 성능을 보여주는 정렬 알고리즘을 학습하고 이들의 성능을 직접 테스트한다.”
”키를 이용하여 자료를 빠른 시간안에 탐색할 수 있는 자료구조인 BST, AVL Tree, RB-Tree와 Hash Table을 배우고 문자열을 파싱 및 자료구조에 저장, 탐색하는 프로그램을 구현한다.”
”비선형적인 데이터를 저장하는 Graph를 표현하는 방법을 배우고, 그래프를 완전탐색하는 알고리즘, 그래프를 위상정렬하는 알고리즘, 최단 경로를 탐색하는 알고리즘 등을 학습한다. 주어진 지하철 노선도에서 두 역 사이의 최단 소요시간을 계산하는 프로그램을 제작한다.”
이론수업 정리
- 연결 리스트, 스택, 큐에서 맨 앞, 맨 뒤 삽입의 경우 예외 처리가 필요하나, 더미헤드를 이용하면 하나의 로직으로 처리할 수 있다.
- PQ - Heap : 힙은 완전이진트리이면서, 모든 노드에 대해 자식<본인이다. 배열은 그 자체로 완전이진트리이다. PerlocateUp, PerlocateDown을 구현하면 삽입과 삭제는 간단하다.
- 삽입: 맨 뒤에 붙인 후 제 위치까지 Up
- 삭제: root를 지운 뒤 맨 뒤 요소를 root로 옮기고 제 위치까지 Down
- Build: 부모에 해당하는 모든 위치에서 제 위치까지 Down 수행
- 정렬: 퀵 소트, 카운팅 소트 정리
- 퀵 소트: partition 후 나뉜 두 부분을 재귀적으로 partition, partition은 구역을 총 3개로 나눈다. pivot 보다 작은 구역, 큰 구역, 미정구역 → 각각의 경계를 i,j로 두고 조건에 따라 i와 j를 하나씩 키워나간다. i로 피벗 위치를 확정짓는다.
- 카운팅 소트: 범위가 주어진 가산집합의 원소들일 때, 최솟값에서 최댓값까지의 범위에서 각각의 갯수를 센다. 가중합을 구하면 각 원소의 위치가 나온다.
- AVL트리: 노드에 Height 속성을 부여하여 균형이 깨지는지를 확인하고, 깨졌다면 해당 위치에서부터 수선을 시작하여 루트까지 기준으로 잡아 수선한다. 자식 노드에서 부모를 포인팅하지 않으므로, 삽입, 삭제 등의 함수의 리턴 값을 노드로 잡아준다. 부모의 left, right를 해당 함수의 반환값으로 하여 자식 노드에서의 변화를 반영하도록 한다.
- 해시 테이블: 해시 함수를 통해 키값에 대한 함숫값의 인덱스를 구하고, 배열의 해당 인덱스에 value를 저장. 충돌이 일어날 경우 연결 리스트로 이어주거나, probing을 통해 적당한 위치를 찾아준다.
- 외부 저장공간까지 탐색이 이어질 경우: 탐색 깊이를 최대한 낮추는게 유리하다. 이를 위해 B-Tree를 이용한다.
- DFS는 스택을, BFS는 큐를 이용한다. 각각의 탐색 결과로 신장 트리를 만들 수 있다.
- 최소 신장 트리를 구하고자 한다면, 프림 알고리즘과 크루스칼 알고리즘을 쓸 수 있다.
현재 노드를 반드시 포함해야 신장 트리의 조건을 만족하므로, 현재 노드에 인접한 정점들 중 최소 비용의 정점을 고르는 것이 최적해를 보장한다. 간선이 없는 노드를 무한대로 설정한 뒤, 이어지는 간선들 중 가능한 최소거리의 노드를 고르고 나머지 노드들의 값을 갱신한다. 이를 반복하여 최소신장트리를 구한다.
최소 비용의 간선부터 골라가면서 집합을 합쳐나가면 최적해를 보장한다.
- 위상정렬: 사이클이 없는 유향 그래프에서 정점을 선형으로 나열하는데, 이때 정점들 간의 앞서는 순서가 보장되도록 정렬하는 것. 진입 간선이 없는 정점에서 시작해서 다음 간선을 고를 때 해당 간선을 지워나가면 된다.
- 최단 경로 알고리즘: 한 정점에서 나머지 정점까지의 최단거리 및 경로를 구한다. 다익스트라 알고리즘과 벨만-포드 알고리즘이 있다.
- 다익스트라 알고리즘: 양의 가중치에 대해서만 생각할 수 있다.
양의 가중치만이 존재한다면, 지금 내가 고를 최선의 정점이 전체적인 최선이다. 다른 정점을 거쳐서 나오는 루트는 지금 내가 고를 거리보다 큰 거리에(’최선’이니까), 추가적인 양수를 더해서 돌아오게 되므로.
(v.cost ← u.cost + w_u,v 아래에 v.prev ← u 를 넣으면 경로까지 구할 수 있다.)
- 음의 가중치가 포함되면 벨만-포드 알고리즘을 써야 한다.
HW 돌아보기
출력할 데이터가 많은 경우, 출력 자체에 시간이 오래 걸리는 경우가 있다. 이때는 StringBuilder를 이용하여 출력할 데이터를 하나의 문자열로 합친 뒤 한번에 출력하는 것이 좋다.
- HW1
컴퓨터프로그래밍과 달리, 주어진 input이 더러웠던 점이 가장 어렵게 다가왔다. 정규식을 지원하는 Pattern-Matcher를 이용하여 문제를 해결하라는 힌트가 주어졌으나, 기호와 숫자를 분리하여 문자열 내부를 탐색하는 방식으로 문제를 해결하였다. 일일이 케이스를 나눠서 짠 탓에 코드가 지저분해졌다. 다시 짠다면 주어진 input을 통채로 정규식으로 옮기고, []를 matcher.find(index)로 접근할 수 있다는 사실을 이용할 것 같음.
- HW2:
input이 더러운 점을 스켈레톤 코드에서 처리해주는 과제였으나, 오히려 이런 구조를 처음 접하는 입장에서 스켈레톤 코드가 전혀 이해가 안 되었다. 컴퓨터 프로그래밍을 선이수한 뒤 과제에 임했다면 크게 어려운 부분은 없었을 것 같다.
연결 리스트와 Iterator를 구현하고, 정렬을 위해 DB에 저장할 Item을 Comparable 인터페이스에 맞게 정의한 뒤, 이를 활용하여 DB 클래스를 구현하였다. 같은 장르의 영화를 관리할 Genre라는 클래스를 만들어 이들을 DB 내부에 연결 리스트로 저장하고, 각 Genre 객체에 MovieItem 객체를 저장하였다. 구현된 CompareTo함수를 이용해 올바른 위치에 새 영화를 삽입한 뒤에는 이중 리스트를 순회하는 것이 다였다.
- HW3:
스택을 비우는 조건을 연산자 우선순위/괄호에 맞게 판단해주면 된다. ^ 연산자의 우선순위가 내 생각과 달라서 생긴 문제 때문에 고생을 했다.
- HW4:
강의 내용을 따라 버블 정렬, 삽입 정렬, 병합 정렬, 힙 정렬, 퀵 정렬, 기수 정렬을 구현하고 이들의 시간을 계산한다. 충분한 횟수의 반복 후 평균, 표준편차 등의 데이터를 계산함에 있어서 파일IO를 이용하였음.
- HW5:
AVL트리를 직접 구현하고, 자바의 HashMap을 이용하여 HashMap에 AVL트리를 대응시키고, AVL트리의 노드에서 중복되는 요소를 linking하여 데이터를 저장하였음. 데이터로는 부분 문자열에 추가적인 정보를 포함한 노드를 정의하여 사용했다. 트리를 순회하는 알고리즘은 크게 어렵지 않으나, 부분 문자열을 찾는 것이 꽤 까다로웠다. 6개 단위로 input을 잘라서 탐색한 결과를 잘 이어붙여가며 리스트에 저장하였다.
- HW6:
Station을 정점으로 하는 그래프를 HashMap - List로 구현했다. 환승을 하나의 간선으로 보고 구현하였으며, 이름이 같은 역들에 대해 모두 탐색을 수행하여 최적해를 출력하였다. Route, Station, Edge를 클래스로 만들어서 활용하였음.
테스트 케이스의 정답이 최소환승을 기준으로 하여, 편의상 최단시간 내에서 최소환승까지 고려한 탐색 알고리즘으로 수정하였다. 이를 위해 Edge에서 환승인지를 판단하는 멤버변수를 만들고, Station에 도달하기까지의 환승횟수를 넣어 relax 후 탐색 과정에서 비용이 같을 때 환승횟수를 고려하도록 하였다.