본문 바로가기

분류 전체보기81

피보나치 수열의 다양한 구현방법 피보나치 수열이란, 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 말한다. 즉 f(t) = f(t-1) + f(t-2)를 만족시키며, 실제 수는 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 로 나아간다. 피보나치 수열은 재귀함수의 활용이나 동적 계획법을 연습하는 데 흔히 쓰인다. 다양한 풀이 방법을 통해 피보나치 수열을 구현하는 법을 알아보자 일반적인 재귀호출을 통한 구현 int Recursion_FIB(int n){ if (n 2023. 4. 3.
이진탐색트리와 AVL 트리 이진탐색트리 이진 탐색 트리는 다음과 같은 속성이 있는 이진 트리 자료 구조이다. 각 노드에 값이 있다. 값들은 전순서가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다. 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다. 즉, 이진 트리 구조로 되어있는데 자식의 왼쪽 값이 부모보다 작고 오른쪽 값이 부모보다 크면 이진탐색트리다. 이진탐색 트리를 순회 할 때는 중위 순회 방식(왼쪽-루트-오른쪽)을 쓴다. 이렇게 하면 이진탐색트리 내에 있는 모든 값들을 정렬 된 순서로 읽을 수 있다. 예시로, 다음의 이진탐색 트리를 중위 순회하면 1, 3, 5, 7, 8, 10으로 정렬된 .. 2023. 4. 3.
Heap과 Priority Queue Heap 우선순위 큐에 대해 알아보기 전에, 우선순위 큐를 위하여 만들어진 자료구조인 Heap에 대해 먼저 알아보자. heap의 특징은 다음과 같다. 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 힙의 종류에는 최소 힙과 최대 힙이 있는데, 최대 힙의 경우 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이고, 최소 힙의 경우 부모 노드의 키 값이 자식 노드의 키 값보다 작거.. 2023. 4. 3.
탐색 알고리즘 탐색 알고리즘이란 지정된 데이터들 중에 원하는 값을 찾는 알고리즘이다. 선형 탐색 알고리즘 (Linear Search Algorithm) 맨 앞이나 맨 뒤부터 순서대로 하나하나 원하는 값을 찾아보고, 원하는 값을 찾았을 때 탐색을 종료하는 탐색 방법이다. 4를 찾을 때 맨 왼쪽에 있는 1부터 시작해서 하나씩 탐색한다. 원하는 값이 리스트의 맨 마지막 원소거나, 없는 경우 n번의 탐색 과정을 거치므로 시간 복잡도는 O(N)이다. int arr[9] = { 3,1,5,7,2,4,9,6,8 }; int arr_size = sizeof(arr) / sizeof(int); int linearSearch(int target) { // 찾은 값의 index 반환, 없으면 -1 반환 int result = -1; fo.. 2023. 4. 1.
Hashing과 Hash Table Hashing Hashing이란 임의의 길이의 값을 해시 함수(Hash function)을 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다. 해시는 다양한 목적으로 사용될 수 있지만, 주로 다음과 같은 용도로 사용된다. 해시 테이블을 이용한 탐색 암호화 : 해시를 통해 변환된 데이터는 원본의 모습을 알아볼 수 없을 정도로 완전히 달라지므로, 이를 이용해 암호화라를 진행한다. SHA(Secure Hash Algorithm)알고리즘이 그 대표적인 예이다. 데이터 축약 : 해시는 길이가 서로 다른 입력 데이터에 대해 일정한 길이의 출력을 만들 수 있다. 이 특성을 이용하면 커다란 데이터를 '해시'하면 짧은 길이로 축약할 수 있다. 이렇게 축약된 데이터끼리 비교를 수행하면 커다란 원본 데이터들을 비교하는 .. 2023. 4. 1.
그래프와 탐색 그래프란 현실세계의 사물이나 개념 간의 연결 관계를 수학적 모델로 단순화하여 표현한 것을 말한다. 그래프는 정점(Vertex)과 그 사이를 잇는 간선(Edge)으로 이루어진다. G = (V, E) 그래프와 관련된 용어 정점, 노드 (Vertex, Node) : 데이터가 저장 된다. 간선 (Edge) 무향 간선 (Undirected Edge) : 방향이 존재하지 않는 간선, 양방향 유향 간선 (Directed Edge) : 방향이 존재하는 간선 인접 (Adjacent) : (정점 관점) 두 정점 A, B 사이에 간선이 존재한다면 A, B는 인접한다. 부속 (Incident) : (간선 관점) 두 정점 A, B 사이에 간선 e가 존재한다면 간선 e는 정점 A, B에 부속한다. 차수 (Degree) : 한 정.. 2023. 4. 1.

티스토리툴바