코딩 기록 저장소

1. 연결 리스트를 이용한 집합의 처리 연결 리스트 - 각 원소당 하나의 노드를 만들고 이들을 연결 리스트로 연결함. - 각 노드에는 원소를 저장하는 필드와 다음 원소, 대표 원소를 가리키는 두 개의 포인터가 있음. - 다음 원소를 가리키는 포인터를 이용해 집합의 모든 원소가 연결 리스트로 연결됨. - 각 집합에는 마지막 원소를 가리키는 tail이라는 변수를 둠. 이것은 두 집합을 합칠 때 시간을 절약할 수 있게 해줌. 상호 배타적 집합의 관리를 위해 필요한 세 가지 연산 1. Make-Set(x) : 원소 x로만 구성된 집합을 만듦. - 노드를 하나 만들어 해당 원소를 저장함. 대표 노드로는 자신을 가리키도록 하고, 다음 원소는 없으므로 포인터는 NIL로 해둠. 2. Find-Set(x) : 원소 x를..

1. 해시 테이블 : 검색 효율의 극단 - 검색 트리는 원소가 저장될 자리가 이미 트리에 존재하는 원소와 비교하여 결정되는 반면, 해시 테이블은 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조. - 저장된 자료와 비교하여 자리를 찾지 않고 단 한 번의 계산으로 자신의 자리를 찾음. - 임의의 원소를 해시 테이블에 저장하려면 먼저 해당 원소의 해시 값을 계산 함. - 해시 값은 해시 함수로 계산됨. - 해시 테이블이 총 m개의 원소를 저장할 수 있다면 테이블의 각 자리는 0부터 m-1의 주소 값을 갖고, 해시 함수는 임의의 원소 값을 입력으로 받아 0,1,2, ... , m-1 중의 한 값을 리턴함. - 이 리턴 값이 바로 해당 원소를 저장하는 주소. - 가장 간단한 방법은 원소 값이 x라면 x를..

1. 레코드, 키의 정의 및 검색 트리 레코드 - 개체에 대한 모든 정보를 포함. - 각각의 정보를 나타내는 부분을 필드라고 함. - 검색트리에 레코드 전부 저장 가능하지만 보통은 해당 레코드를 대표할 수 있는 필드만으로 검색트리를 만듦. 키 - 다른 레코드와 중복되지 않으면서 레코드를 대표할 수 있는 필드를 검색키 또는 키라고 함. - 키는 필드 하나로 구성할 수도 있고, 복수 개의 필드로 구성할 수도 있음. 검색 트리 - 한 노드에서 최대 몇 개의 자식 노드로 분기를 할 수 있느냐에 따라 이진 검색 트리와 다진 검색 트리로 나눔. - 이진 검색 트리는 최대 두 개의 자식 노드를 가질 수 있고, 다진 검색 트리는 세 개 이상의 자식 노드로 분기 가능. - 일반적으로 k진 검색 트리라 하면 자식을 최대 ..

1. 평균 선형 시간 선택 알고리즘 - 퀵 정렬처럼 분할한 후 자기호출 방법을 쓰면 평균적으로 선형 시간에 i번째 작은 원소를 찾을 수 있음. 그렇지만 이 알고리즘은 최악의 경우 O(n²) 시간이 소요됨. - 이번 알고리즘은 단점을 개선해서 최악의 경우에도 선형 시간에 i번째 작은 원소를 찾을 수 있게 함. - n개의 원소가 규칙 없이 저장된 배열에서 i번째 작은 원소를 찾으려 함. - 분할 알고리즘이 리턴하는 값으로 기준 원소가 전체에서 몇 번째 작은 원소인지 알 수 있음. - 기준원소가 전체에서 k번째 작은 원소란 사실을 알면, i와 k의 값을 비교해서 작으면 왼쪽 그룹에 있는 원소 중 하나이고, 같으면 기준 원소가 바로 i번째 작은 수이고, 크면 i 번째 작은 수는 오른쪽 그룹에 있는 원소 중 하나..

1. 기본적인 정렬 알고리즘 선택 정렬 - 선택 정렬은 원리가 간단한 정렬 알고리즘 중 하나. - 배열 A[1~n]에서 가장 큰 원소를 찾아 이 원소와 배열의 끝자리에 있는 A[n]과 자리를 바꿈. - 맨 뒷자리로 옮긴 가장 큰 원소는 제외하고 나머지 원소들로 같은 작업을 반복함. selectionSort(A[],n) { ① for last

1. 점화식 - 점화식은 어떤 함수를 자신과 똑같은 함수를 이용해 나타내는 것. - 동일한 함수가 등호나 부등호의 양쪽에 나타나는데, 양쪽 함수는 변수의 크기가 다를 뿐임. - n!의 점화식은 f(n)=n * f(n-1) - 피보나치 수열의 점화식은 f(n) = f(n-1) + f(n-2) - 점화식은 재귀 함수의 복잡도를 구하는 데 유용함. 자기 호출을 사용하는 알고리즘은 매우 흔함. - 명시적으로 자기호출을 사용하지 않더라도 그 속에서 자신과 똑같지만 크기가 다른 문제를 발견할 수 있는 경우도 있음. - 재귀적 관계를 이용해 알고리즘의 수행 시간을 점화식으로 표현할 수 있음. mergeSort(A[], p, r) // A[p ~ r]을 정렬함 { ① if ( p < r ) then { ② q