문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸..

문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다. 예제 입력 3 10 1 2 5 예제 출력 10 접근 Dynamic Programming으로 접근한다. 첫 번째 동전만 사용하여 각 k값 마다 가능한 경우의 수를 ..

해쉬 테이블(hash table) 해쉬 테이블은 키(key)라는 특별한 인덱스로 자료에 접근하는 배열로 구성되는 자료구조 이다. 해쉬 테이블의 해쉬 함수는 키 값을 받아 그 키의 해쉬값(hash coding 또는 hash value)을 리턴한다. 간단한 해쉬테이블을 시각적으로 표시했을 때, 아래와 같은 그림으로 표시할 수 있다. 해쉬 테이블의 장점은 상수 시간에 탐색이 가능한 것이다. 대신 다른 특징(혹은 단점?)은 순차적인 접근을 지원하지 않는 것이다. 따라서 이러한 특징에 맞는 상황에서 사용되어야 할 것이다. 추가적으로 해쉬 테이블의 특징을 좀 더 알아보자. - 사용할 키와 해쉬 함수를 잘 선택하여 테이블에 균등하게 항목이 배분되도록 해야 한다. - 다른 키값에 대해 같은 해쉬값(같은 테이블로 매핑되..

kd-트리(다차원검색트리)는 이진 탐색 트리를 다차원 공간으로 확장한 것으로써 기본 구조와 알고리즘은 BST와 유사하지만 트리의 레벨 차원을 번갈아 가며 비교한다는 점이 다르다. KD-트리 - 이진검색트리를 확장한 것으로 k개(k≥2)의 필드로 이루어지는 키를 사용 - 동일한 레벨에 있는 노드는 모두 동일한 하나의 필드만 이용해서 분기한다 KD-트리 삽입 A(50, 50) → B(10, 70) → C(80, 85) → D(25, 20) → E(40, 85) → F(70, 85) → G(10, 60) 1. A(50, 50)이 루트 자리를 차지 2. B(10, 70)는 x값 10이 루트의 x값 50보다 작으므로 왼쪽 자식이 된다 3. C(80, 85)는 x값 80이 루트의 x값 50보다 크므로 오른쪽 자식이..

개요 º Balanced Tree란? - 이진 검색 트리의 문제점은 좌우 균형이 맞지 않으면 비효율적. 트리의 성능은 곧 트리의 depth인데, 좌 또는 우로 치우친 경우 O(logN) → O(n^2)까지 성능이 느려질 수 있다. - Balanced Tree는 삽입, 삭제 시 필요하면 스스로 균형을 유지한다. - ex) AVL Tree, 2-3(-4) Tree, Red-Black Tree, B-Tree 등 - 항상 (최악의 경우에도) O(logN) 성능을 보장 º B-Tree란? - 하나의 노드에 여러 자료가 배치되는 트리 구조 - 한 노드에 최대 m개의 자료가 배치되면 → 'M차 B-Tree' (단, 모든 노드에 항상 m개의 자료가 배치되어야 하는 것은 아님) - m이 짝수냐 홀수냐에 따라 알고리즘이 ..

레드블랙트리 이진탐색트리는 저장과 검색에 평균 O(logn)시간이 소요되지만 운이 나쁘면 트리의 모양이 균형을 잘 이루지 못한다. 균형이 많이 깨지면 O(n)에 근접한 시간이 소요될 수도 있다. 그래서 고안해낸 것이 균형잡힌 이진 검색 트리이다. 특성 레드-블랙 트리는 각각의 노드가 레드 나 블랙 인 색상 속성을 가지고 있는 이진 탐색 트리이다. 이진 탐색 트리가 가지고 있는 일반적인 조건에 다음과 같은 추가적인 조건을 만족해야 유효한(valid) 레드-블랙 트리가 된다 노드는 레드 혹은 블랙 중의 하나이다. 루트 노드는 블랙이다. 모든 널 포인터는 블랙이다. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 ..