탐색1 : 선형탐색, 이진탐색 탐색의 분류 1. 선형 자료구조 ( 어레이, 리스트, ...) 내에서의 탐색 선형탐색 (linear search) 또는 순차탐색 (sequential search) 이분탐색 (binary search) : 분할정복을 이용한 탐색 해싱 (hashing) 2. 비선형 자료구조 ( 트리, 그래프, ...) 내에서의 탐색 tree traversal DFS BFS 선형탐색, linear Search 정의 : 데이터의 집합을 처음부터 끝까지 차례대로 하나씩 검색하는 방법 장점 : 구현하기 쉽고 데이터 집합이 정렬되어 있지 않아도 된다 단점 : 검색시간이 오래걸린다 시간복잡도 worst : O(n) average : O(n) best : O(1) // 첫번째 인덱스의 값이 찾고자 하는 값인 경우 이분탐색, Binar.. 2020. 7. 19. 정렬3 : heap sort Heap Sort 최대 힙 트리나 최소 힙 트리를 이용해 정렬을 하는 방법 heap : 반정렬 상태 ( 부모노드 >= 자식노드 or 부모노드 2020. 7. 19. 정렬2 : 분할정복을 이용한 정렬 분할정복을 이용한 정렬 Merge Sort Quick Sort Merge Sort merge sort pseudo algorithm 1. 정렬할 데이터 집합을 반으로 나눈다 2. 나누어진 하위 데이터 집합의 크기가 2이상이면 이 하위 데이터 집합에 대해 1번 작업을 반복한다 3. 원래 같은 집합에서 나뉘어진 두 개의 하위 데이터 집합의 원소들을 크기 순서에 맞춰 정렬하고 병합. 4. 데이터 집합이 하나가 될 때까지 3번작업을 반복 시간복잡도 worst : O(nlogn) average : O(nlogn) best : O(nlogn) Quick Sort quick sort 분할 정복 알고리즘을 이용한 매우 빠른 수행 속도를 자랑하는 정렬 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게.. 2020. 7. 19. 정렬1 : selection, insertion, bubble sort election sort insertion sort bubble sort Selection Sort 제자리 정렬(in-place sorting) 알고리즘의 하나 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다. 두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최솟값을 넣는다. 과정 설명 주어진 배열 중에서 최솟값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)). 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다. time complexit.. 2020. 7. 19. 다이나믹 프로그래밍 Dynamic Programming, 동적계획법 DP란 어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어질 때, 각 단계에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법 분할정복은 문제를 위에서 아래로 쪼개지만 (top-down), DP는 작은 부분 문제부터 상위에 있는 문제로 풀어 올라간다(bottom-up). 분할정복의 쪼갠 문제는 완전히 독립적인 하나의 새로운 문제이지만, DP는 각 단계의 부분 문제들이 이전 단계에 있는 문제들의 답에 의존한다. => DP는 한번 푼 적이 있는 부분 문제의 답은 다시 푸는 일이 없도록 테이블에 저장하여 재활용 메모이제이션 (memoization) : 결과를 저장하는 장소를 마련해 두고, 한번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법. 메모.. 2020. 7. 19. 분할정복 Divide & Conquer 문제를 더 이상 나눌 수 없을 때까지 나누고, 이렇게 나누어진 문제들을 각각 풂으로써 결국 전체 문제의 답을 얻는 알고리즘 분할정복 알고리즘의 핵심은 "문제를 잘게 쪼개기", 하지만 문제를 쪼개는 방법에 대해서 정해진 규칙은 없다 분할정복의 3가지 구성요소 divide : 문제를 더 작은 문제로 분할 base case : 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 merge : 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합 분할시 생기는 각 하위 문제는 완전히 독립접이므로 네트워크상의 여러 컴퓨터에 의해 병렬처리가 가능 예제 BOJ 1780 - 종이의 갯수 https://www.acmicpc.net/problem/1780 2020. 7. 19. 이전 1 2 다음
