다양한 정렬 알고리즘 간단한 정렬 알고리즘의 특징 O(n^2) 선택정렬 입력의 크기에 따라 자료 이동 횟수 결정 삽입 정렬: 레코드의 많은 이동이 필요. 대부분의 레코드가 이미 정렬되어 있는 경우 효율적 버블정렬: 가장 간단한 알고리즘(인접한 두 데이터를 비교하며 정렬) 효율적인 알고리즘들 셸 정렬: 삽입 정렬 개념을 개선한 방법 힙 정렬: 제자리 정렬로 구현하는 방법 병합 정렬: 연속적인 분할과 병합을 이용 퀵 정렬, 이중피벗 퀵 정렬: 피벗을 이용한 정렬 기수 정렬: 분배를 이용해 정렬: 키값에 제한이 있음 셸 정렬 기본 아이디어 삽입정렬은 어느정도 정렬된 리스트에서 매우 빠름 하지만 요소들이 이웃한 위치로만 이동 -> 많은 이동 발생 요소들이 멀리 떨어진 위치로 이동할 수있게 한다면 보다 적게 이동..
전체 글
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 __..
트리란? 계층적 자료의 표현에 적합한 자료 구조 차수: 뻗어나온 가지 루트노드 : 가장 위의 노드 (A) 형제노드: 같은 부모노드를 가진 노드 부모노드: 각 노드의 상위 노드 레벨(Level) : 각 노드가 뻗어나가는 깊이의 정도 서브트리 : 가지를 하나 끊어냈을 때 끊어진 노드들 자체로도 트리를 이룰 수 있음 노드가 하나여도 서브트리 가능 트리의 차수: 트리 중에서 가장 큰 차수 단말 노드(leaf node): 가장 끝에 있는 노드 비단말 노드: 리프노드를 제외한 모든 노드 조상노드 : 각 노드의 부모노드로 올라갔을 때 거치는 노드 자손노드: 해당 노드 아래로 뻗어나갈 때 거치는 모든 노드 트리의 높이: 층수의 개수(0부터 셀 때도 있고 1부터 셀 때도 있음) 일반 트리의 표현 방법 일반 트리의 노드 ..
정렬이란? 데이터를 순서대로 정렬하는 것 용어 레코드 : 정렬시켜야 될 대상 여러개의 필드로 이루어짐 정렬 키(sort key) 정렬의 기준이 되는 필드 레코드들을 키의 순서대로 재배열 정렬 알고리즘 종류 복잡도와 효율성에 따른 분류 단순하지만 비효율적: 삽입, 선택, 버블 정렬 등 복잡하지만 효율적: 퀵, 힙, 병합, 기수정렬, 팀 등 키값의 비교를 사용하지 않는 정렬: 기수, 카운팅 정렬 등 결과적으론 똑같지만 자료의 양 등에 따라 결정하면 됨 정렬 장소에 따른 분류 내부(internal) 정렬: 모든 데이터가 메인 메모리 외부(external) 정렬: 외부 기억장치에 대부분의 레코드 실제로 외부 자체에서 정렬되지 않지만 데이터가 무수히 많을 때 쪼개서 재배열 안정성 같은 데이터를 가졌음에도 정렬 시..
RISC와 CISC RISC(Reduced Instruction Set Computer) 마이크로프로세서를 설계하는 방법 중 하나로 CPU 명령어의 개수를 줄여 하드웨어 구조를 보다 간단하게 만드는 방식 전통적인 CISC CPU에서는 프로그래밍을 돕기 위한 많은 명령어와 주소 모드가 존재했는데 실제 쓰이는 명령어는 얼마 안됨 → 적은 수의 명령어만으로 구성한 명령어 집합으로 CPU의 성능을 높임 SPARC,MIPS등의 아키텍쳐에서 활용 장점 명령어가 적어 전력소비 적음 빠른 속도 단점 복잡한 연산을 수행하기 위해 명령어들을 반복 조합해서 사용 → 레지스터를 많이 필요로 함 복잡한 프로그램 CISC(Complex Instruction Set Computer) 마이크로프로그래밍을 통해 고급 언어에 각기 하나..
큐(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) 소스 파일의 맨 꼭대기 레벨(함수나 클래스 밖)에서 생성 프..