정기연재 - 컴퓨터공학/자료구조와 알고리즘7 6. Sorting (2) 6. Sorting (2) 지난 글에서 살펴본 $\mathcal{O}(n^2)$ 정렬 알고리즘의 경우, $n = 10^5$ 정도만 되어도 오래 걸립니다. 제 컴퓨터에서는 정수 $10$만 개를 정렬하는데 대략 24.5초 정도가 걸렸습니다. 여기서 $n$을 $10$배 하여 데이터가 $100$만 개가 된다면, 정렬이 현실적인 시간 안에 끝나지 않을 것 같습니다. 보다 빠른 알고리즘이 필요할 것 같습니다. 이번 글에서는 지난 글에서 소개한 정렬 알고리즘보다 효율적으로 동작하는 정렬 알고리즘을 2가지 소개하겠습니다. 두 정렬 알고리즘 모두 분할 정복(Divide and Conquer)이라는 굉장히 중요한 알고리즘 디자인 기법을 사용합니다. 이 기법에 대해서는 다른 글에서 더 상세하게 다루도록 하겠습니다. 지난 글.. 2022. 8. 18. 5. Sorting (1) 5. Sorting (1) 주어진 데이터를 특정 기준에 따라 재배열하는 작업을 정렬이라고 합니다. 주어진 데이터에 따라 기준은 얼마든지 달라질 수 있지만, 대표적으로 사용하는 기준은 오름차순 또는 내림차순입니다. 가장 쉬운 예시로 100개의 정수가 포함된 배열이 주어졌을 때 이 배열을 오름차순으로 정렬하는 경우를 생각해볼 수 있을 것입니다. 이때 첫 번째 원소가 최솟값, 마지막 원소가 최댓값임을 쉽게 알 수 있습니다. 또 다른 예시로 카드 게임을 하는데 54장의 트럼프 카드 중에서 조커 2장을 빼려고 하는 경우를 생각해볼 수 있습니다. 처음 개봉한 트럼프 카드라면 정렬이 되어 있어 조커가 맨 앞(혹은 맨 뒤)에 있어 쉽게 조커를 뺄 수 있지만, 카드가 뒤죽박죽 섞여 있다면 조커 2장을 찾기 위해 54장의.. 2022. 8. 10. 4. Linked List 4. Linked List 이번 글에서는 Linked List(연결 리스트) 자료구조에 대해 알아보겠습니다. List 자료구조의 제약 조건 Array나 List 자료구조에서는 원소들이 메모리 공간 상에 연속적으로 존재해야 한다는 제약 조건이 있었습니다. 이 때문에 삽입/삭제를 수행하기 위해서는 빈 공간을 만들거나 없애야 했고, 삽입/삭제 위치 뒤에 있는 원소들을 모두 옮겨야 했습니다. 여기서 만약 '원소들이 메모리 공간 상에 연속적으로 존재해야 한다'는 제약 조건을 없애면 어떻게 될까요? List의 각 원소는 메모리 공간에 개별적으로 존재할 수 있게 하고, List의 다음 원소를 빠르게 찾기 위해 다음 원소의 메모리 주소를 가지고 있도록 구현할 수 있습니다. Linked List 자료구조 소개 우선 Li.. 2022. 7. 27. 3. Arrays and Lists 3. Arrays and Lists 이번 글에서는 활용 빈도가 매우 높은 자료구조인 배열(Arrays)과 리스트(Lists)에 대해 알아보도록 하겠습니다. Arrays 배열은 인덱스(index)와 인덱스에 대응하는 원소들로 이루어진 자료구조입니다. 일반적으로 원소들은 모두 동일한 타입이며, 원소들이 메모리 상으로 연속적으로 존재하며, 언어마다 다르겠지만 보통 고정된 길이를 가집니다. 그림에서 보이는 것처럼, 보통 여러 개의 데이터를 저장할 때 사용합니다. 아래 코드는 C++에서 배열을 사용하는 방법입니다. 배열 C++ 코드 배열의 인덱스는 0부터 시작합니다! 원소가 $n$ 개 있는 배열의 인덱스는 $0$ 부터 $n-1$ 입니다. 이 범위를 벗어난 인덱스를 이용하면 올바르지 않은 참조가 되기 때문에 프로그.. 2022. 6. 1. 2. Asymptotic Notation (2) 2. Asymptotic Notation (2) 지난 글에 이어서 이번에는 점근적 표기법의 엄밀한 정의와 실제로 점근적 분석을 수행하는 방법을 살펴보도록 하겠습니다. 점근적 표기법의 엄밀한 정의 점근적 분석은 입력의 크기가 클 때, 즉 $n$ 이 충분히 클 때 수행한다고 했었습니다. 그래서 자연스럽게 $n$ 이 무한대로 가는 극한이 등장하게 되고, 극한을 엄밀하게 정의하는 방법과 굉장히 유사한 형태로 정의됩니다. Big-$\mathcal{O}$ Notation 어떤 함수 $g(n)$ 이 $\mathcal{O}(f(n))$ 이라는 것은, 적당한 양수 $c$ 와 자연수 $N$ 이 존재하여, 다음이 성립한다는 뜻입니다. $$n \geq N \implies 0 \leq g(n) \leq cf(n)$$ 이를 조금.. 2022. 5. 20. 1. Asymptotic Notation (1) 1. Asymptotic Notation (1) 지난번 글에서 알고리즘의 효율성이 중요하다는 이야기를 했었습니다. 그렇다면 알고리즘의 효율성은 어떤 기준을 가지고 판단할까요? 쉽게 생각해 봤을 때, 우선 알고리즘을 구현한 프로그램의 수행 시간을 생각해볼 수 있을 것입니다. 하지만 수행 시간은 같은 컴퓨터(정확히는 프로세서) 내에서만 유효하고, 기술이 발전해서 장비가 빨라지면 자연스럽게 수행 시간이 빨라지기 때문에 절대적인 지표로 사용하기는 어렵습니다. 따라서 구체적인 동작 시간 자체보다는 알고리즘의 연산 수를 대략적으로 파악하여 효율성을 분석합니다. 이렇게 해야 일단 장비의 사양에 관계 없이 측정할 수 있습니다. 그리고 연산 수가 적어야 알고리즘이 보다 빨리 끝날 것이고, 적은 연산 수로 같은 결과를 얻.. 2022. 4. 30. 0. Introduction 0. Introduction 안녕하세요! 자료구조와 알고리즘 주제로 연재를 하게 된 공우 13기 이성찬입니다. 반갑습니다! 여러분은 만약 구글이나 네이버에 로그인하는데 1분이 넘게 걸린다면 어떤 생각이 드실 것 같나요? 빠른 인터넷과 놀라운 성능을 가진 컴퓨터의 계산 속도에 익숙해진 분들이라면, 아마 참지 못할 정도로 답답해하실 것입니다. 저라면 10초가 지나기도 전에 왜 로그인이 안되는지 의아해하며 바로 새로고침 버튼을 누른 뒤 다시 시도해볼 것 같습니다. 로그인이 빨리 되는 것이 왜 중요할까요? 다양한 답을 생각할 수 있을 것 같습니다. 기다리기 힘들어서, 현대인은 바쁘기 때문에 빠르면 빠를수록 좋아서 등등... 다 맞는 말입니다. 이 현상을 서비스 제공자(구글/네이버)의 관점에서 본다면, 느린 로그.. 2022. 4. 22. 이전 1 다음
