목록내 개인적인 공부/자료구조 (28)
그냥 게임개발자
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/biXx9x/btsGAM8Tdsj/abUaGtHvNCAvYQkALQszlk/img.png)
우선순위 큐! 이게 무슨 말이냐면요 우선순위를 넣을 수 있는 큐에요! 끄읕 아 진짴ㅋㅋㅋㅋㅋ 갑자기 피곤해서 글 쓰는게 귀찮아졌어요...ㅋㅋㅋ 제대로 설명을 드리자면 큐에 요소를 하나씩 담는데 우선순위를 부여할 수 있는 컨테이너를 말해요. 이렇게 큐에 요소들이 담겨있는데 9가 우선순위로 부여가 되어있어 우선순위가 낮은 요소보다 먼저 제공이 된다는 것이죠. 만약에 두 요소의 우선순위가 같으면 대기열에 포함된 순서에 따라 제공이 됩니다. 또 만약에 동일한 우선순위를 가지고 있는데 요소의 순서는 어떻게 정의가 되냐면 정의되지 않습니다. 그대로 유지에요. 우선순위 큐는 FIFO형태가 아닌 우선순위가 높은 요소가 먼저 나가는거에요. 우선순위 큐는 Heap을 통해 구현이 되는데요. 힙(Heap)? 힙은 우선순위 큐..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cgDnMX/btsGBvMgTAf/EwAHrlkS4tQT7VbRUtyjP0/img.png)
vector에 struct라는 타입을 넣고 정렬을 한 번 해보겠습니다. 참 구조체가 할 게 많아요. 좋은 애들.. 힘냅시다! #include #include using namespace std; struct point { int y, x; } bool Compare(const Point& a, const Point& b) { return a.x > b.x; } int main() { vector vec; for (int i = 10; i >= 1; --i) { vec.push_back( { i, 10 - i } ); } sort(vec.begin(), vec.end(), Compare); for (auto it : vec) { cout
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bt1Omo/btsGBfWXsPI/AxenHblavZUECunOTDxGS1/img.png)
구조체! C배우면서 많이들 보셨을 겁니다. 커스텀하게 데이터를 만들 수 있는 자료구조를 의미하는데, 아래 사진을 봐보죠. C에서 struct는 structure tag를 달아서 사용합니다. 그 안에는 멤버 구조들이 짜여져있습니다. 멤버 변수들이 있다는 것이죠. 멤버 변수라는 것은 클래스나 구조체 내부의 변수를 뜻합니다. 한번 만들어봅시다. #incldue using namespace std; struct Santos { int a, b; double c, d, e; }; void print(Santos santos) { cout
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/UwcsV/btsGDBxwEWH/qbKM3CXDn6yWVRKySv9wd1/img.png)
앞서 설명한 queue는 앞에서만 끄집어낼 수 있다면? 이것은 앞뒤로 삽입, 삭제, 참조가 가능한 자료구조입니다. 그 그림 보면 잘 이해가 안갈수도 있는데 Insertion : 삽입 Deletion : 삭제 양쪽에서 삽입 삭제가 가능하다는 소리입니다. 코드로 확인해보죠. #include #include using namespace std; int main() { deque dq; dq.push_front(1); dq.push_back(2); dq.push_back(3); cout
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/k15Tp/btsGDLz6DcT/HM8ajEvOWnMejBgQUP5yvk/img.png)
큐 많이 들어봤을 것입니다. FIFO 피포피포 선입선출(FIFO, First In First Out)성질을 가진 자료구조입니다. 나중에 집어넣은 데이터가 먼저 나오는 Stack과는 반대가 되는 자료구조 하지만 이 또한 삽입 및 삭제에 O(1), 탐색에 O(N)이 걸립니다. 그림을 보듯이 먼저넣은 데이터가 먼저 나옵니다. 잠깐 코드를 사용해보도록 하죠. #incldue #include using namespace std; int main() { queue que; for (int i = 0; i < 10; ++i) { que.push(i); } while (que.size()) { cout
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/UNNbh/btsGDzzGxFJ/mQjvZ4x9DQLLxLtw4S2CS1/img.png)
스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질인 LIFO(Last in First Out)을 가진 자료구조 그 유명한 후입선출이다. 마지막으로 들어온 애들이 처음으로 나온다. 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰인다. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸립니다. 탐색에 O(n)이 걸리는 이유는 n번째 요소를 찾는다고 하면 그 이전에 들어있던 요소들을 거쳐서 찾아야 하기 때문이다. 순회를 하는거죠. 그 과정을 n번 반복해야 찾을 수 있기 때문에 O(n)이 걸립니다. LIFO, 가장 마지막으로 들어간 데이터가 가장 첫번째로 나오는 구조를 지녔습니다. 코드로 확인해볼까요? #include #include using namespace std; sta..
우리는 unique를 알고 있습니다. unique는 중복된 요소를 제거하는 함수입니다. set을 통해서도 애초에 중복을 방지할 수 있는데, 뭐가 더 좋을까요? 성능만 따지자면 unique나 erase를 통한 것이 set보다 더 효율적입니다. 예를 들어봅시다. 중복된 vector가 있다고 생각합시다. 1. 중복된 배열 vector가 생성 2. set을 사용해서 중복제거 3. 다시 새로운 vector를 만들어서 옮김 그렇다면 여기서 vector와 set의 컨테이너가 2개 더 만들어지는 것을 볼 수 있네요. 그런데 unique와 erase는 그냥 해당 중복된 배열의 vector를 기반으로 사용할 수 있다는 장점이 있죠. 이거는 나중에 테스트 해보도록합시다. 일단 확실한건 set으로 중복제거 하는 것보다 uni..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/dbq0sg/btsGBy9DXsr/CxaKcwNNvavITejl1IvWhK/img.png)
set 고유한 요소만 저장하는 컨테이너 또한 set은 중복을 허용하지 않습니다. map처럼 key - value 쌍으로 넣지 않아도 되며, 여러가지 형태로 넣어도 됩니다. 중복된 값은 제거가 되고 map과 같이 자동 정렬이 됩니다.(오름차순) 함수는 map과 같아요. #include #include using namespace std; int main() { set st; st.insert(pair("Santos", 1)); st.insert(pair("Santos", 1)); cout