유제필의 개발 블로그

버블 정렬(Bubble Sort) 요약 시간 복잡도 : O(n) = n ^ 2 인접한 두 요소의 대소 관계를 비교하여 반복 교환 시간 복잡도가 느리지만, 코드가 단순하여 구현이 쉬워 자주 사용 요소의 개수가 n개인 배열에서 n - 1회 비교, 교환을 하고 나면 가장 작은 요소가 맨 처음 또는 끝으로 이동 비교, 교환 과정을 패스라고 함 버블 정렬이란 인접한 두 요소의 대소 관계를 비교하여 교환을 반복하는 것을 말한다. 시간 복잡도가 상당히 느리지만, 코드가 단순하여 구현이 쉽기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 버블 이라는 이름이 붙었다. 버블 정렬은 정렬을 앞에서 시작할 수도 있고, 뒤부터 시작할 수도 있지만, 요소의 끝부터 확인하고 정렬해야 한다..

하노이의 탑(Towers Of Hanoi) 요약 큰 원반이 아래에서 차례로 위치할 수 있고, 최소한의 횟수로 마지막 기둥으로 원반을 옮기는 문제 가장 큰 원반을 제외하고 나머지 원반을 그룹으로 묶어 문제 해결에 접근 그룹은 원반 개수의 N - 1 하노이의 탑(Towers Of Hanoi)이란 하뇌의 탑은 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제이다. 모든 원반는 크기가 다르고 처음에는 모든 원반이 이 규칙에 맞게 첫 번째 기둥에 쌓여 있다. 이 상태에서 모든 원반을 세 번째 기둥으로 최소한의 횟수로 옮기는 문제이며, 원반은 1개씩만, 큰 원반을 작은 원반위에 쌓을 수 없다. 문제를 해결하기 위해 가장 큰 원반을 제외하고, 나머지 원반을 그룹으로 묶어..

재귀(Recursive)란 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적 이라고 한다. 쉽게 말해서 자기 자신을 포함한 것이라고 쉽게 생각할 수 있다. 프로그래밍에서 재귀란 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법을 말한다. 재귀를 효과적으로 사용하면 프로그램을 간결하게 작성할 수 있다. 재귀적 정의에 의해 무한으로 존재하는 자연수를 아래의 두 조건으로 정의할 수 있다. 1은 자연수이다. 자연수 n의 바로 다음 수도 자연수이다. 팩토리얼(Factorial) 팩토리얼이란 한글로 계승 또는 순차곱셈이라고 하며, 1에서 시작하여 어떤 범위에 있는 모든 정수를 곱하는 것을 의미한다. 팩토리얼 예제는 재귀함수의 예제로 많이 사용한다. ..

요약 링 버퍼 큐 복잡도 : O(1) 배열 큐 복잡도 : O(n) 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 구조인 FIFO(First In - First Out) 구조를 따름 큐에 데이터를 넣는 작업을 인큐(Enqueue), 또는 스택과 같이 푸쉬(Push)라고 함 큐에서 데이터를 꺼내는 작업을 디큐(Dequeue) 또는 스택과 같이 팝(Pop)이라고 함 데이터를 꺼내는 쪽을 프론트(Front), 데이터를 넣는 쪽을 리어(Rear)라고 함 링 버퍼는 배열의 처음과 끝이 연결되어 있는 구조로, 배열 요소를 앞쪽으로 옮기지 않아도 되어 좀 더 효율적인 구조로 사용 가능 일반 배열로 사용하는 큐로 구현 시 배열 요소를 앞쪽으로 옮겨야 하는 작업이 필요 큐(Queue)란 큐란 스택과 비슷한 자료구조로..

요약 데이터를 일시적으로 저장히기 위해 사용하는 자료구조로 한 곳에서만 입출력이 일어남 먼저 들어간 데이터는 마지막에 나오는 FIFO 구조 (First In - Last Out) 마지막에 들어간 데이터는 먼저 나오는 LIFO 구조 (Last In - First Out) 데이터를 담는 행위를 Push, 데이터를 추출하는 행위를 Pop이라고 함 중요 구조체 멤버로 저장할 메모리 공간, 현재 가리키는 위치, 최대 사이즈 3가지가 필요 스택(Stack)이란 스택은 바닥에서 부터 데이터를 쌓아 올리는 자료구조의 일종이며, 스택의 입/출력은 오로지 꼭대기에서만 이루어진다. 가장 먼저 들어간 데이터는 가장 나중에 나오는 구조이고(FILO First In - Last Out), 가장 마지막에 들어간 데이터는 가장 먼저..

환형 링크드 리스트(Circular Linked List) 요약 더블 링크드 리스트와 동일하며, 다른 점은 헤드와 테일이 연결되어 있음 테일은 자신의 nextNode로 헤드를 가리키고, 헤드는 prevNode로 테일을 가리킴 리스트의 시작과 끝을 미리 알 수 있음 환형 링크드 리스트(Circular Linked List)란 환현 링크드는 헤드와 테일이 연결되어 있는 리스트 구조를 말한다. 테일은 자신의 nextNode로 헤드를 가리키고, 헤드는 prevNode로 테일을 가리킨다. 환형 링크드 리스트의 가장 큰 장점은 리스트의 시작과 끝을 미리 알 수 있다는 부분이다. 이러한 장점으로, 더블 링크드의 삽입 함수와 같은 부분의 성능을 많이 개선할 수 있다. 또한 노드를 뒤에서 역순으로 찾아나갈 수 있는 탐색..

요약 링크드 리스트의 문제였던 탐색 문제를 개선한 링크드 리스트 자료구조 첫 데이터를 헤드, 끝 데이터를 테일, 각 데이터를 노드라고 부름 각 노드의 다음 노드 주소와 이전 노드 주소 양 방향을 관리 노드가 앞 뒤 양 방향을 다루므로 접근은 용이하나 삭제 등에서 각각 전부 삭제해 주어야 함 데이터의 접근이 어려우나, 생성, 소멸, 삭제 등은 쉬움 더블 링크드 리스트(Double Linked List)란 더블 링크드 리스트란 링크드 리스트의 탐색 기능을 개선한 자료구조이다. 기존 링크드 리스트에서 탐색을 하기 위해 헤드에서 테일 방향으로의 노드를 모두 거쳐야 했다. 이러한 불편함을 더블 링크드 리스트 구조에선 헤드 -> 테일 및 테일 -> 헤드 방향, 즉 양방향 탐색이 가능하도록 개선했다. 양방향 탐색이 ..

요약 배열의 반대 개념으로, 데이터의 크기를 유연하게 변경할 수 있음 첫 데이터를 헤드, 끝 데이터를 테일, 각 데이터를 노드라고 부름 다음 노드의 주소를 이전 노드의 저장하여 다음 노드의 주소로 접근 데이터의 접근이 어려우나, 생성, 소멸, 삭제 등은 쉬움 장점 새로운 노두의 추가, 삽입, 삭제가 쉽고 빠름. (배열은 새로운 요소를 삽입하거나 삭제를 하기 어려움) 현재 노드의 다음 노드를 얻어오는 연산에 대해 비용이 발생하지 않음 단점 다음 노드를 가리키려는 포인터 때문에 각 노드마다 추가적인 메모리가 필요함 특정 위치에 있는 노드에 접근하기 위한 비용이 크며 접근하기 까지 시간이 많이 필요함 (노드에 접근하기 위해 N - 1회의 접근이 필요함) 리스트란 리스트는 이름과 같이 목록 형태로 이루어진 데이..