컴퓨터공학기초 개념/알고리즘 개념38 Algorithm - 버블 정렬(Bubble Sort) 0. 알고리즘 연습 방법 - 연습장과 펜을 준비한다. - 알고리즘 문제를 읽고 분석 후 문제를 풀기 위한 순서를 생각한다. - 각 순서 또는 절차마다 구현할 알고리즘을 나누고 세부 항목을 나누어 적어본다. - 코드로 구현하기 위해 필요한 데이터 구조 또는 사용할 변수를 정리한다. - 각 문장을 코드 레벨로 적는다. - 코드의 흐름을 데이터 구조 또는 사용할 변수를 이용해 손으로 직접 적으면서 작동한다. 즉, 코드에 필요한 모든 순서/절차/흐름을 연습장에서 정리를 한 후 코드로 옮기기만 하는 것이다. 1. 정렬(Sort) 이란? - 데이터를 순서대로 나열하는 것 또는 어떤 규칙이나 기준을 기반으로 나열하는 것 a) 정렬을 알아야 하는 이유 - 정렬은 프로그램 작성 시 빈번하게 사용되는 가장 기본적인 알고리.. 2020. 9. 9. Data Structure - 개념 정리(summary) - 이전 포스팅까지 기본적인 자료구조를 공부했습니다. 이를 기반으로, 알고리즘을 공부해 나갈 계획입니다. - 이번 포스팅은 복습 겸 앞선 포스팅에서 다뤘던 기본적인 자료구조에 대한 개념을 정리하는 포스팅입니다. 1. 자료구조와 알고리즘이란? - 자료구조(data structure): 대량의 데이터를 효율적으로 관리하기 위해 사용하는 데이터의 저장방식을 의미한다. 저장할 데이터의 특성과 데이터 사용의 목적에 따라 해당 데이터를 저장하는 방식이 달라진다. - 알고리즘(algorithm): 프로그래밍에서 어떠한 문제를 해결하거나 풀어내기 위한 방법 또는 과정을 의미한다. 수학처럼, 한가지 문제에도 다양한 알고리즘이 존재한다. 다만, 좋은 알고리즘이란 프로그래밍 상에서 가장 적은 자원(저장공간, 메모리)을 사용.. 2020. 9. 8. Data Structure - Heap(2) 1. Heap 구현 - 데이터 삭제(pop) - Heap은 최대값(max heap) 또는 최소값(min heap)만을 삭제한다. 그렇기에 root노드만을 삭제하면 된다. - root노드의 삭제는 root노드를 꺼내었을 때 발생하며, 이 동작을 pop이라고 명시한다. def pop(self): # heap에 데이터가 없는 경우 if len(self.heap_array) = len(self.heap_array): #배열의 길이보다 긴값 = 없는값 return False # 재정렬 2번 조건 - 좌측 자식노드만 존재(우측 자식노드는 없음) elif right_child >= len(self.heap_array): # 좌측 자식노드와 값을 비교하여 자식노드 값이 큰 경우 if self.heap_array[pop.. 2020. 9. 3. Data Structure - Heap(1) 1. Heap이란? - Heap은 트리구조를 기반으로한 자료구조로 데이터에서 최대값과 최소값을 빠르게 찾기위해 고안된 완전 이진트리(Complete Binary Tree)이다. * 완전이진트리란? → 트리에 데이터가 삽입될 때, 왼쪽에 위치한 자식노드를 먼저 채우는 규칙을 갖고 있는 이진트리이다. 이진트리이기 때문에 자식노드는 2개만 가질 수 있다. 1) Heap을 사용하는 이유 - 우선순위 큐와 같이 최대값과 최소값을 빠르게 찾기위해 사용한다. - 이를 배열로 구현하면 최대값과 최소값을 찾는데 O(n)만큼 걸린다. - 반면에, heap을 이용하여 최대값과 최소값을 찾으면 O(log n)만큼 걸린다. (더 빠르다) 2) Heap의 구조 - Heap은 최대/최소 값을 구하기 위한 구조인 최대 힙(Max H.. 2020. 8. 31. Data Structure - 트리(Tree) & 이진탐색트리(Binary Search Tree) 1. 트리(Tree) - 트리는 node와 branch를 이용하여 구성된 데이터구조로 사이클이 없다. - 트리는 이진트리(Binary Tree)형태의 구조를 이용하여 탐색(검색) 알고리즘 구현에 많이 사용된다. * 이진트리 - 하나의 node에서 뻗어나가는 branch의 수가 최대 2개인 트리구조 [알아야 할 용어] - Node: 트리에서 데이터를 저장하는 기본 요소(데이터와 연결되어 있는 다른 노드에 대한 branch정보가 담겨있다.) - Root Node: 트리 맨 위의 노드 - Level: 최상위 노드인 root node를 level 0으로 하였을 때, branch로 연결된 하위 노드의 깊이를 나타낸다. - Parent Node: 부모 노드를 의미하며 어떤 node에 연결된 상위 node를 의미한다.. 2020. 8. 26. Data Structure - Hash Table (2) 1. Linear Probing 기법 - Close Hashing(폐쇄 해싱) 기법 중 하나로, 해싱충돌이 발생하면 Hash Table의 저장공간 안에서 충돌을 해결하는 기법이다. - 다시 말해, 충돌이 발생하면 Hash address를 이용하여 Hash Table의 빈공간을 찾아 저장하는 기법이다. - 이 기법을 사용하면 Hash Table의 저장공간 활용도를 높일 수 있다. 2. Linear Probing 기법 구현하기 [기본 구조] 시나리오1) 새로 추가하려는 데이터의 hash값에 이미 다른 데이터가 저장되어 있는 경우, hash table을 검색하여 가장 첫번째로 찾는 빈 공간에 데이터를 저장하는 방식이다. hash값 value 0 a 1 - 위의 표를 기반으로 설명합니다. 만약에 hash값이 0.. 2020. 8. 22. Data Structure - Hash Table (1) 1. 해쉬 테이블(Hash Table) Hash Table은 Key와 Value 한 쌍으로 저장하는 데이터 구조를 갖고 있다. Key를 이용하여 원하는 data(value)를 바로 찾을 수 있기에 검색속도가 빠르다는 장점이 있다. 파이썬의 Dictionary가 해쉬 테이블이고 그렇기에 파이썬에서는 별도로 해쉬테이블을 구현할 필요가 없다. ex) dic = {"name":"Raphael", "job":"developer"} [알아야 하는 용어] 해쉬(Hash): 임의 값을 고정된 길이로 변환하는 것 해쉬 테이블(Hash Table): 키 값에 대응하는 value를 갖고 있는 저장공간으로, 키 값을 기반으로 해시함수를 통해 직접 접근이 가능한 데이터 구조 해시 함수(Hash/Hashing Function):.. 2020. 8. 22. Data Structure - 시간 복잡도(Time Complexity) 1. 시간 복잡도 - 어떤 문제를 해결하는데에 있어 어떤 알고리즘이 가장 빠른지 판단하기 위해 알고리즘의 효율성을 수치적으로 계산한 것이다. - 알고리즘의 효율성을 측정하기 위해서 알고리즘이 복잡한 정도를 계산하는데 여기에는 시간과 공간, 2가지가 있다. 시간 복잡도 - 알고리즘의 실행 속도 공간 복잡도 - 알고리즘이 사용하는 메모리의 양/사이즈 * 현업에서 주로 사용하는 것은 시간복잡도이다. 시간복잡도에 대하여 자세히 알아보자. c) 시간 복잡도의 핵심 요소 - 반복문 - 알고리즘 구조에서 어느 부분에서 가장 시간을 많이 소요하는지를 파악하는 것이 핵심이다. - 입력의 크기가 커질수록 반복문의 수행시간이 증가하게 되며, 이는 곧 알고리즘의 수행시간을 증가시킨다. d) 시간복잡도의 표기법 종류 Big O.. 2020. 8. 21. Data Structure - Linked List (2) 1. Linked List - 특정 노드 삭제 - 특정 노드를 삭제하는 경우는 3가지가 있다(첫노드, 중간노드, 마지막노드). 이를 배워보기 전에 베이스로 이용할 연결리스트를 코드로 작성한다. - 위의 코드를 기반으로 3가지 노드 삭제 경우를 처리하기 위한 delete메소드를 작성한다. a) head 노드 삭제 b) 마지막 노드 삭제 & 중간 노드 삭제 2. 다양한 Linked List 구조 - Double Linked List - 연결리스트의 단점은 대용량 자료검색이 힘들다는 점이다. 그 이유는 노드마다 다음 노드의 주소값을 갖고 있기 때문에 1만개의 노드 중 가장 8000번째 노드를 찾는다면 0부터 7999번까지 모든 자료를 보아야 한다. 이런 단점을 해결하기 위해 연결리스트는 다양한 구조로 구현한다.. 2020. 8. 20. 이전 1 2 3 4 5 다음
