다양한 정렬 알고리즘 간단한 정렬 알고리즘의 특징 O(n^2) 선택정렬 입력의 크기에 따라 자료 이동 횟수 결정 삽입 정렬: 레코드의 많은 이동이 필요. 대부분의 레코드가 이미 정렬되어 있는 경우 효율적 버블정렬: 가장 간단한 알고리즘(인접한 두 데이터를 비교하며 정렬) 효율적인 알고리즘들 셸 정렬: 삽입 정렬 개념을 개선한 방법 힙 정렬: 제자리 정렬로 구현하는 방법 병합 정렬: 연속적인 분할과 병합을 이용 퀵 정렬, 이중피벗 퀵 정렬: 피벗을 이용한 정렬 기수 정렬: 분배를 이용해 정렬: 키값에 제한이 있음 셸 정렬 기본 아이디어 삽입정렬은 어느정도 정렬된 리스트에서 매우 빠름 하지만 요소들이 이웃한 위치로만 이동 -> 많은 이동 발생 요소들이 멀리 떨어진 위치로 이동할 수있게 한다면 보다 적게 이동..
Algorithm & Data structure
1. 그래프란? 연결되어 있는 객체 간의 관계를 표현하는 자료구조 가장 일반적인 자료구조 형태 선형 자료구조들이나 트리도 그래프로 표현할 수 있음 그래프의 역사 오일러 문제 다리를 한번만 건너서 처음 출발했던 장소로 돌아오는 문제 위치: 정점(node), 다리: 간선(edge) 오일러 정리 모든 정점에 연결된 간선의 수가 짝수 or 홀수가 2개이면 오일러 경로 존재함 멀티 그래프에서 모든 연결선들을 꼭 한 번씩만 통과하는 경로를 오일러 경로라고 함. 이는 쾨니히스베르크 다리 문제는 오일러 경로를 찾을 수 있는지 여부와 동치임 멀티그래프에서의 오릴러 경로를 판별하는 규칙은 모든 정점에서 그것과 연결된 연결선의 개수가 홀수인 정점홀수점)의 개수가 0 또는 2개 그래프의 정의 그래프 G는 (V,E)로 표시 정..
가중치 그래프 가중치 그래프의 표현 파이썬 리스트로 표현 vertex = ['A', 'B', 'C', 'D', 'E', 'F', 'G' ] weight = [ [None,29,None,None,None, 10,None], [29,None,16,None,None,None,15 ], [None,16,None,12,None,None,None], [None,None, 12,None,22,None,18 ], [None,None,None, 22,None,27,25 ], 인접행렬: 간단한 계산 인접행렬에서의 가중치의 합 계산 # 코드 11.2: 가중치 그래프의 가중치 합(인접 행렬) def weightSum( vlist, W ):# 매개변수: 정점 리스트, 인접 행렬 sum = 0# 가중치의 합 for i in ra..
삽입 삭제에 있어 비효율적인 부분을 O(log n)으로 바꾸어주는 트리 9.1 탐색트리란? 탐색트리란? 탐색을 위한 트리 기반의 자료구조 이진탐색트리 효육적 탐색을 위한 이진트리 기반의 자료구조 이진탐색의 단점(삽입/삭제 연산의 비효율성)을 극복할 수 있음 삽입, 삭제, 탐색 : O(log n) 이진탐색트리의 정의 모든 노드는 유일한 키를 가짐 왼쪽 서브트리의 키들은 루트의 키보다 작다 오른쪽 서브트리의 키들은 루트의 키보다 크다 왼쪽과 오른쪽 서브트리도 이진탐색트리이다. 이진탐색트리의 주요 연산 탐색 연산: 키를 이용한 탐색, 값을 이용한 탐색, 최대,최소 노드 노드의 구조는 일반적으로 이진트리와 동일 이진탐색트리를 위한 노드클래스 (탐색키,키에 대한 값)의 형태 class BSTNode: def __..
정렬이란? 데이터를 순서대로 정렬하는 것 용어 레코드 : 정렬시켜야 될 대상 여러개의 필드로 이루어짐 정렬 키(sort key) 정렬의 기준이 되는 필드 레코드들을 키의 순서대로 재배열 정렬 알고리즘 종류 복잡도와 효율성에 따른 분류 단순하지만 비효율적: 삽입, 선택, 버블 정렬 등 복잡하지만 효율적: 퀵, 힙, 병합, 기수정렬, 팀 등 키값의 비교를 사용하지 않는 정렬: 기수, 카운팅 정렬 등 결과적으론 똑같지만 자료의 양 등에 따라 결정하면 됨 정렬 장소에 따른 분류 내부(internal) 정렬: 모든 데이터가 메인 메모리 외부(external) 정렬: 외부 기억장치에 대부분의 레코드 실제로 외부 자체에서 정렬되지 않지만 데이터가 무수히 많을 때 쪼개서 재배열 안정성 같은 데이터를 가졌음에도 정렬 시..
큐(Queue) 선입선출(First-In First Out: FIFO)의 자료구조 먼저 들어온 데이터가 먼저 처리됨 예: 줄서기 대기열 큐의 구조 전단: 삭제 통로 후단: 삽입 통로 추상 자료형 연산 연산방식 enqueue(e) 요소 e를 큐의 맨 뒤에 추가 dequeue() 큐의 맨 앞에 있는 요소를 꺼내 반환 isEmpty() 큐가 비어있으면 True, 아니면 False 반환 isFull() 큐가 가득 차 있으면 True, 아니면 False 반환 peek() 큐의 맨 앞에 있는 요소를 삭제하지 않고 반환 연산 주의점 - 꽉 차있는 상태에서 enqueue시 overflow - 모두 비어있는 상태에서 peek시 underflow 큐 예시 프린터와 컴퓨터 사이의 인쇄 작업 큐 (버퍼링) 실시간 비디오 스트..
스택이란 스택(stack) “stack”: 쌓아놓은 더미 후입선출(LIFO:Last-In First-Out)의 자료구조 가장 최근에 들어온 데이터가 가장 먼저 나감 자료의 입출력이 상단으로만 가능 추상자료형 연산 설명 push(e) 요소 e를 스택의 맨 위에 추가 pop() 스택의 맨 위에 있는 요소를 꺼내 반환 isEmpty() 스택이 비어있으면 True, 아니면 False 반환 isFull() 스택이 가득 차 있으면 True, 아니면 False 반환 peek() 스택의 맨 위에 있는 값을 삭제하지 않고 만환 스택의 용도 편집기의 되돌리기 이전 페이지로 이동 함수 호출: 시스템 스택 괄호 검사 계산기 후위표기식 계산, 중위 표기식의 후위 표기식 변환 미로 탐색 등 스택 구현 # 코드 4.2: 배열로 구..
자료형, 리터럴과 변수 예약어 리터럴과 자료형 파이썬에서의 변수 파이썬에서의 변수는 모든 자료가 클래스로부터 만들어진 객체 변수는 다른 객체를 참조하는 참조자 또는 포인터의 역할 컬렉션 자료형 여러 자료를 묶어 한꺼번에 저장하고 처리할 수 있도록 지원 시퀀스형 문자열(str) 리스트(list) 튜플(tuple) 리스트와 동일하지만 크기나 값을 변경 못함 매핑형 딕셔너리(dict) 키(key)와 관련된 값(value)으로 이루어진 항목들의 집합 집합형 집합(set, frosenset) 변수의 범위 내장 범위(built-in scope) 언어의 일부로 정의된 변수와 리터럴들 프로그램의 어디에서나 사용할 수 있다. 전역 범위(global scope) 소스 파일의 맨 꼭대기 레벨(함수나 클래스 밖)에서 생성 프..
선형 자료구조와 비선형 자료구조 선형 자료구조 자료를 순서적으로 나열하여 저장하는 창고 접근 방법에 따라 다시 세분화: 리스트, 스택, 큐, 덱 등 비선형 자료구조 복잡한 연결 관계의 자료 표현 트리: 회사의 조직도나 컴퓨터의 폴더와 같은 계층 구조 그래프: 가장 복잡한 연결 관계를 표현 알고리즘이란 컴퓨터로 문제를 풀기 위한 단계적 절차 프로그램 = 자료구조 + 알고리즘 알고리즘과 자료구조 간의 긴밀한 연결성 알고리즘의 조건 입력: 0개 이상의 입력이 존재하여야 한다. 출력: 1개 이상의 출력이 존재하여야 한다. 명백성: 각 명령어의 의미는 모호하지 않고 명확해야 한다. 유한성: 한정된 수의 단계 후에는 반드시 종료되어야 한다. 유효성: 각 명령어들은 실행 가능한 연산이어야 한다. 알고리즘의 기술 방법..
2-3-4트리는 red-black 트리의 쌍둥이 트리이다. 이 트리의 이름이 2-3-4트리인 이유는 자식노드의 개수에 따라 2,3,4개로 구분하기 때문이다. 2-3-4트리는 위와 같이 (1) 자식노드가 최소 2개, 최대 4개 이하이며, (2) 모든 리프노드는 마지막 레벨에 위치해야 하는 탐색트리로 정의된다 ** 단, 이진트리는 아니다 ** 2-노드, 3-노드, 4-노드로 구분 (자식 노드의 개수에 따라 구분) ** 리프 노드들은 원형 이중 연결 리스트에 의해 좌-우로 연결되어 있음 트리의 높이 - 최대 높이는 노드가 모두 자식을 2개씩 가지는 경우이고, 최소 높이는 자식을 4개씩 가지는 경우이다. 결국, 2-3-4 트리는 log4 n 이상, log2 n 이하의 높이를 갖게 되어 h = O(log n)이 ..
