분류 전체보기45 [알고리즘] [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 8 ··· 12 다음