LimeCoding

트리란?(What is Tree?) 트리는 우리가 일상생활에서도 많이 볼 수 있는 형태의 자료구조이다. 윈도우 탐색기에서의 폴더 구조나 대진표가 대표적인 트리 구조이다. 트리는 나무를 거꾸로 뒤집어 놓은 형태를 가지며 노드라 불리는 데이터 요소를 기준으로 나무가지가 뻗어나가듯이 노드들이 연결되어 있다. 트리를 좀 더 명확하게 정의하면 다음과 같다. 정의 트리는 다음과 같이 재귀적으로 정의된다. 트리는 최상위 노드(node)인 하나의 루트(root)를 갖는다. 루트를 제외한 나머지 노드들은 n(n≥0)개의 서로소인 부분집합 T1, ... ,Tn 으로 분리되는데, 각각의 부분집합은 마찬가지로 트리이다. 이때, T1, ... ,Tn을 서브트리(subtree)라 한다. 트리가 무엇인지 간단하게 알았으니 이번에는..

이중 연결 리스트란?(What is Doubly linked list?) 이중 연결 리스트(doubly linked list)는 기존 단순, 원형 연결 리스트의 단점인 단방향 흐름을 2개의 링크 필드를 이용하여 양방향으로 움직일 수 있게 만든 것이 이중 연결 리스트이다. 원형 연결 리스트에 이중 연결 리스트를 결합하면 이중 원형 연결 리스트가 된다. 이중 연결 리스트는 양방향으로 움직일 수 있어 데이터 접근이 단순, 원형 연결 리스트보다 쉽고 삽입, 삭제 연산시 선행 노드에 대한 정보가 필요없다는 장점이 있다. 이중 연결 리스트의 노드는 다음과 같다. 이중 연결 리스트의 기본적인 연산은 다음과 같다. 리스트 생성 노드 삽입 노드 삭제 리스트 생성 리스트는 헤드 노드를 갖는 리스트를 생성한다. 리스트를 생..

연결 리스트를 잘 모른다면 필자가 포스팅한 내용을 보고 온다면 이해하기 편하다. 원형 연결 리스트란?(What is Circular linked list?) 원형 연결 리스트(circular linked list)는 단순 연결 리스트의 단점을 보완한 리스트이다. 단순 연결 리스트는 한 방향으로 움직이면서 그 끝이 정해져 있기 때문에 리스트를 검색할 때 항상 리스트의 처음부터 접근해야하는 단점이 있다. 또한 리스트가 순환을 요구한다면 더더욱 불리하다. 이를 해결하기 위해 단순 연결리스트의 마지막 노드가 리스트의 처음 노드를 가리키도록 만든 것이 원형 연결 리스트이다. 원형 연결 리스트는 다음과 같은 형태를 가진다. 원형 연결 리스트는 다음과 같은 기본연산을 가지고 있다. 리스트 생성 노드 삽입 노드 삭제 ..

연결 리스트란?(What is Linked List?) 연결 리스트(Linked list)란 링크로 원소들이 연결된 순차 리스트를 말한다. 연결 리스트는 순차 리스트의 삽입삭제 연산에서의 불리한 점을 보완하기 위해 만들어 졌다. 순차 리스트에서 삽입 연산을 하게 되면 중간에 데이터를 집어넣을 때 삽입될 데이터를 위해 공간을 만들어야 한다. 이때 공간을 만드는 과정에서 삽입되는 데이터 뒤에 데이터들이 자리를 옮기기 위한 연산을 취해야 하는데 이는 리스트가 가지고 있는 데이터가 크면 클수록 많은 시간이 걸린다. 삭제 연산도 삭제후 빈 공간을 채우기 위해 자리를 옮기는 과정이 필요하다. 이러한 문제점들을 해결하는 것이 연결 리스트이다. 연결 리스트를 이루는 기본적인 단위는 노드(node)이다. 노드는 데이터 ..

큐란?(What is Queue) 큐(Queue)는 데이터가 들어가는 곳과 나가는 곳이 한 곳으로 정해져있는 자료 구조를 말한다. 매표소에 사람들이 줄을 서 있으면 먼저 온 순서대로 표를 구매하게 된다. 큐는 먼저 온 데이터를 먼저 처리하는 형태를 띈다. 이를 FIFO(First-In-First-Out) 또는 LILO(Last-In-Last-Out)이라고 한다. 둘 다 맞는 표현이지만 FIFO를 더 많이 사용한다. 큐에서 데이터가 삽입되는 부분을 rear라고 하고 데이터가 삭제되는 곳을 front라고 한다. rear가 가리키는 데이터는 가장 최근에 삽입된 데이터이고 front가 가리키는 데이터는 가장 먼저 삽입된 데이터이다. 큐의 연산(Queue Operation) 큐의 기본 연산은 다음과 같다. Enq..

