본문 바로가기
정렬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.
4. SQL 1. SQL 2. DDL 3. DML 4. DCL 5. Join 6. View 7. Transaction 1. SQL : 관계형 데이터 베이스의 표준 질의어로 정의, 조적, 제어기능을 모두 갖춘 언어 - sql 구성요소 a) DDL b) DML c) DCL 2. DDL : 놀리적 데이터 구조와 물리적 데이터 구조의 사상을 정의 - CREATE : schema, domain, table, view, index 정의 - ALTER : table에 대한 정의를 변경 - DROP : schema, domain, table, view, index 삭제 3. DML : 데이터베이스 사용자가 응용 프로그램이나 질의어를 통하여 저장된 데이터를 실질적으로 처리하는 데 사용되는 언어 - SELECT : 테이블에서 조건에 .. 2020. 7. 19.
3. Database Design 1. Database Design 2. Normalization 1. Database Design - 개념 : 사용자의 요구를 분석하여 그것들을 컴퓨터에 저장할 수 있는 데이터베이스의 구조에 맞게 변형한 후 특정 DBMS로 데이터베이스를 구현하여 일반 사용자들이 사용하게 하는 것 - 설계 순서 a) 요구조건분석 : 데이터베이스를 사용할 사람들로부터 필요한 용도를 파악 >> 수집된 정보를 바탕으로 요구 조건 명세를 작성 b) 개념적 설계 : 정보의 구조를 얻기 위하여 현실 세계의 무한성과 계속성을 이해하고, 다른 사람과 통신하기 위하여 현실 세계에 대한 인식을 추상적 개념으로 표현하는 과정 >> 요구 조건 명세를 E-R 다이어그램으로 작성 c) 논리적 설계 : 현실 세계에서 발생하는 자료를 컴퓨터가 이해하.. 2020. 7. 19.

티스토리툴바