ki hyun's 개발블로그

힙에 관하여 이전 포스트에서 힙을 이용한 정렬인 힙 정렬에 대해 소개했다. 힙 정렬은 분명 훌륭한 알고리즘이지만 사실 나중에 소개할 퀵 정렬을 잘 구현하는 것이 일반적으로는 더 빠르다. 하지만 힙은 여러 방면으로 유용하게 사용할 수 있는데 이번 포스트에서는 힙을 가장 잘 응용하여 널리 쓰이고 있는 우선순위 큐를 소개해보려고 한다. 우선순위 큐 키라는 값을 가진 원소들을 다루기 위한 자료구조 보통의 큐는 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. 내 코드가 왜 작동하는지 모른다. 아무 생각없이 코드를 짜는 나 아무 생각 없이 코드를 작성하다 보니 이 코드가 왜 작동하는지도 ..