잔잔한 물결로 파도 만들기

Merge Sort는 이전 포스팅에서 공부했던 Quick Sort와 함께 분할 정복을 활용한 대표적인 정렬 기법이다. 1945년에 폰 노이만이 개발했다고 한다. 안정적인 정렬로 알려져 있으며, 데이터의 크기와 상관없이 일정한 성능을 보여준다는 장점이 있다. 따라서 대용량의 데이터를 정렬할 때 효과적이라고 한다. 앞서 Quick Sort가 Java에서 기본형 타입의 배열의 Array.sort() 메서드에 활용된다고 했는데, 객체 타입 배열의 Array.sort()에는 Tim Sort가 쓰인다. 파이썬의 list.sort()와 sorted(list)도 Tim Sort 기반으로 동작한다. 여기서 Tim Sort가 삽입 정렬(Insertion Sort)과 Merge Sort를 결합한 기법이다. 1. 핵심 아이디..

분할 정복 알고리즘은 다양한 알고리즘 설계에서 핵심 원칙으로 사용되고 있다. 자주 접하는 개념 중에선 Quick Sort, Merge Sort가 분할 정복 알고리즘을 응용한 대표적인 예시이다. 고속 푸리에 변환(FFT)도 분할 정복 알고리즘 기반이라고 한다. 분할 정복 알고리즘 개념 분할 정복(Divide and Conquer)은 큰 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 설계 전략이다. Divide and Conquer라는 이름의 어원은 원래 정치와 군사 전략에서 사용되던 용어로, 큰 적 또는 문제를 작은 부분으로 나누어 각각을 해결함으로써 전체를 제어하는 전략을 의미한다고 한다. (나무위키에 따르면 제국주의 시절 유럽 식민제국이 식민지인들의 단결을 막기 위해 주로 사용한 방법으로 유명한 분..

이중 연결 리스트(Doubly Linked List)와 원형 연결 리스트(Circular Linked List)는 연결 리스트를 살짝 변형하여 단점을 개선한 자료구조이다. 연결 리스트를 배열과 비교했듯, 이들 역시 기본형인 단순 연결 리스트와 비교하면서 이해하는 게 효과적일 것 같다. 단순 연결 리스트 vs 이중 연결 리스트 vs 원형 연결 리스트 1. 개념 단순 연결 리스트: 일방향적. Head 노드 → Tail 노드 방향으로 포인터가 다음 노드 주소를 일방향적으로 가리킨다. 이중 연결 리스트: 양방향적. Head 노드 ↔ Tail 노드 양방향에서 다음 노드 주소를 양방향적으로 가리킨다. 원형 연결 리스트: 일방향적이나 순환적. Head 노드 → Tail 노드 일방향으로 포인터가 가리키지만, Tail ..

연결 리스트는 그 유연성과 동적인 특성 때문에 매우 중요한 자료구조로 간주된다. 연결 리스트는 여러개의 노드가 이어지는 형태로 구성되어 있다. '각 노드 = 데이터(data) + 포인터(next)' 이다. 해당 자료구조의 특징에 대해서는 배열(Array)과의 비교를 통해 이해하는 것이 가장 효율적일 것 같다. 그 이후에 단순 연결 리스트의 변형인 이중 연결 리스트, 원형 연결 리스트에 대해 비교해보자. 연결 리스트(Linked List) vs 배열 (Array) 1. 개념적 차이 배열 : 데이터가 메모리 상 연속된 공간에 할당된다. 즉, '논리적 저장 순서'와 '물리적 저장 순서'가 일치한다. 연결 리스트 : 연결 리스트의 노드들은 메모리 상 불연속적인 공간에 존재한다. 즉, '논리적 저장 순서'와 '물..

Quick sort는 1961년 Tony Hoare(토니 호어)가 발표한 정렬 기법이다. 정렬 기법 중에서 매우 흔히 사용되는 기법으로, 현대에는 Quick Sort에 여러 가지 최적화 기법을 추가한 변형을 자주 사용한다. 예를 들어, Java의 Array.sort() 메서드는 기본형 타입의 배열(int, long 등)에 대해서는 Dual-Pivot Quick Sort를 사용한다고 한다. (객체 배열에 대해서는 Tim Sort를 사용한다.) - Dual-Privot Quick Sort: Insertion Sort와 Quick Sort를 결합한 정렬 기법 - Tim Sort: Insertion Sort와 Merge Sort를 결합한 정렬 기법 1. 핵심 아이디어 분할 정복 전략을 사용하여 리스트를 정렬한다..

선형 자료구조 데이터를 효과적으로 관리 및 접근하는 방법은 소프트웨어 개발에서 중요한 요소이다. '자료구조 (Data Structure)'는 그 이름에 걸맞게 데이터를 저장, 관리, 조작하기 위한 구조적인 방법을 의미한다. 그 중에서도 선형 자료구조는 이름에서도 알 수 있듯, 데이터 요소들이 선(linear)처럼 일렬로 연결되어 있는 자료구조이다. 선형 구조는 데이터의 시작부터 끝까지 순차적으로 접근한다는 특징을 가진다. 대표적인 선형 자료구조는 다음과 같다. - 기본적인 자료구조: 배열, 문자열, 스택, 큐, 연결 리스트 (단순 연결 리스트) - 심화(응용) 자료구조: 연결 리스트의 변형 (이중 연결 리스트, 원형 연결 리스트), 큐의 변형 (덱) 아래는 위 리스트 중에서 배열, 스택, 큐, 덱에 대한..

프로그램의 효율성 프로그램의 효율성은 해당 프로그램이 얼마나 빠르게 원하는 결과를 도출하고, 그 과정에서 얼마나 적은 자원을 사용하는지를 기준으로 평가된다. 특히 알고리즘 코드를 작성하는 입장에서는, 내 코드 혹은 동료의 코드의 효율성을 빠르게 판단할 수 있는 인지적 도구가 필요하다. 따라서 프로그램 효율성울 평가하는 두 가지 핵심 요소, 즉 1) 얼마나 빠른 시간 내에, 2) 얼마나 적은 자원을 사용하여 구현되었는지를 쉽게 파악할 수 있도록 1) '시간 복잡도(Time Complexity)'와 2) '공간 복잡도(Space Complexity)', 그리고 이들을 나타내는 표기법인 'Big-O' 개념을 배울 필요가 있다. 백준 문제를 풀 때, 항상 문제에 시간 제한과 메모리 제한이 걸려 있다. 여기서 '..

