c++

[C/C++] 백준 7576번

문제출처: https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net [ 문제 ] 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익..

[자료구조/C++] 해시 테이블(hash table)과 체이닝(chaining) - vector와 list로 구현

[ 1 ] 해시 테이블(hash table)이 필요한 이유 옥스포드 영어 사전에는 약 170,000개의 단어가 수록되어 있다고 한다. 이 사전에서 하나의 단어를 탐색하는데 시간 복잡도가 O(n)인 선형 탐색을 활용한다면 오랜 시간이 걸릴 것이다. 이를 해결하기 위해 AVL Tree나 Red-Black Tree처럼 트리의 높이를 O(log n)으로 유지하는 자료구조를 활용한다면 선형 탐색보다 그 검색 시간을 유의미하게 줄일 수 있을 것이다. 하지만, 데이터의 수가 증가하거나 탐색 횟수가 크게 증가할 경우 O(log n)의 속도도 만족스럽지 못할 수도 있기 때문에 우리는 더욱 효율적인 데이터 저장 - 탐색을 위한 자료구조를 떠올려야 한다. 이때 해시 테이블(hash table)이 효율적이고 효과적인 자료구조..

[자료구조/C++] 맵(map)

[ 1 ] 기본내용 map은 기본적으로 entry라고 불리는 (key, value)쌍이 저장되는 자료구조이다. 하나의 map은 중복된 key값을 가질 수 없다는 특성과 key값으로 해당 key값과 mapping된 value를 쉽게 검색할 수 있는 특성으로 인해 정보 저장 및 검색에 유리한 자료구조이다. 대표적인 map의 특성은 다음과 같다. - map은 중복된 key값을 가질 수 없기 때문에 하나의 key가 여러 개의 value값을 가질 수 없다. - map의 주요 연산으로는 search, insert, erase가 있다. - map을 연결리스트로 구현할 경우 위의 주요 연산의 시간복잡도는 O(n)이다. - map 연산의 시간복잡도를 줄이기 위해 hash map 등을 활용하기도 한다. [ 2 ] C++에..

[자료구조/C++] 우선순위 큐

[ 1 ] 기본내용 우선순위 큐(Priority Queue)란 First-In First-Out(FIFO) 구조를 따르는 일반적인 큐와 달리 힙(heap)을 활용하여 원소들의 우선순위를 설정하고, 우선순위에 따라 가장 작은(또는 가장 큰) 원소에 빠르게 접근할 수 있는 자료구조이다. 단, 최대 or 최소 둘 중 하나에 대해서만 우선순위를 적용할 수 있으며 최댓값을 우선순위로 둘 경우 최대 힙(Max heap), 최솟값을 우선순위로 둘 경우 최소 힙(Min heap)이라 한다. [ 2 ] C++에서의 우선순위 큐 [ 2 -1 ] 헤더파일 C++에서는 container adaptor로서 priority_queue를 제공하고 있으며, vector를 기본 컨테이너로 사용한다. priority_queue를 사용하..