코딩 기록 저장소

1. 전형적인 그리디 알고리즘의 구조 - 눈앞의 이익만 우선 추구하는 알고리즘을 총칭해서 그리디 알고리즘이라 함. - 대부분의 경우 뛰어난 결과를 도출하지 못하지만 드물게 최적해를 보장하는 경우도 있음. - 그리디 알고리즘은 최적화 문제를 대상으로 함. - 최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼음. do { 가장 좋아 보이는 선택을 함; } until ( 해 구성 완료 ) - 그리디 알고리즘은 하나의 온전한 해가 만들어질 때까지 눈앞에 가장 좋아보이는 선택을 반복함. - 간선이 하나도 없는 집합에서 시작해서 간선을 하나씩 더해가면서 n-1개의 간선이 될 때까지 집합을 키워나감. - 각 단계에서 어떤 간선을 택할지 결..

1. 그래프 - 그래프는 현상이나 사물을 정점과 간선으로 표현하는 것. - 정점은 대상이나 개체를 나타내고, 간선은 이들 간의 관계를 나타냄. - 방향을 가진 간선으로 그래프를 나타내면, 방향을 가진 그래프 또는 유향 그래프라고 함. - 반면, 간선의 방향이 없는 그래프를 무향 그래프 또는 무방향 그래프라고 함. - n개의 정점 집합 V와 이들 간에 존재하는 간선의 집합 E로 구성된 그래프 G를 보통 G=(V,E)로 표시함. 2. 그래프의 표현 - 크게 행렬을 이용하는 방법과 리스트를 이용하는 방법이 있음 인접 행렬을 이용한 방법 - 행렬 표현법은 이해하기 쉽고 간선의 존재 여부를 즉각 알 수 있다는 장점이 있음. - 정점 i와 정점 j의 인접 여부는 행렬의 (i, j) 원소나 (j, i) 원소의 값만 ..

1. 어떤 문제를 동적 프로그래밍으로 푸는가 - 동적 프로그래밍은 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고, 이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 재귀적 중복을 해결하는 방법을 뜻함. - 피보나치 수 구하기에 동적 프로그래밍의 개념을 이해할 수 있는 핵심이 모두 들어있음. f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 - n의 피보나치 수는 n-1의 피보나치 수와 n-2의 피보나치 수를 포함하고 있음. - 이처럼 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있으면 최적 부분 구조를 가졌다고 함. - 동적 프로그래밍을 적용하려면 문제가 일단 이 성질을 가져야 함. - 간명하지만 때때로 엄청난 비효율을 초래할 수 있음. - 문제의 크기가..

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진 검색 트리라 하면 자식을 최대 ..