본문 바로가기

전체 글

 (51)
C언어) LinkedList, 연결리스트에 대해서 Linked List 연결리스트는 일반 배열과 다르게 동적으로 크기가 변할 수 있고, 삭제나 삽입 시에 데이터를 이동시킬 필요가 없는 자료구조입니다. 배열의 경우 중앙에 값을 추가/삭제할 때 그 뒤의 요소들을 전부 움직여야 하는데, 이때 깊은 복사가 일어나게 된다. 깊은 복사는 무거운 연산이기 때문에 시간이 오래 걸린다. 하지만 연결리스트에서 포인터값을 복사하며 이동하는 경우는 얕은 복사이기 때문에 이 차이점으로 인해 연결리스트의 추가, 삭제 연산은 배열보다 효율적이게 된다. 연결리스트 구현 구현 과정은 파이썬에서 구현하는 것과 크게 다르지 않습니다. typedef struct Node{ int data; struct Node* next; }node; 먼저 노드 구조체를 선언합니다. 노드의 Node*는 ..
C언어) 포인터와 주소 연산자 포인터란? C언어에서의 포인터는 메모리의 주소값을 저장하는 변수이며, 포인터 변수라고 부르기도 합니다. 변수가 데이터 값을 저장하는 것처럼 포인터 변수는 주소값을 저장합니다. 주소값 데이터의 주소값이란, 해당 데이터가 저장된 메모리의 시작 주소를 의미합니다. C언어에서는 이러한 주소값을 1바이트 크기의 메모리 공간으로 나누어 표현합니다. 예를 들어 int형 데이터는 4바이트의 크기를 갖지만, int형 데이터의 주소값은 시작 주소 1바이트만을 가리킵니다. 포인터 연산자 주소 연산자 & : 주소 연산자는 변수의 이름 앞에 사용하며, 해당 변수의 주소값을 반환합니다. '&' 기호는 앰퍼샌드(ampersand)라고 읽으며, 번지 연산자라고도 불립니다. 참조 연산자 * : 참조 연산자는 포인터의 이름이나 주소 앞..
LCS (Longest Common Subsequence) LCS란 Longest Common Subsequence의 줄임말로 최장 공통 부분수열을 뜻합니다. 최장 공통 부분수열은 공통 부분 문자열 중 가장 길이가 긴 문자열을 말합니다. 앞으로 알아볼 LCS 알고리즘은 LCS에 부합하는 문자열을 찾기 위한 알고리즘입니다. LCS는 최장 공통 부분수열만이 아니라 최장 공통 문자열(Longest Common Substring)을 말하기도 하는데, 두 알고리즘의 차이점을 알아보겠습니다. 아래 그림으로 알아보자면 ABCDEF 와 GBCDFE 두 문자열을 비교해보겠습니다. 왼쪽의 최장 공통 부분수열은 BCDF, BCDE 두 개의 결과를 얻을 수 있고, 오른쪽의 최장 공통 문자열은 BCD의 결과만 얻었습니다. 최장 공통 부분수열은 부분수열이기 때문에 문자와 문자를 건너뛰어..
최소 신장 트리란? 신장 트리(Spanning Tree) 먼저 신장 트리에 대해 설명하자면, 그래프 내의 모든 정점을 포함하는 트리 그래프의 최소 연결 부분 그래프 -> 최소 연결 = 간선의 수가 가장 적다. -> n개의 정점을 갖는 그래프의 최소 간선의 수는 n-1개이고, n-1개의 간선을 갖는 그래프 = 트리 형태 특징 하나의 그래프에 여러 개의 신장 트리가 존재할 수 있다. 모든 정점들이 연결되어 있어야 하고, 사이클을 포함해서는 안 된다. 최소 신장 트리란? (MST : 미니멈 스패닝 트리) : 각 간선의 가중치가 동일하지 않을 때, 간선의 가중치를 고려하여 최소 비용의 신장 트리를 선택하는 방법이다. 최소 신장 트리의 특징 n개의 정점에 대해 반드시 n-1개의 간선만을 이용해야 한다. 사이클을 포함하면 안 된다. ..
이진 탐색 알고리즘 이진 탐색(binary search)이란? 이진 탐색은 데이터가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘이다. 그렇기 때문에 이진 탐색 알고리즘을 사용하려면 배열의 데이터가 정렬되어 있어야 한다. 이진 탐색 알고리즘은 탐색을 반복할 때마다 검색 범위가 거의 절반으로 줄어들기 때문에 검색에 필요한 비교 횟수는 평균 O(log N)이다. 먼저, 배열의 인덱스를 가리키는 포인터를 왼쪽, 오른쪽, 중간값 세 개를 정의해줍니다. lenght = len(array) pl = 0 pc = (lenght - 1) // 2 pr = lenght - 1 pl - 왼쪽 포인터는 0 인덱스부터 pr - 오른쪽 포인터는 가장 뒤 인덱스부터 (lenght - 1) pc - 중간 포인터는..
B-Tree란? 먼저 이진트리는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조다. 이진트리의 종류로 정이진트리 : 트리의 모든 node가 0개 혹은 2개의 자식을 갖는 트리 포화이진트리 : leaf node가 끝까지 꽉 찬 트리 완전이진트리 : 마지막 레벨을 제외한 모든 레벨에서 순서대로 node가 채워진 트리 균형이진트리 : leaf node들의 레벨 차이가 최대 1레벨까지만 나는 트리 등이 있는데 오늘 얘기할 B-Tree는 균형이진트리에 속한다. 균형이진트리는 한 쪽으로 데이터가 쏠릴 수 있는 현실에서도 트리의 높이를 균형적으로 유지시켜줄 수 있어 많이 사용되는 자료구조이며, 검색할 때 최악의 시간복잡도가 O(log N)으로 굉장히 안정적이다. B-Tree B-Tree는 Balanced-tree로 이..
그래프(Graph)란? 그래프 : 데이터들의 관계를 여러 개의 노드(node)와 이들을 연결하는 간선(edge)으로 표현한 자료구조이다. 노드는 정점(vertex)이라고도 하며, 방향성 있는 간선을 arc라고 하기도 한다. 그래프는 대표적인 비선형 자료구조다. 비선형 자료구조는 선형 자료구조와 달리 데이터를 일렬로 구성하지 않고, 자료 순서나 관계가 복잡한 자료구조를 말한다. 데이터 요소를 계층적으로 저장, 표현해 분기점이나 사이클 등이 존재한다. 비선형 자료구조는 선형 자료구조보다 복잡하지만 다양한 문제를 해결할 때 활용할 수 있다. 다른 노드로 나가는 간선을 해당 노드(정점)의 outdegree(도, 길)라고 하며, 들어오는 간선을 indegree라고 한다. 그래프의 장점 복잡한 관계를 직관적으로 표현할 수 있다. 네트워크..
피보나치 수열(반복문, 재귀함수) 피보나치 수열이란? 1부터 시작하여 1,2 인덱스를 더하면 3인덱스의 답이되고, 2,3인덱스를 더하면 4 인덱스의 답이 되는 수열이다.. 1, 1, 2, 3, 5, 8 ........ 반복문을 이용하는 방법과 재귀 함수를 이용하는 두 가지 방법이 있다. 먼저 반복문을 이용하는 방법이다 # 반복문을 이용하는 방법 def fibonacci_for(n): list = [] if n

티스토리툴바