기타/자료구조 & 알고리즘

양방향 연결 리스트란? 데이터를 가지고 있는 노드가 이전 노드와 다음 노드의 주소를 가지고 있는 리스트이다. 양방향 연결리스트의 특징 단방향 연결리스트는 이전 노드로 돌아가려면 저장을 해둬야했던 반면에, 양방향은 자유롭게 노드 이동이 가능하다. 그 대신에 이전 노드를 저장하는 변수가 하나 더 추가된다. 상황에 따라 사용하면 된다. 탐색이 빠르다고 하는 게시글도 몇몇 있는데, 정렬된 리스트가 아니면 의미 없기에 특징으로 적지 않겠다. 양방향 연결리스트 구현 (그림 설명) 2021/01/15 - [프로그래밍/자료구조 & 알고리즘] - 연결 리스트 (Linked List) 연결 리스트 (Linked List) 연결 리스트(Linked List)란? 데이터를 가지고 있는 노드가 다음 노드의 주소를 가지고 있는 ..

연결 리스트(Linked List)란? 데이터를 가지고 있는 노드가 다음 노드의 주소를 가지고 있는 리스트이다. 연결 리스트의 특징 메모리만 여유있다면, 크기 제한이 없다. 자료의 추가, 삭제가 O(1)에 가능하다. 자료의 탐색이 O(n)으로 느리다. But, 자료를 (추가, 삭제)하기 전에도 탐색을 한번 거쳐야 하기 때문에, (추가, 삭제)가 빠른 것을 장점이라고 말하기 어렵다. 연결 리스트 구현 (그림 설명) 자료를 쉽게 다루기 위해, Node 클래스 하나를 더미로 만들어 리스트의 시작 노드로 설정한다. 1. 데이터 추가 (맨 뒤에 삽입할 때) 받은 데이터로 노드를 하나 생성하고, 노드를 연결해준다. (리스트의 중앙에 삽입할 때) 마찬가지로 노드를 하나 생성하고, 위치를 찾아서 연결해준다. 순서 주의..

퀵 정렬(Quick Sort)란? 한 데이터를 골라 Pivot으로 설정하고, Pivot보다 작은 값은 왼쪽으로 넘기고 큰 값은 오른쪽으로 넘기면서 정렬하는 방식이다. 퀵 정렬의 특징 시간복잡도 최악 O(n^2), 평균 O(n log n) 분할정복 알고리즘이다. 평균적으로 매우 빠른 속도로 수행된다. 퀵 정렬 원리 1. 전체 배열을 대상으로 함수를 호출한다. 2. 가장 오른쪽 값을 Pivot으로 잡는다. (Pivot을 랜덤으로 잡으면 랜덤 퀵소트다.) 3. Pivot보다 작은 값들을 다 왼쪽으로 넘긴다. 3. Pivot이 들어갈 위치에 있는 값과 가장 오른쪽 값을 swap한다. 4. Pivot을 제외하고, 왼쪽과 오른쪽 배열을 계속 재귀함수 부른다. 퀵 소트 구현 (C++) #include #include..

합병 정렬(Merge Sort)란? 데이터들을 최소 단위로 쪼개고, 합치면서 정렬하는 방식이다. 합병 정렬의 특징 시간복잡도 O(nlog₂n) 분할정복 알고리즘이다. 배열을 분리한 뒤, 합칠 때 새로운 배열이 필요하다. 합병 정렬 원리 원래의 배열을 하나의 데이터를 가지는 배열로 쪼갠 뒤, 합치면서 정렬한다. 아래 그림은 합치면서 정렬하는 과정이다. 1. 정렬할 데이터를 담을 배열을 만든다. (변수명은 mergeArr로 했음) 1. 왼쪽 배열과 오른쪽 배열을 비교하면서 mergeArr에 추가한다. 2. 하나의 배열이 끝이나면, 다른 배열에 남은 값들을 mergeArr에 추가한다. 3. 정렬된 배열(mergeArr)을 원래의 배열에 복사한다. 합병 정렬 구현 (C++) #include #include vo..

버블 정렬(Bubble Sort)란? 인접한 2개의 데이터를 비교하며 정렬하는 방식이다. 데이터를 비교하는 방식이 버블과 비슷하다고 해서 지어진 이름이라고 한다. 버블 정렬의 특징 시간복잡도 O(n^2) 구현이 간단해서 테스트용으로 정렬할 때 주로 사용한다. 버블 정렬 원리 임의의 숫자 배열을 만들고, 오름차순으로 정렬하는 과정을 PPT로 만들어보았다. 위 과정을 한번 반복하게 되면, 맨 끝에 확정된 숫자가 생긴다. 그 다음은 확정된 숫자를 제외한 나머지 숫자들로 위 과정을 반복한다. 위 그림에 나타나 있는 과정을 반복해서 인덱스로 나타내보면, (0,1) (1,2) (2,3) (3,4) (4,5) (5,6) (6,7) (7,8)> 8번 인덱스 값 확정 (0,1) (1,2) (2,3) (3,4) (4,5)..

ArrayList (배열 리스트) 배열을 이용한 리스트이다. ArrayList 의 장점 - 인덱스가 있어서 정렬이 되어있을 때, 이진탐색을 이용한 탐색이 쉽다. ArrayList 의 단점 - 컴파일 시 배열의 크기를 정해주어야 한다. - 삽입 및 삭제 시 배열을 하나씩 당겨주거나, 하나씩 밀어주어야 한다. 데이터 양이 많지만 삽입/삭제가 거의 없고, 데이터의 접근이 빈번히 이뤄질 때 유리하다. LinkedList (연결 리스트) 데이터를 담을 공간과 다음 데이터를 가르키는 포인터 하나가 구조체를 이룬다. LinkedList 의 장점 - 논리적 공간의 제약이 없다. - 삽입 및 삭제 시, 시간복잡도가 O(1)이다. LinkedList 의 단점 - 탐색 시, 시간복잡도가 O(n)이다. 삽입/삭제가 빈번히 이..

재귀를 이용해 C언어로 피보나치 수열을 구현 피보나치 수열 규칙 1. 처음 2개의 숫자는 1이다. 2. 3번째 값부터는 앞의 두 수를 더한 값이다. // 피보나치 수열 int fibo(int n) { if(n

함수의 재귀적 호출을 이용하여 c언어로 하노이 타워를 구현 하노이 탑 규칙 1. 가장 위의 원판만 이동 가능함 2. 작은 원판 위로 큰 원판이 올라갈 수 없음 3. 최소 이동횟수로 이동해야함 4. 한번에 하나의 원판만 이동해야 함 제일 밑의 원판을 옮기기 위해 위의 원판들을 B로 옮긴다 (A->B) -> hanoi(n-1,a,c,b); 제일 밑의 원판을 A에서 C로 옮겨야 한다. (A->C) -> printf("%d 원반이 %c -> %c\n",n,a,c); 제일 밑의 원판을 C로 옮겼으므로 B에 있던 원판들을 다시 A로 옮긴다 (B->C)/p> -> hanoi(n-1,b,a,c); // 하노이 타워 void hanoi(int n, char a, char b, char c) { if(n==0) { ret..