오늘의 주제는 '우선순위 큐'이다. 이는 내부적으로 '힙(Heap)' 자료구조를 구현하고 있기 때문에 함께 익혀보도록 하자. 또한 우선순위 큐를 활용한 프로그래밍 문제를 풀어보며 응용하는 시간도 가져보자. Priority Queue란? C++의 컨테이너 어댑터인 priority queue는 큐의 원소 중 가장 큰 값을 우선 순위로 두고 오름 차순으로 원소들을 배열하는 큐의 한 종류이다. 어떤 원소의 삽입(push)나 삭제(pop)가 발생할 경우 큐의 우선순위에 맞추어 정렬한다. 자료구조 Heap으로 구현되었기에 push에 의한 정렬은 O(logN)의 시간 복잡도를 가진다. 사용법과 기본 매서드는 아래와 같다. 1. priority_queue 선언 헤더 파일를 include 해준다: #include pq;..
[Python] 자료구조 탐색하기 : 리스트[List] / 튜플(Tuple) / 셋{Set}
1. 리스트 [ List ]★★★★★ - 리스트는 항목(item)들을 저장하는 컨테이너로서 그 안에 항목들이 '순서를 가지고' 저장된다. - 자동으로 늘어나고 줄어든다. (memory allocation/dealloaction) - 리스트는 어떤 타입의 항목이라도 저장할 수 있다. - 인덱스(index)를 통해 리스트의 위치를 알 수 있고, 접근할 수 있다. 1) 기본 선언 aList= ['p', 'y', 't' , 'h', 'o', 'n'] 파이썬 내부적으로 리스트를 선언했을 때, 아래와 같이 메모리가 할당되고, 리스트 이름이 리스트가 할당된 메모리를 가리키는 형태이다. 2) 인덱스 활용 - 인덱스를 이용해 리스트 특정 위치에 접근해 해당 값을 불러올 수 있고, 혹은 해당 위치에 원하는 값을 대입할 수..
[완전 탐색 알고리즘]은 무엇일까? '완전 탐색 알고리즘'은 이름에서 알 수 있듯 답을 찾기 위해 모든 상황을 다 계산하여 답을 찾도록 구현하는 알고리즘으로 시간이 가장 오래 걸리는 방법이지만, 가장 정확한 답을 찾을 수 있다. 완전 탐색 알고리즘을 풀 때, 'for 문'을 사용하면 금방 해결의 실마리를 찾아낼 수 있지만 for문을 얼마나 체계적으로, 효과적으로 짜느냐가 중요한 관건이다. 완전 탐색 알고리즘의 시간 복잡도는 for문이 얼마나 중첩되어 있느냐에 따라서 크게 다른데 for문이 x개 중첩되면 시간 복잡도가 n의 x제곱이 되는 만큼 시간 복잡도가 매우 크다. 완전 탐색을 사용해야 하는 두 문제를 리뷰해보면서 해당 알고리즘에 대해 파고들어 보자. 백준 2309번: 난이도 下 문제 설명: 왕비를 피..
스마트 포인터, 왜 사용하는 걸까? C언어로 개발을 하다 보면 new를 사용해서 메모리를 동적으로 할당받아 사용해야 하는 경우를 많이 볼 수 있다. 이때, 주의해야 할 점은 메모리를 할당받을 경우, 사용 후 반드시 Delete 해줘야 하는 것인데, 그렇지 않을 경우 '메모리 누수(Memory Leak)'가 발생하여 메모리를 낭비하게 된다. 그래서 최신 C++에서는 사용자가 메모리를 관리해야 하는 번거로움을 줄이고, 메모리/리소스 누수와 예외 안전성을 보장하기 위해 포인터처럼 동작하는 클래스 템플릿, '스마트 포인터'를 도입했다. 간단히 말하자면 스마트 포인터는 사용이 끝난 메모리를 자동으로 해제해준다. 스마트 포인터, 어떻게 사용하면 될까? 우선, 스마트 포인터는 세 가지 종류가 있다. 이들에 대해 각각..