ki hyun's 개발블로그

🔗 연결 리스트? 연결 리스트(linked list)는 객체가 선형적 순서를 가지도록 배치된 자료구조다. 인덱스에 의해 선형적 순서가 결정되는 배열과는 달리 연결 리스트에서는 각 객체에 있는 포인터에 의해 순서가 결정된다. 양방향 연결 리스트 key 속성값과 두 개의 포인터인 prev와 next를 속성값으로 가지는 객체다. 리스트의 원소 x가 주어질 때, x.next는 연결 리스트의 바로 다음 원소를, x.prev는 바로 직전 원소를 가리킨다. x.prev = NIL 이라면 이전 원소가 없으므로 이 리스트의 첫 번째 원소 또는 head라 한다. x.next = NIL 이라면 원소 x는 바로 다음 원소가 존재하지 않으므로 이 리스트의 마지막 원소 또는 tail이라고 한다. 단순 연결 리스트: prev 포인..

스택에서는 가장 최근에 삽입된 원소가 삭제된다. 즉, 후입선출 정책을 구현한 것이다. 큐에서는 집합에서 가장 오랜 시간 동안 존재한 원소가 삭제된다. 즉, 선입선출 정책을 구현한 것이다. 🗂 스택 스택에서는 스택에 값을 추가하는 연산을 Push, 인자를 값을 삭제하는 연산을 Pop이라고 한다. 💡 이때 Pop은 인자를 가지지않고 가장 최근에 삽입된 원소를 제거한다. 💡 이 연산들의 이름은 카페테리아 식당에서 스프링으로 접시를 받쳐 올려주는 접시 스택에서 유래된 것이라고 한다. 배열 S[1..n]으로 최대 n개의 원소를 가지는 스택을 구현할 수 있다. 배열은 가장 최근에 삽입된 원소를 가리키는 S.top을 속성값으로 가진다. S[1]은 스택의 맨 밑에 있는 원소를 나타내고 S[S.top]은 맨 위에 있는 ..

O(n)의 등장 이때까지 봐온 모든 정렬 알고리즘들은 입력된 숫자들을 비교해가며 정렬을 하였다. 하지만 비교하며 정렬하는 모든 알고리즘은 O(n log n)이라는 명확한 한계를 가지고 있다. 그렇다면 어떻게하면 정렬 알고리즘을 더욱 빠르게 작동시킬 수 있을까? 바로 비교를 하지 않으면 된다. O(n) 시간에 실행되는 정렬 알고리즘들은 비교를 하지 않고 정렬을 한다는 특징을 가지고 있다. 계수 정렬 계수 정렬은 말 그대로 x에 대해서 x보다 같거나 작은 원소의 개수를 센다. 이렇게 센 값은 나중에 x를 어디에 배치할 것인가를 결정할 때에 사용된다. 예를 들어 [2, 1, 3, 4, 8, 7, 9] 라는 배열이 있다고 가정해보자 이때 x에 대해서 같거나 작은 원소의 개수를 센다면 0 = 0 1 = 1 2 =..

🚨 이번 포스트는 복잡한 식과 머리 아픈 내용이 나올 수 있습니다. 퀵 정렬의 성능 저번 포스트에서는 퀵 정렬에 대해 알아보았다. 퀵 정렬의 평균적인 수행시간이 O(n log n) 이고 최악의 수행시간이 O(n^2) 이라는 것을 알았지만 최악의 수행시간이 O(n^2) 이나 되는 알고리즘이 어째서 힙 정렬보다 더 빠른지에 대해서는 자세히 다루지 않았다. 이번 포스트에서는 퀵 정렬의 성능에 대해 알아보고 어째서 퀵 정렬이 힙 정렬보다 더 효율적인 알고리즘인가에 대해 알아볼 것이다. 퀵 정렬의 수행시간은 분할 후 양쪽 구역의 크기가 비슷한가 아닌가에 따라 달라진다. 분할이 균등하게 된다면 퀵 정렬은 병합 정렬처럼 빠르게 작동한다. 하지만 분할의 균등하지 않다면 삽입 정렬처럼 느리게 동작한다. 분할을 가장 나쁘..

퀵 정렬은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n²)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. - 위키백과 - 1. 퀵 정렬? 퀵 정렬은 n개의 원소를 가진 배열을 최악의 경우에 O(n²)시간에 정렬하는 알고리즘이다. 이렇게 최악의 경우로만 봤을땐 퀵 정렬은 느리지만 평균 수행시간이 O(n lg n)으로 굉장히 효율적이고 O(n lg n)에 숨겨진 상수 인자도 굉장히 작다. 퀵 정렬은 병합 정렬과 마찬가지로 분할정복에 기반을 두고 있다. 따라서 퀵 정렬의 동작은 다음과 같이 설명할 수 있다. 분할: 배열 A[p..r]을 두 개의 부분 ..

