전체 글45 [알고리즘] [10] 트리 1. 트리(Tree) 비선형 자료구조 원소들 간 관계가 일대다인 계층형 자료구조 노드 (Node)는 트리의 원소이며, 최상위 노드를 루트 (root)라고 한다. 노드에 연결된 나머지 노드들은 각각 하나의 트리로 묶이며(재귀적 정의) 이를 부트리 (subtree)라 한다. 트리 용어 형제 노드 (sibling node) : 같은 부모를 가지는 자식 노드들 조상 노드 : 간선을 따라 루트 노드까지 이르는 경로의 모든 노드들 서브 트리 (subtree) : 부모 노드와의 간선을 끊었을 때 생기는 새로운 트리 자손 노드 : 서브 트리에 있는 하위 노드들 차수 (degree) >> 노드의 차수 : 노드에 연결된 자식 노드 수 >> 트리의 차수 : 트리에 있는 노드 차수 중 가장 큰 값 >> 단말 노드 (리프 노드.. 2024. 2. 6. [알고리즘] [9] 연결리스트 1. 리스트 (List) 순서를 가지는 데이터의 집합으로 추상 자료형이다. 데이터의 중복이 허용된다. 구현 방법에 따라 크게 순차 리스트, 연결 리스트로 나뉜다. 2. 순차 리스트 : 배열을 기반으로 구현되는 리스트 1차원 배열에 순서대로 저장한다. 배열의 인덱스로 데이터에 접근한다. 특정 위치에 원소를 삽입 후 삽입 위치 다음의 항목을 뒤로 이동한다. 특정 위치의 원소를 삭제 후 뒤의 원소들을 앞으로 이동시킨다. 단순 배열을 이용한 순차 리스트는 자료의 삽입 및 삭제에 소요되는 시간이 크다. 3. 연결 리스트 : 메모리의 동적 할당을 기반으로 구현되는 리스트 자료의 논리적 순서와 메모리 상의 물리적 순서가 일치하지 않는다. 개별적으로 위치하는 각 원소를 연결하여 전체 자료 구조를 구성한다. 원소의 물리.. 2024. 2. 5. [알고리즘] [8] 부분 집합 1. 부분 집합 집합에 포함된 원소들을 순서 없이 택하는 것 집합에서 최적의 부분 집합을 찾는 알고리즘이 많다. >> ex. 배낭 (knapsack) 재귀로 부분 집합을 생성할 수 있다. import java.util.Scanner; public class PowerSetTest { static int n, input[]; static boolean isSelected[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); input = new int[n]; isSelected = new boolean[n]; for (int i = 0; i < n; i++) { input[i] = s.. 2024. 2. 1. [알고리즘] [7] 조합 1. 조합 (Combination) 서로 다른 n개의 원소 중 r개를 순서 없이 택하는 것 nCr = n-1Cr-1 + n-1Cr 의 재귀적 표현이 가능하다. nC0 = 1 재귀를 이용한 조합 생성 // nCr input[]; // n 개의 원소를 가지는 배열 numbers[]; // 조합을 저장할 r 크기의 배열 comb(cnt, start) { // cnt : 현재까지 선택한 원소 개수. start : 조합할 원소의 시작 인덱스 if (cnt == r) { return; } else { for (i = start; i < n; i++) { numbers[cnt] = input[i]; comb(cnt + 1, i + 1); } } } 2. 중복조합 순서가 무관하지만 원소의 중복이 가능한경우 nHr = .. 2024. 1. 31. [알고리즘] [6] 완전탐색, 순열 1. Baby-gin Game 0 ~ 9 사이의 숫자 카드에서 임의로 6장을 뽑았을 때 3장의 카드가 연속 번호를 가지는 run과 3장의 카드가 동일한 번호를 가지는 triplet으로만 구성되는 경우를 baby-gin이라고 한다. 6자리 숫자를 입력받았을 때 baby-gin 여부를 판단하는 프로그램을 작성한다. (1, 2, 3, 1, 2, 3) 정렬하여 확인하는 등 탐욕 알고리즘적인 접근은 해답을 찾지 못할 수도 있다. 2. 완전 검색 (Exhaustive Search) 모든 경우의 수를 나열하고 확인하는 기법 Brute force 혹은 generate-and-test 기법이라고 부른다. 상대적으로 빠른 시간에 알고리즘 설계가 가능하며 경우의 수가 작은 경우 유용하다. 수행 속도는 느리지만 해답을 찾아내.. 2024. 1. 30. 이전 1 2 3 4 5 6 7 ··· 9 다음