Algorithm

[알고리즘] 선택 정렬 (Selection Sort)

1. 선택 정렬 말 그대로 현재 위치에 들어갈 데이터를 찾아 선택하는 알고리즘이다. 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬'이기도 하다. 정확히는 데이터를 서로 교환하는 (swap)에서 임시 변수를 하나 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 본다. [장점] 1. 추가적인 메모리 소비가 작다. [단점]1. 시간복잡도가 O(N^2)이다. 2. 안정 정렬이 아니다. (불안정 정렬) 두 번째 단점인 안정 정렬이 아니라는 것에 대해 알아보자. [B1, B2, C, A] (A < B < C) 주의해서 볼 점은 B에 붙어있는 숫자는 임의로 붙인 숫자다. B1이 B2보다 크거나 작은..

[알고리즘] 버블 정렬(Bubble Sort)

1.버블 정렬 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘 [장점] 1. 추가적인 메모리 소비가 작다. 2. 구현이 매우 쉽다. 3. 안정정렬이 가능하다. [단점] 1. 다른 정렬 알고리즘에 비해 교환 과정이 많아 많은 시간을 소비한다. 자세히 보기 https://visualgo.net/en/sorting Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the only "payment" t..

[알고리즘] 자료구조: 트리(Tree)

1. 트리(Tree) 구조 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 실제로 어디에 많이 사용되는가? 트리 중 이진트리(Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨 2. 알아둘 용어 Node: 트리에서 데이터를 저장하는 기본 요소(데이터오 다른 연결된 노드에 대한 Branch 정보 포함) Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0 으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node: 어떤 노드의 다음 레벨에 연결된 노드 Child Node: 어떤 노드의 상위 레벨에 연결된 노드 Leaf Node(Terminal Node): Child Node가..

[알고리즘] 자료구조: 해쉬

1. 해쉬 테이블 키(Key)에 데이터(Value)를 매핑할 수 있는 데이터 구조 해쉬 함수를 통해, 배열에 키에 대한 데이터를 저장할 수 있는 주소(인덱스 번호)를 계산 Key를 통해 바로 데이터가 저장되어 있는 주조를 알 수 있으므로, 저장 및 탐색 속도가 획기적으로 빨라짐 미리 해쉬 함수가 생성할 수 있는 주소(인덱스 번호)에 대한 공간을 배열로 할당한 후, 키에 따른 데이터 저장 및 탐색 지원 2. 알아둘 용어 해쉬 함수(Hash Function): 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수 해쉬(Hash), 해쉬 값(Hash Value), 또는 해쉬 주소(Hash Address): 해쉬 함수를 통해 리턴된 고정된 길이의 값 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접..