힙에 관하여 이전 포스트에서 힙을 이용한 정렬인 힙 정렬에 대해 소개했다. 힙 정렬은 분명 훌륭한 알고리즘이지만 사실 나중에 소개할 퀵 정렬을 잘 구현하는 것이 일반적으로는 더 빠르다. 하지만 힙은 여러 방면으로 유용하게 사용할 수 있는데 이번 포스트에서는 힙을 가장 잘 응용하여 널리 쓰이고 있는 우선순위 큐를 소개해보려고 한다. 우선순위 큐 키라는 값을 가진 원소들을 다루기 위한 자료구조 보통의 큐는 FIFO를 구현한다. 따라서 우선순위에 상관없이 무조건 먼저 들어온 원소가 가장 먼저 나간다. 하지만 우선순위 큐에서는 우선순위에 따라 나가는 순서가 결정된다. 가장 나중에 들어온 원소이더라도 우선순위가 가장 높다면 가장 먼저 나가게 되는 것이다. 우선순위 큐의 종류 힙과 같이 우선순위 큐에도 최대 우선순..

Big-O-Notation 알고리즘의 속도를 표현하는 방법이다 알고리즘의 속도는 초와 같은 단위로 나타낼 수 없다. 왜냐하면 같은 코드를 실행하더라도 코드를 돌리는 하드웨어에 따라 속도 차이가 천차만별이기 때문이다. 따라서 작업을 수행하는데 걸리는 Step에 따라 속도를 계산한다. Ex) 수행하는데 5개의 스텝이 필요한 알고리즘이 10개의 스텝이 필요한 알고리즘보다 효율적임 코드의 실제 러닝 타임을 표시하는 것이 아니며, 인풋 데이터 증가율에 따른 알고리즘의 성능을 예측하기 위해 사용한다. 실제 러닝 타임을 표시하지 않는 이유는 만약 알고리즘이 4n + 9시간이 걸린다고 가정했을때 n이 10억이라면 이 알고리즘이 돌아가는데는 40억 + 9시간이 걸린다고 말하는 사람은 아무도 없을 것이다. 따라서 Big-..

시작 오늘부터 Introduction to Algorithms에 대한 TIL을 진행하려고 한다. 왜 정렬 알고리즘인가? 수많은 컴퓨터 공학자가 정렬을 알고리즘 연구에서 가장 기본적인 문제로 여기고 있다고 저자는 말한다. 여기에는 몇가지 이유가 있는데 정보를 정렬하는 것 자체가 필요한 응용 분야가 있다. Ex) 은행에서는 고객 청구서를 준비하기 위해 수표를 수표 번호순으로 정렬해야 한다. 많은 알고리즘이 자주 정렬을 사용한다. Ex) 층을 이루는 물체를 그리는 프로그램은 밑바닥부터 꼭대기까지 순서대로 그릴 수 있도록 상하관계에 따라서 정렬해야한다. 정렬 알고리즘은 종류가 다양하고 많은 기술이 적용된다. 힙 힙 자료구조는 완전 이진 트리로 볼 수 있는 배열 객체이다. 완전 이진 트리가 뭐지...? 완전 이진..

알고리즘을 공부하려는 이유 먼저 알고리즘을 공부하려고 마음먹은 계기는 내가 만드는 프로그램들을 유지 보수하면서부터 시작됐다. 나는 전형적인 P이기 때문에 개발을 할 때도 큰 계획 없이 그때그때 구현하고 싶은 기능을 빠르고 생각 없이 구현했다. 이런 식으로 생각 없이 만든 코드가 늘다 보니 여러 문제가 생기게 되었는데... 1. 프로그램의 속도가 느려진다. 별 생각 없이 코드를 짜다 보면 코드의 효율성과 속도는 딱히 신경 쓰지 않고 진행하게 된다. 처음에는 별문제가 없어 보이지만 프로젝트를 완성하고 보면 X 같은 최적화에 엄청난 속도를 보여주는 프로그램을 만날 수 있었다. 2. 내 코드가 왜 작동하는지 모른다. 아무 생각없이 코드를 짜는 나 아무 생각 없이 코드를 작성하다 보니 이 코드가 왜 작동하는지도 ..