개발 블로그 개발 블로그

트리의 구조와 관련 용어트리는 아래의 사진과 같이 노드(node)와 가지(edge)로 구성된다. 각 노드는 가지를 통해 다른 노드와 연결된다.루트  : 트리의 가장 위쪽에 있는 노드를 루트라고 한다. 루트는 트리 하나에 1개만 존재한다.  리프 : 가장 아래쪽에 있는 노드를 의미한다. 단말 노드(terminal node), 외부 노드(external node)라고도 한다. 물리적으로 가장 밑에 위치한다는 의미가 아니라 가지가 더 이상 뻗어나갈 수 없는 마지막에 노드가 있다는 뜻이다. 비단말 노드(non-terminal node) : 리프를 제외한 노드. 내부 노드(internal node)라고도 한다. 자식 : 어떤 노드와 가지가 연결되었을 때 아래쪽 노드. 노드는 자식을 몇개라도 가질 수 있다. 부모 ..

리스트는 데이터에 순서를 매겨 늘어놓은 자료구조다. 구조가 간단한 리스트로 선형 리스트(linear list) 또는 연결 리스트(linked list)가 있다.위의 그림은 연결 리스트의 기본 구조다. A에서 F까지 데이터가 순서대로 나열되고 각 데이터가 화살표로 연결되어 있다. 이런 구조에서는 누군가를 건너뛰거나 뒤돌아 앞사람에게 연락해서는 안 된다.연결 리스트에서 각각의 원소를 node라고 한다. 노드는 data와 pointer를 갖고 있다. 맨 앞에 있는 노드를 head node, 맨 끝에 있는 노드를 tail node라고 한다. 각 노드에서 바로 앞에 있는 노드를 predecessor node, 바로 뒤에 있는 노드를 successor node라고 한다. 배열로 연결 리스트 만들기뒤쪽 노드 꺼내기:..

정렬 알고리즘의 정의정렬(sorting)이란 텍스트나 숫자 등의 key를 항목 값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말한다. 데이터를 정렬하면 쉽게 검색할 수 있다. 값이 작은 데이터를 앞쪽에 늘어놓는 것을 오름차순(ascending order)정렬이라 하고, 반대를 내림차순(descending order) 정렬이라 한다.정렬 알고리즘은 데이터를 교환-선택-삽입하면서 정렬을 완료한다. 대부분의 정렬 알고리즘은 이 세가지를 응용한다.안정성여러 정렬 알고리즘 가운데 안정적인(stable) 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있다.위의 그림처럼 안정적인 정렬 알고리즘은 값이 같은 원소의 순서가 정렬한 후에도 유지되는 것을 말한다. 안정적이지 않은 알고리즘은 정렬 ..

어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우 재귀(recursion)라고 한다.  재귀를 사용하는 대표적인 예로 팩토리얼(factorial) 문제가 있다. 팩토리얼은 양의 정수를 순서대로 곱한다는 의미다. 양의 정수 n의 팩토리얼(n!)은 다음과 같이 재귀적 정의를 할 수 있다.(재귀 과정으로 팩토리얼값을 구하는 문제는 재귀의 원리를 이해하기 위한 예제일 뿐 알고리즘 문제를 풀 때 현실적으로 적절하지 않다.) 더보기def factorial(n :int): if n > 0: return n * factorial(n - 1) else: return 1 if __name__ == '__main__': n = int(input('..

Queue큐는 스택과 같이 데이터를 임시 저장하는 자료구조이다(배열을 사용하여 구현 가능).가장 먼저 넢은 데이터를 가장 먼저 꺼내는 선입선출(FIFO) 구조이다.  컴퓨터에서 데이터를 주고받을 때 각 주변장치들 사이에 존재하는 속도의 차이나 시간차이를 극복하기 위한 임시 기억 장치로 큐가 사용되는데, 이것을 buffer라고 한다. 큐에 데이터를 추가하는 작업을 인큐(enqueue), 데이터를 꺼내는 작업을 디큐(dequeue). 데이터를 꺼내는 쪽을 front, 넣는 쪽을 rear라고 한다. 위의 배열은 원소 24를 인큐하고 19를 디큐하는 작업이다. 인큐는 맨 뒤의 인덱스에 추가하면 그만이기 때문에 복잡도는 O(1)으로 적은 cost로 구현 가능하다. 하지만 디큐는 맨 앞의 원소를 꺼낸 후 모든 원소..

검색의 종류로는 배열 검색, 연결 리스트 검색, 이진 검색 트리 알고리즘이 있다.배열 검색의 종류로는  선형 검색 : 무작위로 늘어놓은 데이터 집합에서 검색을 수행한다.이진 검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서 빠른 검색을 수행한다.해시법 : 추가-삭제가 자주 일어나는 데이터 집합에서 빠른 검색을 수행한다. 체인법 : 같은 해시값 데이터를 연결 리스트로 연결하는 방법이다.오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법이다.선형 검색 linear search가장 기본적인 배열 검색 방법이다. 선형으로 늘어선 배열에서 원하는 Key값을 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘이다.즉, 선형 검색에서 배열 스캔의 종료 조건은 2가지다.1. 검색할 값을 찾지 못하..

병합 정렬 merge sort노이만이 고안한 분할 정복 알고리즘. 퀵 정렬과 반대로 안정 정렬에 속한다. 배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘이다. 과정i) 리스트의 길이가 0또는 1이면 이미 정렬된 것으로 본다.ii) 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.iii) 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.iv) 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 장점- 안정적인 정렬 방법- 레코드를 linked list로 구성하면, 데이터의 이동은 무시할 수 있을 정도로 작아진다. (퀵 정렬을 포함한 다른 정렬 방법보다 효율적이다.) 단점- 레코드를 배열로 구성하면 임시 배열이 필요하다..