근진이의 알고리즘 시간

이 문제는 사실 예전에 본적이 있다.

먼 과거긴 하지만 수많은 노가다를 통해 일종의 인식기를 만들어서 풀었고 심지어 답도 맞췄다.

요즘 말로하면 "어케 맞췄노" 정도 되겠다.

각설하고 문제를 분석하면, 쉽게 말해 Stack을 통한 인식기를 만들라는 것이다.

원리는 간단하다.  "("가 나오면 push하고 ")"가 나오면 pop한다.

몇 번째 "("가 ")"와 짝인진 사실 알기 힘들다. 하지만 명백한 사실은, 스택에 "(" 가 남아있다면 ")"이 부족하단 것이다.

단, 낮은 정답률에서 알 수 있다시피 그게 다가 아니다. 조심해야할 예외가 있다.

코드는 아래와 같다.

자료구조를 매번 직접 구현해서 푸는 건 거의 불가능에 가깝다.

C style로 풀더라도 STL을 사용하면 좀더 빠른 구현이 가능하니까 익숙해지도록 하자.

Stack : 10828번 (http://boj.kr/d9375b2a95744c15836b94b588c425cc)

Queue : 10845번 (http://boj.kr/9412f140024348dca6c335e71c60a8a9)

Deque : 10866번 (http://boj.kr/c196f255fb8046d78444fcf52816a9e5)

Priority queue : 11279번 (http://boj.kr/26fffbf3bd8647ef82c268b593c11f25)

자료구조를 한번에 다루다 보니까 소스코드를 직접 올릴 수 없어 코드로 대체한다.

대체로 주어진 구현해야하는 커맨드는 위와 같다. 소소한 차이는 있지만, 크게 벗어 나지 않는다.

네 자료구조 모두 비어있는 상태에서 pop()을 시도하거나 값을 가져오려고하면 메모리 접근 관련된 런타임 에러가 난다는 것을 감안해서 프로그램을 작성 해야한다. 문제에서 pop()에 관한 조항이 있으니 실수로라도 놓지지 말고 반드시 확인하도록 하자.

또한, cin, cout이 시간을 많이 쓰므로, Priority queue에선 시간 초과가 난다는 점을 조심해야 한다.

Java가 아니라 C++로 문제를 푸는 사람들은 입력시 " "(공백문자)를 어떻게 처리 해야할지 난감할 때가 있다.

"push_front 1" 같은 입력은 띄어쓰기 때문에 cin으로는 원하는 입력을 얻을 수 없다. 

std::getline()을 이용하여 입력받고, 입력받은 op를 stringstream에 넣어 스트림으로서 하나씩 꺼내 쓸 수 있어,

사실상 split()을 한 것과 비슷한 효과를 얻을 수 있다.

상반기에 코딩테스트를 보러 역삼에 갔었지만

흠씬 두들겨 맞고 돌아왔다.

서류는 자신있으니, 실력을 길러 합격하도록 하자!

우선 삼성에서 광탈한 후 나의 현실을 먼저 파악해보니 기본적으로 내 실력이 형편 없단 걸 깨달았다.

이론이야 알지만, 시간 복잡도를 계산하거나 문제 해결을 위한 계획하는 게 엉망이었다.

손이 펜보다 프로젝트 만들기에 먼저가니  문제가 풀릴리가 있나.

백준(https://www.acmicpc.net/step)에서 우선 구현 위주의 문제를 먼저 풀어보고

자료구조, 시뮬레이션, 동적계획법, 브루트포스. 그래프 위주로 문제를 풀 것 이다. 이 일을 7월 중에 마칠 수 있도록 노력해야겠다.

이 일을 7월 중에 마치고, 8월 부턴 SWEA(https://www.swexpertacademy.com)에서 문제를 풀며 삼성 특유의 스토리텔링에 익숙해지도록 할 것이다.

또한 고생해서 풀었거나 인상이 깊은 문제들은 이곳에 올리어 정리할 생각이다.

사실 시작은 7월 첫째주에 했는데, 블로그에 강해지는 모습을 기록해야겠단 생각이 들어서 뒤늦게 글로서 정리한다.