알고리즘 (31) 썸네일형 리스트형 [알고리즘] 패스트캠퍼스 챌린지 15일차 어제까지 자료구조 이론 끝나고 오늘부터 알고리즘 이론 강의 시작!! 정렬 알고리즘 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 정렬은 프로그램 작성시 빈번하게 필요로 함 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수 => 다양한 정렬 알고리즘 이해를 통해, 동일한 문제에 대해 다양한 알고리즘이 고안될 수 있음을 이해하고, 각 알고리즘간 성능 비교를 통해, 알고리즘 성능 분석에 대해서도 이해할 수 있음 버블 정렬 알고리즘(Bubble Sort) 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘 [참고자료] https://visualgo.net/en/sorting VisuAlgo - Sorting (Bubble, Selecti.. [알고리즘] 패스트캠퍼스 챌린지 14일차 힙 구현 일반적으로 힙 구현시 배열 자료구조를 활용함 배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해, root 노드 인덱스 번호를 1로 지정하면, 구현이 좀더 수월함 부모 노드 인덱스 번호 (parent node's index) = 자식 노드 인덱스 번호 (child node's index) // 2 왼쪽 자식 노드 인덱스 번호 (left child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2 오른쪽 자식 노드 인덱스 번호 (right child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2 + 1 코드 참고해서 Swift로 구현해보고 테스트도 해봤다. 부모 노드 index = 자식 노.. [알고리즘] 패스트캠퍼스 챌린지 13일차 힙(Heap) 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, 𝑂(𝑙𝑜𝑔𝑛) 이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 Heap의 구조 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우) 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작음 완전 이진 트리 형태를 가짐(완전 이진 트리.. [알고리즘] 패스트캠퍼스 챌린지 12일차 어제까지 트리를 구성하고, 트리에 데이터 넣기, 그리고 특정 데이터가 트리에 들어있는지 검색하는 것 까지 구성했다. 오늘은 숫자들로 트리를 구성하고, 트리에 데이터들이 다 있는지 체크하는 것을 해봄 어제까지 작성했던 코드들은 생략하고, 테스트 코드만 넣었다. // pick 100 random numbers in 1 to 1000 var numbers: [Int] = [] for i in 1...100 { numbers.append(Int.random(in: 1...1000)) } // make tree with numbers // root node = 500 let headNode = Node(500) let tree = BinarySearchTree(headNode) for number in numbe.. [알고리즘] 패스트캠퍼스 챌린지 11일차 그럼 이제 어제 만들어놓은 트리와 트리에 값 insert 하는 함수 만든 것에 이어서 특정 값 탐색하는 것 해보자...! 탐색 // search value from the tree func search(value: T) -> Bool { self.node = self.head while self.node != nil { if self.node?.value == value { // find!! return true } else if value < self.node!.value! { // go left self.node = self.node?.left } else { // go right self.node = self.node?.right } } // value is not in the tree. retur.. [알고리즘] 패스트캠퍼스 챌린지 10일차 트리(Tree) 구조 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 실제로 어디에 많이 사용되나? 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨 알아둘 용어들 Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node: 어떤 노드의 다음 레벨에 연결된 노드 Child Node: 어떤 노드의 상위 레벨에 연결된 노드 Leaf Node (Terminal Node): Child Node가 하나.. [알고리즘] 패스트캠퍼스 챌린지 09일차 해쉬테이블 충돌 해결 알고리즘 [Chaining 기법] 개방 해슁 또는 Open Hashing 기법 중 하나 해쉬 테이블 저장공간 외의 공간을 활용하는 기법 충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법 [Linear Probing 기법] 폐쇄 해슁 또는 Close Hashing 기법 중 하나 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법 저장공간 활용도를 높이기 위한 기법 빈번한 충돌을 개선하는 방법 해쉬 함수을 재정의 및 해쉬 테이블 저장공간을 확대 ex. 이전 예제에서 hash Func = key % 8 으.. [알고리즘] 패스트캠퍼스 챌린지 08일차 해쉬 테이블(Hash Table) 키(Key)에 데이터(Value)를 저장하는 데이터 구조 Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법) 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨 용어 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address): Key를 해싱 함수로 연산해.. 이전 1 2 3 4 다음