스택이란?(What is Stack?) 우리가 식당같은 곳에 가보면 다 먹은 음식의 접시나 그릇은 위로 차곡차곡 쌓아 올리는 모습을 볼 수 있다. 설거지를 할때는 위에서부터 하나씩 꺼내어 설거지를 하게 된다. 이것이 스택이다. 스택(Stack)이란 데이터 삽입, 삭제가 한 방향에서만 이루어지는 것을 말한다. 스택은 가장 먼저 들어온 데이터는 가장 나중에 나가고 가장 나중에 들어온 데이터는 가장 먼저 나가게 된는 성질을 가지고 있다. 이를 LIFO(Last-In-First-Out) 또는 FILO(First-In-Last-Out)이라고 한다. 둘 다 맞는 표현이지만 LIFO를 더 많이 사용한다. 스택은 top과 bottom이라는 2개의 포인터를 이용하여 삽입과 삭제를 제어한다. top포인터는 스택의 가장 위..

배열이란?(What is Array) 배열(array)또는 순차 리스트(sequential list)는 인덱스와 값의 쌍으로 이루어진 연속적인 메모리 위치의 집합이라고 정의할 수 있다. 배열은 인덱스와 값으로 이루어지는데 인덱스(index)는 어떤 값에 접근하기 위해 필요한 것이다. 값(value)는 배열 안에 실제로 들어가 있는 값을 의미한다. 만약 우리가 week[7] = {월, 화, 수, 목,금, 토, 일}이라는 배열을 선언한다면 요일은 배열의 값이 되고 '수'라는 값에 접근하고 싶으면 인덱스 2를 통해 접근할 수 있다. 이 부분은 c의 배열을 공부하면 배열이 어떤 식으로 작동하는지 알 수 있다. 배열은 값에 접근할 때 O(1)의 시간 복잡도를 갖는다. 즉, 배열은 어떤 값에 접근하던지 모두 동일한..

자료구조란? 자료구조(Data structure)는 컴퓨터 분야에서 여러가지 문자, 숫자와 같은 자료들을 체계적으로 정리하고 구조화하는 방법을 배우는 이론이다. 자료구조는 컴퓨터 분야를 공부하는 사람이라면 필수적으로 알아야하는 기초 상식이다. 우리는 컴퓨터를 가지고 현실의 문제를 해결한다. 하지만 컴퓨터와 현실 사이에는 표현하는 방법의 차이가 있다. 우리는 10진법을 사용하지만 컴퓨터는 2진법을 사용한다. 우리는 종이와 펜으로 계산을 하지만 컴퓨터는 전기의 켜짐과 꺼짐으로 데이터를 인식한다. 마찬가지로 자료를 다루는 방법에서도 컴퓨터와 현실에서는 차이를 보인다. 이 현실에서의 데이터를 컴퓨터에서 구조화하고 그 구조 안에서 데이터를 효율적으로 처리하고 각 구조의 효율성을 측정하는 것이 자료구조의 목표이다...

분할 정복(Divide and Conquer) 분할 정복(divide and conquer)이란 해결해야 될 문제를 작은 단위로 나누어 더 이상 나눌 수 없어지는 단계가 되면 그 단계에서 문제를 해결하고 이를 통해 본래 문제로 거슬러 올라가는 방식의 문제해결 방법이다. 때로는 가장 작은 단계의 해답이 본래 문제의 해답이 되기도 한다. 분할 정복의 사용 예시로는 합병 정렬(merge sort)가 있다. 동적 계획법(Dynamic Programming) 동적 계획법(Dynamic Programming)은 문제를 분할한다는 점에서는 분할 정복과 같지만 이전 문제의 해답을 이용하여 다음 문제를 푼다는 점에서 분할 정복과의 차이점을 보인다. 팩토리얼을 예로 들어 설명하도록 하겠다. 우리가 10!의 해답을 구하면 ..

반복 알고리즘(loop algorithm) 반복 알고리즘(loop algorithm)이란 for, while과 같은 반복문을 이용하여 문제를 해결하는 알고리즘을 말한다. 반복문을 이용한 알고리즘으로는 1부터 100까지 더하는 합 알고리즘이 있다. 재귀 알고리즘(recursive algorithm) 함수는 자기 자신을 내부에서 호출할 수 있다. 이러한 함수를 재귀 함수라고 한다. 재귀 알고리즘(recursive algorithm)이란 재귀 함수를 이용하여 문제를 해결하는 알고리즘을 말한다. 재귀 알고리즘은 팩토리얼이나 피보나치 수열등에 쓰인다. 재귀 함수와 반복문의 차이 재귀 함수와 반복문은 속도나 작동 방식에서 차이가 난다. 반복문은 프로그래머가 지정해준 초기값, 조건값, 증감값을 통해 반복을 제어하고 ..