Seungsu Hwang

1. 들어가며 "주어진 알고리즘의 연산 횟수를 입력 크기 N에 대한 다항식 형태로 표현할 수 있다면, 그 알고리즘은 효율적이라고 할 수 있다" * 수학에서, 다항식(多項式, 문화어: 여러마디식, 영어: polynomial)은 한 개 이상의 항의 합으로 이루어진 식이다. 즉, 단항식의 결합(덧셈과 뺄셈)으로 이루어진 식이다. 예를 들어, x2 - 2x + 3, 4x3, 5xy + 6은 모두 다항식이다. 다항 시간(polynomial-time) 알고리즘을 이용하여 솔루션을 구할 수 있는 문제를 계산 복잡도 관점에서 클래스 P(Polynomial Time, 다항 시간) 문제라고 한다. 이외에도 다른 형태의 계산 복잡도로 표현되는 문제들이 있으며, 다음과 같다. - NP(Non-Deterministic Poly..

1. C++ 해시 테이블 (unordered_set, unordered_map) 정수로부터 해시 값을 계산하기 위해 사용했던 모듈로 함수는 문자열과 같은 다른 타입에는 적용할 수 없다. C++는 모든 기본 데이터 타입에 대한 해시 값을 생성하는 기능을 제공한다. 일례로 C++은 문자열로부터 해시 값을 생성하는 용도로 std::hash(std::string) 함수 객체가 있다. STL은 템플릿의 형태로 모든 데이터 타입에 대한 해시 테이블을 제공한다. - std::undordered_set: 키만 저장 - std::unordered_map: 키와 값을 함께 저장 두 컨테이너 모두 체이닝을 사용하는 형태로 구현되어 있고, 각 행은 키 또는 키와 값의 쌍을 저장하는 벡터이다. 여기서 각 행을 버킷(bucket..

해시 테이블 모든 원소를 선형으로 검토하여 원하는 값을 찾는 작업은 O(N)의 매우 많은 시간이 소요되고 비효율적이다. BST와 같은 속성을 갖도록 높이 균형 트리에 데이터를 저장하더라도 O(logN)이라는 시간이 소요되고 검색 횟수가 크게 증가할 경우 이 정도 연산도 만족스럽지 않다. 위 경우보다 더욱 효율적인 방법은 해시 테이블을 이용하는 것이다. 해싱은 각각의 데이터를 가급적 고유한 숫자 값으로 표현하고, 나중에 같은 숫자 값을 사용하여 데이터의 유무를 확인하거나 해당 숫자에 대응하는 원본 데이터를 추출하는 작업이다. 이때 주어진 데이터로부터 고유한 숫자 값을 계산하는 함수를 해시 함수라고 한다. 가장 간단한 구조의 해시 테이블 : 충돌 문제 발생 가장 간단한 해시 함수는 큰 범위의 정수를 인자로 ..

트리의 단점 하나의 노드에서 다른 노드로 이동하는 경로가 하나만 존재하기 때문에 원형 또는 순환적인 종속성을 표현할 수 없다. 예를 들어 도로망과 같이 특정 장소(노드)에서 다른 장소로 이동하기 위한 다양한 경로가 존재하는 경우 그래프를 이용해야 한다. 그래프 그래프는 노드 데이터뿐만 아니라 노드 사이의 엣지 데이터도 저장해야 한다. 엣지에 가중치 또는 더 많은 정보를 부여한 그래프를 가중 그래프, 그렇지 않은 그래프를 비가중 그래프라고 한다. 그래프는 방향성에 따라 방향 그래프와 무방향 그래프로 구분할 수 있다. 무방향 그래프는 기본적으로 엣지가 양방향임을 의미하고, 방향 그래프는 단방향을 의미한다. 만약 방향 그래프에서 양방향을 표현하려면 A->B, B->A로 향하는 두 엣지를 사용해야 한다. 그래프..