본문 바로가기

공부

자료의 정렬 - 삽입 정렬(Insertion sorting)
공부/자료 구조 및 알고리즘 2019. 7. 26. 자료의 정렬 - 삽입 정렬(Insertion sorting) 삽입 정렬(Insertion sorting) 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘. 삽입 정렬(Insertion sorting)의 방법 ① 두수를 비교하여 큰수를 오른쪽으로 이동 ② 새로운 수가 들어오면 왼쪽 값과 차례대로 비교하면서, 값이 크면 오른쪽으로 이동 ③ 비교 값보다 작은 값이 나오면 멈춘다. 삽입 정렬(Insertion sorting) 예시 두 수를 비교하여 큰 수를 오른쪽으로 이동 왼쪽 값과 차례대로 비교하면서, 값이 크면 오른쪽으로 이동 위 사진으로는 뭔가 감이 잘 오지않는다. 쫌더 자세히 살펴보자. 일단, 무작위 숫자 3, 10, 41, 21, 42, 34, 13, 1, 43, 12를 정..
알고리즘 기법[부분 탐색] - 분기 한정(Branch & Bound)
공부/자료 구조 및 알고리즘 2019. 7. 22. 알고리즘 기법[부분 탐색] - 분기 한정(Branch & Bound) 분기 한정(Branch & Bound) 분기: branch, 한정: bound →분기를 한정시켜 쓸데없는 시간 낭비를 줄이는 방법 백트래킹에서 부가적으로 발생한 알고리즘 설계 기법 백트래킹이 허용되는 탐색에서 더 이상 탐색할 필요가 없는 지점을 판단하는 것. -비선형 구조의 탐색 과정에서 더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀 -탐색과정에서 더 이상 의미가 없다고 판단되는 데이터에 대해서는 더 이상 탐색하지 않고 백트래킹함. -나무에서 필요없는 가지를 잘라내는 가지치기와 유사하여 가지치기 기법이라고도 함. 만약 2번에서 3번으로 진행하려고 할 때, 3번 이하의 모든 노드를 더 이상 탐색할 필요가 없다고 판단할 경우, 이하의 탐색을 중단하고 9번으로 진행할 수 있다. 위 그림은 더 이상 탐..
알고리즘 기법[부분 탐색] - 탐욕적 방법(Greedy method)
공부/자료 구조 및 알고리즘 2019. 7. 21. 알고리즘 기법[부분 탐색] - 탐욕적 방법(Greedy method) 탐욕적 방법(Greedy method) 전체 문제가 여러 단계로 구성되어 있는 경우에 각 단계별로 최적 해를 구함으로써 전체 문제를 해결하려는 알고리즘 설계 방법. -수학적으로 탐색 영역을 배제함. -문제를 해결하기 위해서 해가 될 수 있는 모든 부분(전체적 최적화)을 탐색하는 것이 아니라, 탐색할 부분을 제한(부분적 최적해하여 원하는 해를 구하는 방법. -전체적 최적화에 도달하지 못하는 경우가 있을 수 있음. -올바른 해를 구하기 위해 탐색을 배제한 부분에 대한 수학적 검증이 필요. Greedy 예시 및 알고리즘 1. CPU 스케줄링(scheduling) 문제 선점을 허용하지 않는 하나의 CPU와 n개의 작업이 있을 때 CPU 스케줄링은 작업 시간의 크기를 기준으로 오름차순 정렬하여 작업 시간이 가장 ..
알고리즘 기법[전체 탐색] - 백트래킹(Backtracking)
공부/자료 구조 및 알고리즘 2019. 7. 19. 알고리즘 기법[전체 탐색] - 백트래킹(Backtracking) 백트래킹(Backtracking) 비선형으로 구성된 자료 구조를 깊이 우선으로 탐색할 때, 더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀하는 과정을 말한다. -일반적으로 최적화 문제를 해결할 때 사용하는 방법이다. -문제를 비선형으로 구조화한 다음, 가능한 모든 상태를 깊이 우선으로 탐색해가며 해를 구성해 나간다. -이 과정에서 더 이상 탐색을 진행할 수 없으면 백트래킹하여 다시 다른 상태를 조사해 나간다. -모든 가능한 상태를 다 조사하며 이를 백트래킹 기법이라 한다. 문제해결 방법 ① 주어진 문제를 비선형 구조로 구조화한다. ② 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다. ③ 구성된 해를 정리한다. 예제 및 알고리즘 주어진 3 x 3 행렬에서 개의 원소를 서로 행과 열이..
알고리즘 기법[전체 탐색] - 브루트 포스(brute force)
공부/자료 구조 및 알고리즘 2019. 7. 16. 알고리즘 기법[전체 탐색] - 브루트 포스(brute force) 암호학에서의 브루트 포스(brute force attack)가 아닌 알고리즘의 브루트 포스(brute force search)에 관한 것을 작성한다. 브루트 포스(brute force) brute: 무식한, force: 힘 무식한 힘으로 해석할 수 있다. 완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다. 일반적 방법으로 문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색할 수 있는 방법을 필요로 한다. 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다. 선형 구조를 전체적으로 탐색하..
자료의 탐색 - 해싱(Hashing)
공부/자료 구조 및 알고리즘 2019. 7. 15. 자료의 탐색 - 해싱(Hashing) 해싱(Hashing) 순차 탐색이나 이진 탐색의 비교 연산이 아닌 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 찾아가는 계산 탐색 방법. 해싱(Hashing) 탐색방법 ① 키값에 대해서 해싱 함수를 계산하여 주소를 구한다. ② 구한 주소에 해당하는 해시 테이블로 바로 이동한다. ③ 해당 주소에 찾는 키가 있으면 탐색을 성공한 것이며, 해당 주소에 찾는 키가 없으면, 찾는 원소가 없는 것으로 판단한다. 해싱(Hashing) 예제 문제: 10장으로 구성 수가 다음과 같다고 가정한다. 1)해싱 함수를 수 자체 해시값으로 정의한 경우 각 숫자가 저장된 위치는 다음과 같이 저장된다. 즉, 34의 경우는 34번째 공간에 저장되며 1은 첫 번째 공간에, 999는 999번째 공간에 저장되어 찾고자 하는 수가 3..
자료의 탐색 - 이진 탐색(Binary search)
공부/자료 구조 및 알고리즘 2019. 7. 13. 자료의 탐색 - 이진 탐색(Binary search) 이진 탐색(Binary search) 가운데에 있는 항목을 키값과 비교하여 다음 탐색 위치를 결정하여 키를 찾을 때까지 이진 탐색을 반복적으로 수행한다. ex) 순차 탐색과 달리 묶음 책 속의 수들이 차례대로 정렬되어 있는 구조를 가졌다는 전제를 토대로 책의 중간에 위치한 수를 먼저 비교하고 찾고자 하는 수가 비교한 수보다 큰 경우는 책의 오른쪽 부분을 탐색하고 작은 경우는 책의 왼쪽 부분을 탐색하는 것을 반복하는 방법. - 찾는 키값 > 원소의 키값: 오른쪽 부분에 대해서 이진 탐색 실행 - 찾는 키값 list[middle] ) return list[middle+1]부터 list[high]에서의 탐색; 이진탐색(Binary search) 예제 문제: 10장으로 구성된 묶음 책으로 각 장에 수가 다음과 ..
자료의 탐색 - 순차 탐색(Sequential search)
공부/자료 구조 및 알고리즘 2019. 7. 12. 자료의 탐색 - 순차 탐색(Sequential search) 순차탐색(Sequential search) 데이터의 첫 부분(선두)부터 순서대로 탐색키와 데이터를 비교하여 원하는 데이터를 찾는 방법. ex) 책에서 원하는 자료를 찾고자 할 때 처음부터 차례대로 한 장씩 열어 보고 원하는 자료를 찾는 방법이다. 첫 번째 장의 자료가 찾고자 하는 자료인지를 보고 만일 찾는 자료가 아니라면 두 번째 장의 자료를 열어 보고 찾는 자료가 아니라면 다시 다음 장을 살펴보는 방법이다. 책 속의 자료들의 배치에 대한 아무런 정보 없이 원하는 자료를 찾는 극히 단순하며 정확한 방법이다. → 즉, 자료를 처음부터 마지막까지 순서대로 탐색하는 가장 간단하고 이해하기 쉬운 직접적인 탐색 방법이다. 순차탐색(Sequential search) 탐색방법 ① 자료의 집합에서 첫 번째 원소부터 시..
문재 해결을 위한 기본적 접근 방법 - 트리(Tree)
공부/자료 구조 및 알고리즘 2019. 7. 12. 문재 해결을 위한 기본적 접근 방법 - 트리(Tree) 자료를 포함하고 있는 노드(node)와 노드들 간의 관계(edge)로 구성되며, 임의의 두 노드는 부모(parent)와 자식(child) 관계만을 갖는다. root node: 최상단의 부모 노드를 갖지 않는 노드 leaf node: 트리에서 자식 노드를 가지고 있지 않는 노드 Internal node: 루트 노드와 잎새 노드 제외한 나머지 노드 sibling node(형제 노드): 같은 부모를 가진 자식 노드 *트리의 특징 ① 트리는 계층적 자료를 표현하는데 적합한 자료 구조이다. ② 트리에서 자료의 저장은 노드에 한다. ③ 트리에서 부모가 없는 노드를 루트 노드라고 하고 자식이 없는 노드를 잎새 노드라고 한다. ④ 이진 탐색 트리는 한번의 경로 탐색으로 자료의 유무 및 원하는 자료를 검색할 수 있다. ..

티스토리툴바