본문 바로가기
반응형

Algorithm/자료구조 이론10

Chapter 10. 힙(Heap) 대표적인 데이터 구조8: 힙 1. 힙 (Heap) 이란? 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, $ O(log n) $ 이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 2. 힙 (Heap) 구조 힙은 최대값을 구하기 위한 구조 (최대 힙, Max Heap) 와, 최소값을 구하기 위한 구조 (최소 힙, Min Heap) 로 분류할 수 있음 힙은 다.. 2020. 7. 20.
Chapter 09. 트리(Tree) 대표적인 데이터 구조7: 트리 1. 트리 (Tree) 구조 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 실제로 어디에 많이 사용되나? 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨 2. 알아둘 용어 Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node: 어떤 노드의 다음 레벨에 연결된 노드 Child Node: 어떤 노드의 상위 레벨에 연결된 노드 Leaf Node (Termina.. 2020. 7. 20.
Chapter 08. 해쉬 테이블(Hash Table) 대표적인 데이터 구조6: 해쉬 테이블 (Hash Table) 1. 해쉬 구조 Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조 Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법) 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨 2. 알아둘 용어 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수(Hashing.. 2020. 7. 20.
Chapter 07. 시간 복잡도 알고리즘 복잡도 표현 방법 1. 알고리즘 복잡도 계산이 필요한 이유 하나의 문제를 푸는 알고리즘은 다양할 수 있음 정수의 절대값 구하기 1, -1 ->> 1 방법1: 정수값을 제곱한 값에 다시 루트를 씌우기 방법2: 정수가 음수인지 확인해서, 음수일 때만, -1을 곱하기 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산함 2. 알고리즘 복잡도 계산 항목 시간 복잡도: 알고리즘 실행 속도 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈 가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 함 알고리즘 시간 복잡도의 주요 요소 반복문이 지배합니다. 생각해보기: 자동차로 서울에서 부산을 가기 위해, 다음과 같이 항목을 나누었을 때, 가장 총 시간에 영향을 많이 미칠 것.. 2020. 7. 20.
Chapter 06. 링크드 리스트(Linked List) 대표적인 데이터 구조: 링크드 리스트 (Linked List) 1. 링크드 리스트 (Linked List) 구조 연결 리스트라고도 함 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원 링크드 리스트 기본 구조와 용어 노드(Node): 데이터 저장 단위 (데이터값, 포인터) 로 구성 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 * 일반적인 링크드 리스트 형태 (출처: wikipedia, https://en.wikipedia.org/wiki/Linked\_l.. 2020. 7. 20.
Chapter 05. 스택(Stack) 꼭 알아둬야 할 자료 구조: 스택 (Stack) 데이터를 제한적으로 접근할 수 있는 구조 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 큐: FIFO 정책 스택: LIFO 정책 1. 스택 구조 스택은 LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따름 LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책 FILO: 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책 대표적인 스택의 활용 컴퓨터 내부의 프로세스 구조의 함수 동작 방식 주요 기능 push(): 데이터를 스택에 넣기 pop(): 데이터를 스택에서 꺼내기 Visualgo 사이트에서 시연.. 2020. 7. 20.
Chapter 04. 큐(Queue) 대표적인 데이터 구조: 큐 (Queue) 1. 큐 구조 줄을 서는 행위와 유사 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일 FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대 엑셀로 이해해보기 2. 알아둘 용어 Enqueue: 큐에 데이터를 넣는 기능 Dequeue: 큐에서 데이터를 꺼내는 기능 Visualgo 사이트에서 시연해보며 이해하기 (enqueue/dequeue만 클릭해보며): https://visualgo.net/en/list 3. 파이썬 queue 라이브러리 활용해서 큐 자료 구조 사용하기 * queue 라이브러리에는 다양한 큐.. 2020. 7. 17.
Chapter 03. 배열 꼭 알아둬야 할 자료 구조: 배열 (Array) 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조 * 인덱스(index): String처럼 연관된 데이터에 대해서 직접적으로 접근이 가능하도록, 번호를 할당. 이를 이용해서 연결된 배열의 개별 요소에 직접적으로 접근을 가능하도록 한다. 파이썬에서는 리스트 타입이 배열 기능을 제공함 1. 배열은 왜 필요할까? 같은 종류의 데이터를 효율적으로 관리하기 위해 사용 같은 종류의 데이터를 순차적으로 저장 장점: 빠른 접근 가능 (Index를 활용.) 첫 데이터의 위치에서 상대적인 위치로 데이터 접근(인덱스 번호로 접근) * 연관된 배열의 시작 주소를 알아야 한다. 단점: 데이터 추가/삭제의 어려움 미리 배열의 최대 길이를 지정해야 함. * 기존.. 2020. 7. 14.
Chapter 02. 자료구조와 알고리즘이란? 자료구조란? 용어: 자료구조, 데이터 구조, Date structure 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미 (Real world의 정보를 어떻게 데이터로 변환하여 구조를 만드느냐? = 자료구조) 코드상의 효율적으로 데이터를 처리하기 위해, 데이터 특성에 따라, 체계적으로 데이터를 구조화해야함. 어떤 데이터 구조를 사용하느냐에 따라, 코드 효율이 달라짐. 효율적으로 데이터를 관리하는 예. 우편번호: 5자리 우편번홀르 국가의 기초구역을 제공 5자리 우편번호에서 앞자리 3자리는 시, 군, 자치구를 표기, 뒤 2자리는 일련번호로 구성 지역에 대한 정보를 5자리의 숫자로 나타낸다. 학생 관리: 학년, 반, 번호를 학생에게 부여해서, 학생부를 관리 XX학년, X반, X번 학생 만약 위 .. 2020. 7. 10.
Chapter 01. 강의소개 및 학습 방법 목표 : 기본 자료구조/알고리즘 익히기. 알고리즘 풀이를 위해, 기본적으로 알고 있어야 하는 자료구조와 알고리즘 정리 짧은 시간 안에 효과적으로 익힐 수 있도록 구성 수업 전 꼭 알아둬야할 점 프로그래밍은 작은 원리를 적용하는 방법을 익히고, 연습을 통해 익숙해져야 함. 자료구조와 알고리즘은 프로그래밍 끝판왕! 프로그래밍 자체에 익숙하지 않다면, 수업을 듣기전에, 반드시 간단한 문제를 스스토 코드로 만들 수 있도록 해야함.(최소 구구단 정도) 최소 10줄의 코드는 스스로 작성할 수 있어야 함. 프로그래밍은 가능하지만, 파이썬이 익숙하지 않다면, 파이썬 기본 문법에 익숙해져아함. 참고. Python basic(문제 풀이) 2020. 7. 10.
728x90
반응형

티스토리툴바