MOLOKINI

쉘 정렬(Shell Sort) 쉘 정렬은 Donald L. Shell 이라는 사람이 제안한 방법으로 삽입 정렬이 어느정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안한 방법입니다. 쉘 정렬의 속도는 삽입정렬의 O(n^2)보다 빠릅니다. 쉘 정렬의 속도는 약 O(n^1.5) : 몇개로 그룹들을 나누느냐에 따라 실행속도가 달라집니다. 삽입정렬의 최대 문제점은 요소들이 삽입될 때 이웃한 위치로만 이동한다는 것입니다. 만약, 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 이미 정렬된 요소들이 많은 이동을 해야만이 제자리로 삽입될 수 있습니다. - 정렬 위치 이후의 모든 요소들이 한 칸씩 옆으로 이동해야 정렬이 됨 쉘 정렬은 요소들이 멀리 떨어진 위치로 이동할 수 있습니다. 1. 정렬해야 할 ..

버블정렬 (Bubble Sort) 버블정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행합니다. 이렇게 되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동하게 되는데 이 과정을 스캔이라고 합니다. 이 스캔 과정을 반복하며 숫자가 정렬될 때까지 반복 수행합니다. 레코드의 이동 과정이 마치 물 속에서 거품이 보글보글 떠오르는 것과 유사하다고 하여 버블정렬이라고 부릅니다. 1. 인접한 2개의 레코드 비교, 작은 숫자를 앞으로 교환 2. 가장 큰 수가 오른쪽 끝으로 가게 됨 3. 1의 과정을 다시 진행하여 모든 숫자가 정렬될 때 까지 반복 스캔 과정 버블정렬의 특징 버블정렬은 안정성이 있고, 비효율적인 정렬입니..

삽입정렬 (Insertion Sort) 삽입정렬은 손안의 카드를 정렬하는 방법과 유사합니다. 즉, 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지되게 합니다. - 새로 삽입될 카드의 수 만큼 반복하면 전체 카드가 정렬 1. 리스트의 처음부터 값을 비교하며 정렬된 부분의 어느 위치에 삽입되어야 하는가를 판단 2. 해당 위치에 이 숫자를 삽입하게 되면 정렬된 부분의 크기는 하나씩 커지며 자리이동 3. 정렬되지 않은 부분은 크기가 하나 줄어듦 의 순서를 반복합니다. 삽입정렬의 특징 삽입정렬은 안정성이 있으며, 비효율적입니다. 처리속도는 선택정렬과 마찬가지로 O(n^2)입니다. 삽입정렬 코드

선택정렬 (Selection Sort) 선택정렬은 가장 이해하기 쉬운 정렬 방법입니다. 리스트 중 가장 작은 숫자를 선택하여 왼쪽 부터 정렬시켜 나가는 작업을 반복하는 정렬입니다. 아래는 선택정렬의 순서입니다. 선택정렬의 특징 선택정렬은 안정성이 없고 비효율적이지만 구조가 단순하여 구현이 간단하다는 장점이 있습니다. 레코드 갯수의 -1번 반복하여 정렬을 완료합니다.처리속도 O(n^2) - 안정성 : 입력 데이터에 동일한 키 값을 갖는 레코드가 여러개 존재할 경우 이들의 상대적인 위치가 정렬 후에도 그대로 바뀌지 않는 것을 안정성 있는 정렬 이라고 합니다. 선택정렬 구현 [출처] 게임프로그램을 위한 C++ Day-69 : 자료구조1 - 선택 정렬|작성자 1따봉1비행기

트리 (Tree) 지금까지는 리스트, 스택, 큐 등의 선형 자료 구조(Linear Data Structure)만을 공부했습니다. - 선형 자료 구조는 자료들이 직선과 같이 나열되어 있는 구조를 의미합니다. 만약 선형이 아니고 자료가 계층적인 구조를 가지고 있다면 어떻게 해야할까요? - 조상과 자손, 전체와 부분, 상사와 부하직원, 컴퓨터의 디렉토리 구조 등의 계층적 관계입니다. - 이런 계층적인 관계를 표현하기에는 선형 자료 구조로는 한계가 있습니다. 트리는 이러한 계층적인 구조를 표현하는데 사용하는 자료구조입니다. - 인공지능 문제에서도 트리가 사용됩니다. 의사결정트리 등 트리의 용어들을 알아보겠습니다. 노드 : 트리의 구성요소들 루트노드 : 부모가 없는 노드, 트리는 하나의 루트노드만 가집니다. 리프..

