목록내 개인적인 공부 (60)
그냥 게임개발자
![](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
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/n1sxU/btsGA1dqUTC/IQKolPnsKsijQOVTQdlxkk/img.png)
저번 포스팅에서는 정렬이 되는 컨테이너 map을 사용했다면, 이번에는 정렬이 되지 않은 unorderd_map을 사용할 것입니다. 물론 함수들은 map과 똑같습니다. map과 unordered_map의 차이점은 map unordered_map 정렬 안정렬 균형 이진 검색트리 기반 해시테이블 기반 탐색, 삽입, 삭제 O(logN)이 걸림 탐색, 삽입, 삭제에 평균은 O(1) 최악은 O(N) 이렇습니다. 만약 정렬이 필요하지 않을 때에는 unordered_map을 사용하는 것도 좋지만 최악의 경우는 map보다 느릴 수 있어요. 왠만하면 map을 사용하는 것을 추천합니다. 간단하게 사용해보고 다음으로 넘어가죠 #include #include using namespace std; int main() { unor..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bBlcjo/btsGAfiUsTa/vu39eMySBcocPmtAoGtuJ0/img.png)
map은 C#에서 Dictionary와 같습니다. 고유한 키를 가지며 그 키를 기반으로 key - value 쌍으로 이루어져 있는 정렬된 연관 컨테이너입니다. 균형 이진 검색트리(레드 - 블랙트리)로 구현이 되어있어서, 삽입, 삭제 수정 탐색 시간 복잡도는 O(logN)의 시간 복잡도를 가지게 됩니다. 고유한 키를 가지기 때문에 하나의 키에 중복된 값이 들어갈 수는 없습니다. 또한 자동으로 오름차순으로 정렬이 되기 때문에 넣은 순서대로 탐색이 아니라 ASCII 순서대로 정렬된 값들을 기반으로 탐색하게 됩니다. 참조할 때는 대괄호 연산자 [ ]로 해당 키를 넣어 직접 참조할 수 있습니다. 예를 들어 위에처럼 "The Invisible Man" : 4, "Helen Keller" : 7 이런식의 string..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bqcikl/btsGBNZWhIx/L5V9NTRkR1QVkJ2wSNVwYk/img.png)
배열은 연속된 메모리 공간에 데이터를 저장 연결리스트는 연속되지 않은 메모리 공간에 데이터 저장 배열은 삽입과 삭제에는 O(n)이 걸리고 참조에는 O(1)이 걸립니다. 연결리스튼 삽입과 삭제에는 O(1)이 걸리고 참조에는 O(n)이 걸립니다. 그렇기에 데이터추가나 삭제를 많이 하는 것은 연결 리스트가 좋으며, 그게 아니고 참조를 많이 하는 자료형이 필요하면 배열로 하는 것이 좋습니다. 왜 연결리스트의 삽입삭제가 O(1) O(n)인지에 대한 설명은 따로 포스팅을 해놓았습니다. https://sudoju.tistory.com/218 Linked_List 연결 리스트! 음 연결리스트란 것은 요소들이 서로 인접한 메모리 위치에 저장되지 않는 선형 자료 구조입니다. 한마디로 주변에 서로 없다는 거죠. 랜덤 접근도..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bmSE7v/btsGAKwbLfI/q5hekHCPkRZ0ioOJqCQDT1/img.png)
랜덤접근(Random Access) 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능 순차적 접근 데이터를 저장된 순서대로 검색하는 기능 Vector나 Array 같은 경우 랜덤 접근이 가능해 n번째 요소에 접근할 때는 O(1)이 걸리며, 연결리스트나 스택 큐는 순차적 접근만 가능해 n번째 요소에 접근할 때 O(n)시간이 걸립니다.
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/drpcNI/btsGz1yknDG/lXqKgEVHig8xm5B1MyTVr1/img.png)
연결 리스트! 음 연결리스트란 것은 요소들이 서로 인접한 메모리 위치에 저장되지 않는 선형 자료 구조입니다. 한마디로 주변에 서로 없다는 거죠. 랜덤 접근도 불가능하고 오로지 순차적으로만 접근이 가능해요. 각 요소들을 접근하려면 next, prev라는 포인터로 연결이 되어있고 중복은 가능합니다. 그렇다면 이렇게 하면 장점이 뭘까요? 이는 공간적인 효율성이 좋습니다. 뭐 예를 들어 배열에서 중간 데이터를 삭제한다면 이런식으로 삭제가 되서 다시 재배치가 되겠죠? 하지만 연결리스트는 다릅니다. 삭제를 하면 그 요소의 next와 prev포인터를 변경만 시켜주면 되죠. 삽입 또한 똑같아요. 2번째에 삽입하려면 이 방식으로 삽입하고 다시 재배치 하겠죠. 연결리스트의 삽입은 네 포인터만 바꿔주면 되요. 그래서 삽입과..