본문 바로가기

STL

 (6)
Stack과 Queue의 차이 차이 스택은 선입후출(FILO/LIFO), 큐는 선입선출(FIFO)이다. 용도 스택 : DFS 알고리즘, 퀵 소트 큐 : BFS 알고리즘(특히 A*) 그 외에는 게임 개발하는 동안 사용한 적이 없는 것같다.. 단점 스택 : 스택 오버플로우를 주의해야한다. 큐 : 큐에 빈 메모리가 남아 있어도 rear가 배열의 끝에 도달했을 경우 꽉 차있는것으로 판단할 수 있다.
데이터를 찾을 때 hash와 array 어떤게 더 빠를까 인덱스를 아는 경우와모든 데이터를 순차적으로 접근하는 경우에는 array가 빠르다. array와 hash 모두 O(1)이지만 array는 hash function을 거치지 않기 때문에 hash보다 더 빠르다. key를 찾는 경우에는 hash가 빠르다. hash의 경우 O(1)이지만 array는 key 값의 개념이 없어 순차탐색하므로 O(N)이 된다.
hash를 사용하는 경우 1. 많은 자료를 저장하고, 검색 속도가 빨라야하는 경우 2. 너무 빈번하게 자료를 삽입, 삭제하지 않는 경우 해쉬는 테이블에 자료를 저장할때 키값을 해시 함수에 대입하여 버킷 번호가 나오면 그 버킷의 빈 슬롯에 자료를 저장하는 자료구조이다. 버킷 번호에 자료를 넣기 때문에 많은 자료를 저장해도 삽입, 삭제, 검색 속도가 거의 일정하다. Key 값 → 해쉬 함수에 대입 → 버킷 번호 출력 장점 : 많은 자료를 저장하고 있어도 검색이 빠름, 단점 : 적은 자료를 저장하는 경우 메모리 낭비와 검색 시 오버헤드가 발생함 많은 양의 자료를 저장하는 경우 해쉬를 사용하고, 적은 양이라면 리스트가 벡터가 낫다. 참고 https://gamdekong.tistory.com/73
list와 vector의 차이 기술 면접 때 나온 질문은 아니지만 복습하면 좋을 것 같아서 정리해봅니다. 1. 중간 데이터 삭제 시 벡터 - 해당 원소 뒤의 원소들을 모두 한 칸씩 앞으로 이동하는 작업을 수행하므로 속도가 느리다. 리스트 - 해당 원소의 앞 뒤의 노드들을 상호 연결하는 과정만 수행하므로 속도가 빠르다. 2. 메모리 저장 위치 벡터 - 메모리의 한 공간에 연속적으로 값이 할당된다. 리스트 - 메모리의 여러 부분에 값이 할당되고 포인터로 서로를 연결하는 구조이다. 3. 랜덤 접근 벡터 - 해당 위치에 바로 접근할 수 있다. 리스트 - 반복문으로 해당 원소가 있는 위치까지 순차 접근을 해야한다. 공통점 1. 크기 변경 가능 2. 순차 접근 가능
int array와 vector의 차이 1. 길이의 고정 여부 배열의 경우, 정의와 동시에 길이를 지정하며 고정되어있다. /* 정적 할당하는 경우 */ int array[3] = {0};// 3이라는 크기를 지정했다 /* 동적 할당하는 경우 */ int array[] = new int[5];// 마찬가지로 크기를 정해주어야한다 벡터의 경우, 사용자가 계속해서 원소를 추가하거나, 삭제하여 길이를 조절할 수 있다. vector myvector(2);// 크기를 할당할 수 있다 myvector.push_back(1); myvector.push_front(2); myvector.push_back(5);// 크기는 이제 3으로 늘어났다 2. 중간 값 삭제 시 배열의 경우, 값을 삭제하더라도 해당 인덱스의 공간은 빈 공간으로 남아있다. 벡터의 경우, 값..
int array와 list의 차이 1. 길이의 고정 여부 배열의 경우, 정의와 동시에 길이를 지정하며 고정되어있다. /* 정적 할당하는 경우 */ int array[3] = {0};// 3이라는 크기를 지정했다 /* 동적 할당하는 경우 */ int array[] = new int[5];// 마찬가지로 크기를 정해주어야한다 리스트의 경우, 사용자가 계속해서 원소를 추가하거나, 삭제하여 길이를 조절할 수 있다. list mylist;// 아직 크기 정하지 않음! mylist.push_front(5);// 현재 크기 1 mylist.push_back(3);// 현재 크기 2 mylist.pop_front();// 현재 크기 1 2. 중간 값 삭제 시 배열의 경우, 값을 삭제하더라도 해당 인덱스의 공간은 빈 공간으로 남아있다. 리스트의 경우, ..

티스토리툴바