1. 수식의 괄호 쌍이란? 수식의 괄호 쌍 - 말 그대로 수식의 괄호 쌍을 의미하며 주어진 괄호 문자열이 올바른지 판단하는 문제이다. 2. 문제 해결을 위한 관찰 괄호 문자열이 올바른지 아닌지 판단하는 방법 중 가장 보편적인 방법은 바로 안쪽부터 짝맞추기를 해서 지워나가는 방법이다. 다 짝이 맞으면 올바른 괄호 쌍인거고 그렇지 않으면 올바르지 않은 괄호 쌍입니다. +) ) 의 갯수가 ( 의 갯수를 넘지 않으면 된다. 그런데 괄호가 여러 종류일 때에는 여는 괄호의 갯수와 닫는 괄호의 갯수 만으로는 해결이 되지 않는다. 예를 들어 ({}), ({)}라는 두 괄호 문자열을 생각해보면 첫 번째는 올바르고 두 번째는 올바르지 않다. 그런데 둘 다 ) 의 갯수가 ( 을 넘은 적도 없고, } 의 갯수가 { 을 넘은 ..

1. 정의와 성질 덱 - 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조 덱은 Restricted Structure의 끝판왕과 같은 느낌의 자료구조인데, 양쪽 끝에서 삽입과 삭제가 전부 가능하다. 자료구조의 덱은 deque고 Double Ended Queue라는 뜻을 가진다. 덱은 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조로 스택과 큐를 덱의 특수한 경우이다. 덱의 성질 1. 원소의 추가 - O(1) 2. 원소의 제거 - O(1) 3. 제일 앞/뒤의 원소 확인 - O(1) 4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능. 그리고 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능한데 독특하게도 STL deque에서는 인덱스로 원소에 접근할 수 있다. STL st..

1. 정의와 성질 큐 - 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조 스택에서는 먼저 들어간 원소가 나중에 나왔는데 큐에서는 먼저 들어간 원소가 먼저 나오게 된다. 스택은 FILO(First In Last Out), 큐는 FIFO(First in First Out)이다. 큐의 성질 1. 원소의 추가 - O(1) 2. 원소의 제거 - O(1) 3. 제일 앞/뒤의 원소 확인 - O(1) 4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능. 스택에서는 보통 원소가 추가되고 제거되는 곳을 top이라고 부르고, 원소가 위 아래로 배치된 것으로 생각을 많이 하는데 큐에서는 추가되는 곳을 rear, 즉 뒤쪽이라고 하고 제거되는 쪽을 front, 즉 앞쪽이라고 한다. 스택과 ..

1. 정의와 성질 스택 - 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조 먼저 들어간 원소가 제일 나중에 나오는 FILO(First In Last Out) 자료구조이다. +) 참고로 큐나 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있어 스택, 큐, 덱을 묶어서 Restricted Structure라고 부르기도 한다. 스택의 성질 1. 원소의 추가 - O(1) 2. 원소의 제거 - O(1) 3. 제일 상단의 원소 확인 - O(1) 4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능. 원칙적으로 불가능하다는 뜻을 잘 이해할 필요가 있는데, 원래 스택이라는 자료구조는 원소의 추가/제거/제일 상단의 원소 확인이라는 기능만 제공하는 자료구조이다. 제일 상단이 아닌 나..