재귀함수 문제를 아직 몇 개 못 풀어보긴 했지만, 지금까지 느낌으로는 재귀함수를 활용한 풀이는 마법같이 느껴지기도 한다. 하위 문제가 올바르게 해결된다는 가정만 정확히 한다면, 하위 문제의 구체적인 해결 방법을 코드로 직접 짜지 않아도 컴퓨터의 빠른 연산이 자동으로 해결해준다. 처음에는 '이게 말이 돼?'라는 생각이 든다. 때문에 직관적이지 않지만, 제대로 습득한 사람들에게는 매우 유용한 도구가 될 것이라 생각된다. 하위 문제에 대한 해결책이 이미 정의되어 있다고 "가정"하는 것은 재귀의 핵심 철학 중 하나입니다. 재귀의 아름다움은 그것이 문제를 단순화하는 방식에 있습니다. 복잡한 문제를 여러 작은 조각으로 나누면, 각 조각을 해결하는 것은 종종 훨씬 더 쉽습니다. 재귀는 이러한 단순화를 반복적으로 적용..

레지스터 레지스터는 CPU 내부의 작은 임시저장장치. 프로그램 속 명령어와 데이터는 실행 전후로 레지스터에 저장된다 레지스터는 앞선 ALU와 제어장치 대비 프로그래머 입장에서 더 중요하다. 우리가 개발하고 실행하는 것이 명령어, 데이터이기 때문이다. 우리는 레지스터에 담긴 값들을 관찰할 수 있다. 업무상으로도 레지스터에 담긴 값을 관찰할 일이 생각보다 많다. 로우레벨(시스템, 임베디드, 해킹 등) 개발자들은 더더욱 많다. 레지스터의 종류 CPU 내부에는 다양한 종류의 레지스터가 있고, 각각의 역할이 있다 (CPU마다 레지스터 종류와 이름이 다르기에, 일단 공통적인 것들을 일반화해서 알아두자) 프로그램 카운터 (명령어 포인터, Instruction Pointer) 메모리에서 읽어들일 명령어의 주소를 저장한..

ALU와 제어장치 CPU는 ALU, 제어장치, 여러개의 레지스터 로 이루어져 있다. ALU: 계산하는 장치 (산술논리 장치) 제어장치: 제어 신호를 발생시키고 명령어를 해석하는 장치 ALU (산술논리 장치, Arithmetic logic unit) (해당 강의에서는 다루지 않으나, ALU 안에는 가산기, 검출기 등 다양한 회로가 있다.) ALU가 받는 정보 (input to ALU) 계산을 하기 위해서는 피연산자와 수행할 연산이 필요하다 2 + 1 을 수행하라 → 2와 1은 피연산자이고, +는 수행할 연산(연산자)이다 피연산자는 레지스터에서 받아들이고, 수행할 연산은 제어장치로부터 제어신호로써 받아들이게 된다 ALU가 내보내는 정보 (output from ALU) 1. 연산 결과 binary 형태의 연산..