Computer Science/Data structure & Algorithm
DP의 대표 문제 중 하나인 LCS에 대해 다루어 보겠다. Longest Common Substring 공통 부분 문자열을 찾으라고 했을 때 우리는 보통 longest common substring을 생각하곤 한다. 이는 오늘 알아볼 LCS와는 다른 개념이니 혼동해서는 안된다. Longest Common Substring은 말 그대로 공통으로 가지고 있는 substring 중 가장 긴 것을 구한다. 이 문제는 DP로 해결할 수 있으며 굉장히 간단하게 구현이 가능하다. 두 문자가 같다면 [j-1][i-1]의 값에 +1을 하는 방식으로 위의 표를 채워나가면 된다. Longest Common Subsequence 1. 기본 개념 그럼 Common Subsequence는 무엇일까? 부분 수열 중 가장 긴 것이라..
오늘은 Optimal Binary Search Tree ( 최적 이진 탐색 트리 ) 에 대해 정리해보았다. Binary Search Tree Binary Search Tree는 Binary Tree의 성질을 만족하면서 Ordered 되어 있는 상태이다. BST의 성질은 다음과 같다. 왼쪽 자식 노드는 부모 자식의 값보다 작다. 오른쪽 자식 노드는 부모 자식의 값보다 크다. BST는 탐색시간을 줄여준다는 것에서 굉장히 큰 의미가 있다. Optimal BST (최적 이진 탐색 트리) 1. 기본 개념 오늘 할 Optimal BST는 BST 중 평균 탐색 시간이 가장 작은 Tree를 의미한다. 여기서 '평균 탐색시간'이란 무엇일까? 이때까지 우리는 노드를 탐색할 확률이 같다고 가정하고 Tree를 만들었다. (r..
https://mobuk.tistory.com/21 [자료구조] C - 스택(Stack) 오늘은 컴퓨터에서 정말 많이 사용되는 자료구조인 스택에 대해 알아 볼 것이다. 스택(Stack) 스택을 사전에서 찾아보면 더미, 낟가리 를 의미한다고 되어 있다. 스택은 말 그대로 자료들이 더미 mobuk.tistory.com 지난시간에는 스택의 기본적인 개념에 대해 알아보았다. 이번 시간에는 스택을 '배열'로 구현하는 방법에 대해 알아보겠다. 총 3가지의 방법을 소개하고 있다. 첫번째는 전역변수로 구현하는 방법, 두 번째는 함수의 데이터로 매개변수를 전달하는 방법, 마지막은 동적으로 할당한 배열로 구현하는 방법이다. 전역변수로 구현하는 방법 이 방식은 스택으로 사용할 1차원 배열과 스택의 데이터 개수인 top 변수..
오늘은 컴퓨터에서 정말 많이 사용되는 자료구조인 스택에 대해 알아 볼 것이다. 스택(Stack) 스택을 사전에서 찾아보면 더미, 낟가리 를 의미한다고 되어 있다. 스택은 말 그대로 자료들이 더미로 쌓여있는 것과 유사하게 작동을 한다. 예를 들어 창고에 상자들을 쌓는다고 해보자. 가장 먼저 쌓은 상자는 가장 마지막에 꺼낼 수 있다. 가장 최근에 쌓은 상자는 가장 먼저 꺼낼 수 있다. 이러한 형태를 '후입선출'이라고 하며, 스택은 후입선출을 대표하는 자료형이다. 스택은 다양한 곳에 사용된다. 컴퓨터 프로그램을 실행하면 수많은 함수호출이 이루어진다. 함수는 실행이 끝나면 자신을 호출한 함수로 돌아가야하는데 이때 돌아갈 주소를 저장하는 것도 스택이다. 스택의 구조와 추상자료형 스택은 말그대로 데이터가 들어가는 ..
오늘은 이중연결리스트에 대해 다루어 볼 것이다. 단순연결리스트와 원형 연결리스트에 대해서는 이전 포스팅을 참고하자. https://mobuk.tistory.com/8?category=1076684 [자료구조] C - 연결리스트(linkedlist) - 1. 단순연결리스트 연결리스트(linked list) 연결리스트는 각 데이터들을 포인터로 연결하여 관리하는 구조이다. 이때, 자기 참조 구조체를 선언하여 '노드'라는 것을 만들고 이를 포인터로 연결한다. 자기 참조 구조 mobuk.tistory.com https://mobuk.tistory.com/14?category=1076684 [자료구조] C - 연결리스트(linkedlist) - 2. 원형연결리스트 오늘은 지난시간에 이어서 연결리스트에 대한 이야기를..
오늘은 지난시간에 이어서 연결리스트에 대한 이야기를 할 것이다. 연결리스트의 개념과 단순연결리스트에 대한 내용은 아래 링크를 참고해라. https://mobuk.tistory.com/8?category=1076684 [자료구조] C - 연결리스트(linkedlist) - 1. 단순연결리스트 연결리스트(linked list) 연결리스트는 각 데이터들을 포인터로 연결하여 관리하는 구조이다. 이때, 자기 참조 구조체를 선언하여 '노드'라는 것을 만들고 이를 포인터로 연결한다. 자기 참조 구조 mobuk.tistory.com 원형연결리스트의 구조 지난시간에는 단순연결리스트에 대해 공부했다. 이번에는 단순 연결리스트의 처음과 끝이 연결되어 있는 형태인 원형연결리스트에 대해 공부했다. 원형 연결리스트 구조는 기본적..
연결리스트(linked list) 연결리스트는 각 데이터들을 포인터로 연결하여 관리하는 구조이다. 이때, 자기 참조 구조체를 선언하여 '노드'라는 것을 만들고 이를 포인터로 연결한다. 자기 참조 구조체 자기참조구조체란 구조체 안에서 자신과 똑같은 모양의 구조체를 포인터로 가리키는 모양을 띄고 있다. struct self{ struct self * link; }; 위 코드가 자기 참조 구조체의 가장 간단한 형태이다. struct self 안에서 struct self 형을 가리키는 link를 선언해서 포인터가 가리킬 수 있도록 하였다. 이 것을 이용하면 연결리스트를 구현할 수 있다. 연결리스트 연결리스트의 기본 모양 typedef int element; typedef struct linkedlist{ ele..
