자료구조, 알고리즘

[알고리즘] Kruskal 알고리즘

프로그래머스에서 섬 연결하기 문제를 Kruskal 알고리즘으로 풀면서 공부한 것을 정리한 내용이다! 최소 신장 트리 (Minimum Spanning Tree)란? 먼저 Kruskal 알고리즘을 이해하기 전에 최소신장트리(MST)를 알아야 한다. MST란 간선에 가중치가 있을 때, 모든 정점을 방문하면서 비용을 최소로하는 트리를 의미한다. 이때 그래프에 사이클이 포함되면 안된다. 위 그림을 보면 가중치가 포함된 그래프가 주어질 때, 오른쪽 그림의 간선을 연결함으로써 최소 비용으로 모든 노드를 방문할 수 있는 트리가 만들어지게 된다. 최소신장트리를 구현하는 알고리즘에는 대표적 Kruskal과 Prim 알고리즘이 있다. 오늘은 Kruskal 알고리즘에 대해서만 알아보자. Kruskal 알고리즘이란? Krusk..

[알고리즘] CodeForce 해시 알고리즘 구현 (Python)

저번에 Python에서 set 과 list의 시간복잡도를 비교하는 글을 쓴 적이 있다. list를 사용하는 경우 in 연산을 할 때 O(n)시간이 걸리는 반면, set은해시테이블을 기반으로 구현되기 때문에 O(1)의 시간만에 값을 찾을 수 있다는 내용이었다. https://jjung0326.tistory.com/66 [Python] Set과 List의 시간 복잡도 차이 코딩테스트 공부를 하는데, List를 사용하면 시간 초과가 나왔던 문제가 Set을 사용하자 통과가 됐었다. 관련 포스팅: https://jjung0326.tistory.com/65 [Python] 백준 1987번 - 알파벳 문제: https://www.acmicpc.net/p jjung0326.tistory.com 이때 사용되는 해시 알고..

[자료구조] 큐 (Queue)

07. 큐 (Queue) 07-1. 큐의 이해와 ADT 정의 큐(Queue)는 선입선출 방식의 자료구조이다. FIFO(First-In, First-Out) 구조라고도 불린다. 따라서 스택과 달리 데이터를 넣을 땐 앞에서 넣고, 뺄 땐 뒤에서 빼는 구조이다. 큐도 스택처럼 배열을 기반으로, 연결 리스트를 기반으로 모두 작성 가능하다. 큐 자료구조의 ADT는 다음과 같다. void QueueInit(Queue * pq); - 큐의 초기화를 진행한다. - 큐 생성 후 제일 먼저 호출되어야 하는 함수이다. int QIsEmpty(Queue * pq); - 큐가 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다. void Enqueue(Queue * pq, Data data); - 큐에 데이..

[자료구조] 스택 (Stack)

06. 스택 (Stack) 06-1. 스택의 이해와 ADT 정의 스택(Stack)은 후입선출 방식의 자료구조이다. LIFO(Last-In, First-Out)구조라고도 불린다. 예시로 스택은 한쪽은 막히고 한쪽은 뚫려있는 초코볼 통에 비유할 수 있다. 먼저 들어간 것이 나중에 나오는 구조이다. 이러한 스택은 선형자료구조의 일종이다. 이에 따라 스택은 배열을 이용해서도 구현이 가능하고, 연결 리스트를 이용해서도 구현이 가능하다. 스택의 대표적인 기능인 넣고, 꺼내고, 들여다 보는 연산을 각각 push, pop, peek이라 한다. 이러한 연산을 바탕으로 ADT를 정의할 수 있다. 스택의 ADT는 리스트 자료구조에 비해 상대적으로 정형화 된 편이다. void StackInit(Stack * pstack); ..

[자료구조] 원형 연결 리스트 (Circular Linked List)

05. 연결 리스트 (Linked List) 05-1. 원형 연결 리스트 (Circular Linked List) 원형 연결 리스트는 연결 리스트에서 마지막 노드가 첫 번째 노드를 가리키게 한 것이다. (연결의 형태가 원을 이룸) 원형 연결 리스트는 머리와 꼬리의 구분이 없다고도 한다. 원형 연결의 장점은 머리와 꼬리를 가리키는 포인터 변수를 각각 두지않고 꼬리 변수 포인터만 있어도 머리 또는 꼬리에 노드를 간단히 추가 할 수 있다는 점이다. (꼬리의 next가 머리를 가리키기 때문) 노드를 꼬리에 추가했을 때와 머리에 추가했을 때의 유일한 차이점은 tail이 가리키는 노드가 다르다는 점이다. (노드의 순서는 결국 같다) 이에 따라 원형 연결 리스트에서 LNext함수를 실행하면 무한 반복 호출이 가능하다..

[자료구조] 연결 리스트(Linked List)

04. 연결 리스트 (Linked List) 04-1. 연결 리스트의 개념적인 이해 앞서 공부한 배열리스트는 메모리의 길이를 변경하는 것이 불가능했다. 따라서 필요로하는 메모리의 크기에 유연하게 대처하기 위해 '동적인 메모리 구성'이 필요하다. 연결 리스트는 필요할 때마다 구조체 변수를 하나씩 동적 할당해서 이들을 연결한다. 위의 사진처럼 노드는 '데이터를 저장할 장소'(Data)와 '다른 변수를 가리키기 위한 장소'(Next)로 나뉘어 있다. 연결 리스트는 손으로 구조를 그려가며 공부하는 것을 추천한다. 연결 리스트에서는 데이터를 삭제할 때 다음과 같이 삭제 포인터를 두개 만든다. Node * delNode = head; Node * delNextNode = head->next; 이유는 delNode의..

[자료구조] 배열 리스트 (Array List)

03. 배열 리스트 (Array List) 03-1. 추상 자료형 : Abstract Data Type '구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것'을 가리켜 추상자료형(ADT)라 한다. 예를들어 지갑에 동전을 넣고 빼는 과정을 자세히 설명하면 다음과 같다. 지갑을 들어 지퍼를 열고 동전을 안에 넣고 지퍼를 다시 닫는다. 지갑을 들어 지퍼를 열고 동전을 집고 동전을 빼고 지퍼를 다시 닫는다. 이를 추상자료형으로 나타내면 다음과 같이 나타낼 수 있다. 동전의 삽입 / 동전의 추출 03-2. 배열을 이용한 리스트의 구현 리스트 자료구조는 구현방법에 따라 크게 두가지로 나뉜다. 순차 리스트 : 배열을 기반으로 구현된 리스트 연결 리스트 : 메모리의 동적 할당을 기반으로 구..

[자료구조] 재귀(Recursion)

02. 재귀(Recursion) 02-1. 함수의 재귀적 호출의 이해 재귀 함수의 흐름은 재귀함수가 복사되는 것이라고 이해하면 쉽다. "Recursive 함수를 실행하는 중간에 다시 Recursive 함수가 호출되면, Recursive 함수의 복사본을 하나 더 만들어서 복사본을 실행하게 됩니다." - 팩토리얼(Factorial) $n!$을 계산하는 식은 $(n-1)$항에 대한 일반항으로 나타낼 수 있으므로 재귀함수를 활용하여 나타낼 수 있다. #include int Factorial(int n){ if(n==0) return 1; else return n*Factorial(n-1); } int main(void){ printf("5! = %d \n", Factorial(5)); } 02-2. 재귀의 활용..