수식의 괄호 쌍 많이 나오는 문제는 아닌거 같지만, 전에 봤던 코딩테스트에서 못풀었던 기억이 있어서 공부해봤다. ( ) ( ) ( ) 위와 같은 괄호가 있다면 잘 맞아떨어지는 올바른 괄호의 쌍이다. ( ) ) ( ) 위와 같은 괄호는 가운데 ' ) ' 때문에 쌍이 안맞기 때문에 올바르지 못한 괄호의 쌍이다. 이 문제는 가장 마지막에 담긴 원소랑 비교를 해야하기 때문에 스택을 사용하면 적합하다. 여는 괄호일때는 스택에 Push를 해서 담아주고, 닫는 괄호일때는 스택의 top을 확인해서 쌍이 맞는지 확인해주고 맞으면 Pop해주면 된다. 괄호 쌍이 틀린 조건들 1. 닫는 괄호를 만났는데 스택이 비어있는 경우 (여는 괄호가 앞에 없었다는 뜻) 2. 닫는 괄호를 만났는데 짝이 안맞는 경우( 닫는 괄호로 대괄호를 ..

덱(Deque) - 양쪽끝에서 삽입/삭제가 가능한 자료구조 - 큐,스택,덱을 합쳐서 Restricted Structure라고 부름. - Deque / Double Ended Queue라는 뜻을 가지고 있다. - 원소의 추가/제거 O(1) - 제일 앞/뒤의 원소 확인이 O(1) C++ STL - Deque Deque의 문서를 보면 앞쪽에 원소를 추가/제거 할 수 있다는 것만 빼면 Vector와 상당히 유사한것을 알 수 있다. 자료구조의 Deque은 앞/뒤가 아니면 확인이 불가능하지만 STL의 Deque는 인덱스로도 접근이 가능하다. C++ stl vector vs deque 를 검색하면 많은 글들이 나오니 차이점들은 나중에 파보기로 하고, 코테에서 Vector와 deque중에 어떤걸 쓸지 판단하는 기준은 ..

큐(Queue) - 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄수있는 자료구조 (FIFO : First In First Out, 은행에서 번호표를 뽑고 기다리리는 것을 생각하면 편함) -추가되는 곳은 Rear / 제거되는곳은 front - 원소의 추가/제거 O(1) - 제일 앞/뒤 원소확인 O(1) - 앞/뒤가 아닌 원소의 확인 변경x C++ STL - Queue C++의 STL에서도 역시 Queue를 제공한다. 코테에서는 따로 구현할 필요 없이 헤더파일을 포함시켜 사용하면 된다. int main() { queue Q; Q.push(2); // 원소 삽입 2 Q.push(3); // 원소 삽입 3 if (!Q.empty()) //큐가 비어있는지 확인 후 제일 앞의 원소(2) 출력 cout > n; ..

스택(Stack) - 끝에서만 원소를 넣거나 빼는 자료구조 - 먼저들어간 원소가 나중에 나옴 (FILO : First In Last Out / 프링글스 통을 생각하면 편함) - 최상단(top) 원소의 추가/제거/확인의 시간복잡도는 O(1) - 다른 원소의 확인/변경은 불가능함. STL - Stack #include #include using namespace std; int main(void) { stack myStack; //스택에 원소 1을 삽입 myStack.push(1); //스택에 원소가 있다면 최상단의 원소를 출력 if (!myStack.empty()) cout

연결리스트 - 원소를 저장할때 그 다음 원소의 위치를 포함하는 방식으로 저장하는 자료구조 - 원소들은 흩어져 있음 성질 1. k번째 원소를 확인/변경 하기 위해서는 O(k)의 시간복잡도가 필요.(원소들을 타고 가야 하기 때문) 2. 임의의 위치에 원소 추가/제거를 하기위한 시간복잡도는 O(1)임. 3. 연속되어 있지 않아서 Cache Hit rate가 낮지만 할당이 다소 쉬움. 종류 단일 연결리스트 - 다음 원소의 주소 하나만 들고 있는 연결리스트 이중 연결리스트 - 이전,다음원소의 주소를 전부 들고있는 연결리스트 - 주소를 저장할 곳이 하나 더 필요하기 때문에 메모리를 더 씀 - STL의 list가 이중 연결리스트의 구조로 구현이 되어있음 원형 연결리스트 - 끝이 처음와 연결되어있는 연결리스트 연결리스..

배열 배열은 메모리상에 원소를 연속하게 배치한 자료구조이다. 1. 데이터의 크기를 정해놓기 때문에 추가적으로 소모되는 메모리의 양이 거의 없다. 2. Cache Hit Rate가 높다고 하는데 뭔지 몰라서 찾아봤다. 자주 사용하는 데이터를 빠르게 가져올 수 있는 캐시 메모리에서 원하는 데이터를 가져오려고 할때 그 데이터가 캐시에 존재할 때 Cache hit 이라고 한다. Cache Hit Rate = Cache hit 횟수 / 총 참조 횟수 깊게 파고들면 끝도 없겠지만 배열은 원소를 메모리상에 연속하게 배치하기 때문에 캐시 적중률이 높다고 한다. 3. 메모리상에 연속한 구간을 잡아야하기 때문에 할당에 제약이 있음 배열을 사용할때 시간복잡도 배열은 연속한 메모리 공간에서 인덱스로 접근 가능하기 때문에, 원..