일지
-
JUNGOL...178일지 2022. 1. 11. 17:19
Intermediate_Coder/그래프탐색-DFS/키 순서 문제 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 1번 학생의 키 < 5번 학생의 키 3번 학생의 키 < 4번 학생의 키 5번 학생의 키 < 4번 학생의 키 4번 학생의 키 < 2번 학생의 키 4번 학생의 키 < 6번 학생의 키 5번 학생의 키 < 2번 학생의 키 이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 ..
-
알고리즘...101일지 2022. 1. 11. 13:51
트리를 이용한 집합의 처리 연결 리스트를 이용한 집합의 처리보다 효율적인 방식으로 각각의 집합을 트리로 표현하는 방법이다. 기존의 트리와는 달리 자식 노드가 부모 노드를 가리키는 방식으로 표현된다. 이러한 방식을 사용하는 경우 두 집합을 합칠 때 단순하게 합치려는 노드의 루트가 기존 집합의 루트를 가리키도록 하면 된다. 연산의 효율성을 높이는 방법 - 랭크를 이용한 Union 각 노드에 자신의 서브 트리의 높이를 랭크(Rank)라는 이름으로 저장하고 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다. - 경로 압축 FindSet 진행 시 중간에 만나는 모든 노드에 대해 루트를 직접 가리키도록 바꾸어 추후 FindSet을 할 때 경로의 길이를 줄이는 방법이다. 더보기 참고문헌 한빛아카데미.문병..
-
JUNGOL...177일지 2022. 1. 10. 15:53
Intermediate_Coder/그래프탐색-DFS/키 순서 문제 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 1번 학생의 키 < 5번 학생의 키 3번 학생의 키 < 4번 학생의 키 5번 학생의 키 < 4번 학생의 키 4번 학생의 키 < 2번 학생의 키 4번 학생의 키 < 6번 학생의 키 5번 학생의 키 < 2번 학생의 키 이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 ..
-
알고리즘...100일지 2022. 1. 10. 14:45
연결 리스트를 이용한 집합 처리 집합을 표현하기 위해 각 노드는 대표 노드(집합의 최초 노드)를 가리키는 포인터와, 다음 원소를 가리키는 포인터, 값을 나타내는 변수를 가진다. 또, 집합의 연산을 쉽게 하기 위해 각 노드는 tail 노드를 가리키는 포인터를 따로 가지고 있게 된다. 이 집합을 사용하기 위해서는 다음의 함수가 필요하다. MakeSet(x) 원소 x로 이루어진 집합을 만든다. FindSet(x) 원소 x를 가지는 집합을 찾는다. Union(x, y) 원소 x를 가진 집합과 원소 y를 가지는 집합을 하나로 합친다. 수행 시간은 MakeSet과 FindSet은 상수 시간이 걸리지만 Union은 집합의 크기에 따라 상수 시간을 벗어날 수 있다. 이 수행 시간을 최소화하기 위해 큰 집합에 작은 집합..
-
JUNGOL...176일지 2022. 1. 7. 17:57
Intermediate_Coder/그래프탐색-DFS/키 순서 문제 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 1번 학생의 키 < 5번 학생의 키 3번 학생의 키 < 4번 학생의 키 5번 학생의 키 < 4번 학생의 키 4번 학생의 키 < 2번 학생의 키 4번 학생의 키 < 6번 학생의 키 5번 학생의 키 < 2번 학생의 키 이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 ..
-
알고리즘...99일지 2022. 1. 6. 17:54
해시 테이블 충돌 해결 더블 해싱 구현 충돌 해결 방법 중 개방주소 방법의 더블 해싱을 구현한다. 다른 부분은 상위 클래스에서 구현이 되어있으므로 충돌 해결 방법만 추가로 구현한다. int HashTable_OpenAddressing_DoubleHashing::GetProperHashIndex(int idx, int data) { int jumpValue{ HashTable::GetHashIndex(data, HashFunction::Multiplication) }; if (CurrentHashFunction() == HashFunction::Multiplication) { jumpValue = HashTable::GetHashIndex(data, HashFunction::Division); } int ..
-
JUNGOL...175일지 2022. 1. 5. 16:41
Intermediate_Coder/그래프탐색-DFS/미로 탐색 문제 동현이는 방이 N개인 미로의 지도를 갖고 있다. 각 방에는 1번부터 N번까지 번호가 매겨져 있고, N개의 방 사이에는 M개의 문이 있으며, 각 문은 서로 다른 두 방을 연결한다. 동현이는 1번 방에서 출발해서 N개의 방을 모두 탐색해 볼 것이다. 동현이는 모험심이 강하기 때문에 항상 새로운 방을 찾기를 원한다. 동현이는 자신이 위치한 방과 연결된 방 중 한 번도 들르지 않은 방이 있다면 그 중 가장 번호가 작은 방으로 가고, 그렇지 않으면(연결된 방이 모두 전에 들렀던 방이면) 그냥 왔던 곳으로 되돌아가게 된다. 동현이가 N개의 방을 모두 방문하고 1번 방으로 오면 동현이는 탐색을 끝낸다. N개의 방을, 동현이가 먼저 방문한 순으로 정렬..
-
알고리즘...98일지 2022. 1. 5. 15:48
해시 테이블 이차원 조사 구현 기존 구현에 추가로 충돌 해결용 함수만 구현한다. 이번에는 i를 순서대로 더하는 대신 i의 제곱값을 더하는 방식으로 빠르게 군집을 벗어나도록 만든다. int HashTable_OpenAddressing_QuadraticProbing::GetProperHashIndex(int idx, int data) { int properIdx{ idx }; int i{ 1 }; while (m_table[properIdx] != Empty && m_table[properIdx] != data) { properIdx = (idx + (i * i)) % Size(); i++; } return properIdx; } main.cpp #include "Common.h" #include "해시테이..