덱 (Deque) 덱은 Double-Ended Queue의 줄임말로 큐의 전단과 후단에서 모두 삽입과 삭제가 가능한 큐를 의미합니다. 덱은 스택과 큐의 연산들을 모두 가지고 있습니다. 예를 들면 add_front, delete_front 연산은 스택의 push, pop add_rear, delete_front 연산은 큐의 enqueue, dequeue 연산과 같습니다. 추가로 덱은 get_front, get_rear, delete_rear를 가지고 있습니다. (대소문자의 큰 의미는 없습니다) 덱은 보통 이중 연결 리스트로 구현됩니다. - 그 이유는 전단과 후단에서 모두 삽입, 삭제가 가능해야 하기 때문에 양쪽으로 링크를 가지고 있어야 편리하기 때문입니다. - 이중 연결 리스트의 첫 번째 노드와 마지막 노..

큐 (Queue) 스택의 경우 나중에 들어온 데이터가 먼저 나가는 구조인데 반해 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 구조입니다. 이러한 구조를 선입선출(FIFO : First-In First-Out)이라고 합니다. 큐의 예로는 매표소에서 표를 사기 위해 한줄로 늘어선 열을 들 수 있겠습니다. 큐의 연산은 enqueue : 큐의 뒤에 요소를 추가한다 dequeue : 큐의 앞에서 요소를 삭제한다 큐는 뒤(Rear)에 요소를 추가하고 앞(Front)에서 삭제합니다. 이러한 형태입니다. 데이터가 들어온 순서대로 앞에서 삭제되는 것을 확인하실 수 있습니다. 큐를 배열로 구현할 경우 rear와 front가 무한히 늘어나고, Dequeue 연산 이후 주기적으로 모든 요소들을 왼쪽으로 다시 이동시켜주..

스택 (Stack) 스택을 영어사전에서 찾아보면 '건초, 밀집 따위를 쌓아놓은 더미, 낟가리'를 의미한다고 되어있습니다. 예를 들면, 식당에 접시더미, 책상에 쌓여있는 책 정도로 볼 수 있습니다. 스택은 제일 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조를 가지고 있습니다. 이러한 형태를 후입선출(LIFO : Last-In First-Out)이라고 합니다. 스택에는 두가지 연산이 있습니다. Push : 삽입 연산 Pop : 삭제 연산 이러한 구조입니다. 즉, 스택의 맨 위에서만 입출력이 일어납니다. 가장 전형적인 스택의 사용 예로는 함수 호출에서 복귀주소를 기억하거나 undo 기능을 구현할 때에도 스택이 사용됩니다. 아래는 스택의 C++ 구현 코드입니다. 코드..

빅엔디안과 리틀엔디안 바이트 오더라하여 바이트의 정렬 순서를 이야기합니다. 프로그래밍 하는 과정에서 많이 헷갈리기도 하는데요. 리틀엔디안부터 알아보도록 하겠습니다. 리틀엔디안 (Little Endian) 리틀엔디안은 주로 인텔 프로세스에서 사용하는 바이트오더 입니다. 리틀이라는 말 처럼 메모리 시작 주소를 하위 바이트부터 기록한다는 뜻입니다. - 빅엔디안은 그럼 반대겠죠? 리틀 엔디안의 바이트 오더 기록 순서입니다. 레지스터에 기록된 내용을 하위바이트부터 메모리에 넣는 것을 보실 수 있습니다. - 오른쪽 -> 왼쪽의 순서로 읽습니다. 리틀엔디안은 메모리에 저장된 값의 하위 바이트들만 사용할 때에는 별도의 계산이 필요 없다는 장점이 있습니다. - 앞의 두 바이트나 한 바이트를 떼어내면 바로 하위 16비트나..

아키텍처, 프레임워크, 플랫폼. 상당히 많이 헷갈려서 검색을 해보았습니다. [아키텍처: S/W 주요 설계 구조] S/W의 특징들을 결정짓는 주요 설계 구조이다. 즉, S/W의 구성 요소 및 이들간의 인터페이스, 동작 방식 등의 특징들을 결정짓는 모든 설계 구조를 말한다. 이는 S/W의 주요 특징을 결정짓고 개발에 미치는 영향도 매우 커서 가장 중요한 부분이라고 할 수 있다. [프레임워크: S/W 뼈대 구조] 프레임워크는 S/W가 개발될 수 있는 뼈대 구조이다. 지원 프로그램, 라이브러리, 언어, 다른 S/W 구성 요소들을 엮어 주는 역할을 한다. 그리고 플랫폼과 구분되는 점은 프로그램 개발을 위한 부분만을 갖기에 완전한 S/W 실행 환경이 되지 않는다. [플랫폼: S/W 실행 환경] 가장 일반적이면서도 ..