728x90 Computer Science/Data Structure5 [자료구조] 이진탐색트리 (Binary Search Tree) ■ 이진 탐색 (Binary Search) 우리가 보통 벡터나 연결리스트를 활용하여 원하는 요소가 있는지 찾기 위해 순회를 할 경우 O(n)의 시간 복잡도를 갖고 전체를 둘러봐야한다. 하지만 정렬이 되어있는 상태라면 이렇게 할 필요 없이 이진 탐색을 해주면 된다. 이진 탐색이란 중간 요소를 기점으로 탐색할 값이 해당 요소보다 클 경우 우측을, 작을 경우 좌측을 탐색해주는 것인데 이를 찾을 때까지 [or 탐색 대상이 하나로 줄어들 때까지] 무한 반복 해주는 것이다. 반씩 쪼개서 탐색하므로 O(logN)의 시간 복잡도를 갖고 있으며 이는 일반적으로 전체를 순회하는 O(n)보다 좋은 성능을 의미한다. ■ 이진 탐색 트리 (BST; Binary Search Tree) [이론] 이진탐색트리는 이진트리의 구조를 띄.. 2024. 3. 29. [자료구조] 그래프 (Graph) ■ 의의 현실 세계의 사물이나 추상적인 개념 간의 '연결 관계'를 표현 트리와 굉장히 유사한데 트리보다 약간 넓은 개념으로 보면 됨. 트리가 약간 그래프의 일종이라고 보는게 좀 더 정확할듯. ■ 구성 (1) 정점 (Vertex) : 데이터를 표현 (사물, 개념 등) (2) 간선 (Edge) : 정점들을 연결하는데 사용 [사용 예시] 1. 소셜 네트워크 관계도 2. 지하철 노선도 3. 최적 길 판단 4. 다수 간의 호감도 등 ■ 종류 (1) 가중치 그래프 (Weighted Graph) 정점과 정점 사이를 잇는 간선에 가중치(비용)가 주어진 그래프를 뜻한다. (2) 방향 그래프 (Directed Graph) 정점과 정점 사이를 잇는 간선에 방향이 주어진 그래프를 뜻한다. ■ 표현 방법 (1) 인접 리스트 :.. 2024. 3. 25. [자료구조] 우선 순위 큐 (Priority Queue) ■ 이론 우선 순위 큐는 힙 트리(Heap Tree)의 구조를 갖는다. 최적 조건에 해당하는 값을 한 번에 구하고 싶을 때 유용한 자료구조이다. 연결리스트나 벡터 같은 경우 최대값 최소값을 찾으려면 O(n)만큼 선회하며 모든 값을 비교해줘야 도출할 수 있다. 하지만 우선순위큐는 힙트리의 구조로인하여 완전이진트리의 형태를 띄고 있다. 데이터를 삭제 및 추가하는 과정에서 대소관계를 비교하며 노드를 이동시키는 연산이 트리의 높이(logN)만큼 발생하므로 O(logN) 정도의 시간복잡도로 수행된다. [힙트리 설명 및 힙 정렬 알고리즘은 아래 포스팅에서 이전에 C#으로 구현해봤었다.] https://yjhdevelopdiary.tistory.com/172 [Alogrithm] 히프, 기수, 계수 정렬, 알고리즘 .. 2024. 3. 25. [자료구조] 순환적, 반복적 피보나치 수열 구현 및 성능 비교, 순환문과 반복문 비교, 하노이탑 ■ 구현 ■ Main ■ 성능 비교 이로 인하여 피보나치 수열은 Iterative 기법이 더욱 효과적인 것을 알 수 있었다. ■ 순환 (Recursive) vs 반복 (Iterative) 순환 (Recursive) 반복 (Iterative) [장점] 가독성 증대 및 코딩도 간단해짐 [단점] 함수 호출의 오버헤드 발생으로 수행속도가 느림 (스택 저장 공간에 함수 파라미터 스택을 저장할 기억 공간이 더필요하고 이와 관련된 작업을 함에 있어서 오버헤드가 발생함) [특징] 1. 어떤 경우는 순환이 아니면 프로그램 구현이 어려운 경우가 있음 2. 시간 복잡도 (Time Complexity)는 순환 호출 1번에 1번의 곱셈을 수행하므로 n번 발생시 O(n)이다. [장점] 수행속도가 빠름 [단점] 가독성을 악화시킬 .. 2024. 2. 3. [자료구조] 자료구조의 이해와 자료 표현 (수치 및 진수) ■ 정의 자료구조란 계산에 쓰이는 여러가지 자료들을 조직화 및 구조화(organize)한 것을 의미한다. ■ 일상생활과의 비교 일상생활 자료구조 물건을 쌓아두는 것 스택 (LIFO; Last In First Out) 영화관 매표소의 줄 큐 (FIFO; First In First Out) 할 일 리스트 리스트 영어 사전 (알파벳 순서) 사전, 탐색구조 지도 그래프 조직도 트리 ■ SW코딩 [의미] 대부분의 SW코딩은 자료(data)를 처리하며, 이 자료들은 자료구조(data structure)를 사용하여 표현되고 저장된다. 이는 여러 가지 측면으로 SW코딩이 무엇인지를 나타낼 수 있다. 측면 정의 이론적 그래프이론, 집합이론, 조합적 분석의 이산수학과 확률이론을 기초로 알고리즘을 분석하여 검색, 정렬방법을.. 2024. 1. 21. 이전 1 다음 728x90
