무작위로 N개의 수가 들어있는 리스트가 있다고 하자. 이 안에 특정 수 x가 들어있는지 찾는 최적의 알고리즘은 무엇일까? 이런 류의 문제를 탐색(searching)문제라고 한다. 탐색 문제에는 크게 세 가지 알고리즘이 있다. 선형 탐색(linear searching) 복잡도 : O(N) 선형 탐색은 N개의 수를 하나씩 차례대로 x인지 비교하는 방법이다. 이는 가장 간단한 알고리즘이지만 N이 커질 때 복잡도가 크게 늘어난다. 파이썬의 in 연산자가 선형 탐색을 이용한다. 이진 탐색(binary searching) 복잡도 : O(logN) 정렬된 리스트에서 사용 가능한 알고리즘으로, 아래의 순서로 진행된다. 리스트의 중간 인덱스를 잡고, 해당 인덱스의 값을 x와 비교하여 같으면 종료한다. 다르다면, 크기를 ..

스택 구조란, 쌓여 있는(stack) 더미처럼 된 자료구조를 말한다. 그림처럼 쌓은 수건을 위에서부터 사용하면서, 빨래한 새 수건을 다시 위에 쌓으면 아래 있는 수건은 계속 안 써서 먼지가 쌓인다. 이 구조가 스택 구조이다. 스택 구조는 나중에 들어온 데이터가 먼저 나가는 LIFO(Last In, First Out) 구조이다. 또한, 스택에 데이터를 넣는 것을 push, 데이터를 (위에서) 빼는 것을 pop이라고 한다. 백준 9012번: 괄호 백준 9012번(괄호)는 스택 문제의 대표적인 유형이다. 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid..