HJ Works

4949번: 균형잡힌 세상 (acmicpc.net) 스택 응용 문제 중 하나이다. 어려운 내용은 딱히 없고, ( / [ 가 정상적인 종료인지만 확인하면 된다. 따라서, stack을 간단하게 생각하면 기본적인 구현이 가능하다. 예를 들면, ( -> [ -> ( 로 진입하는 문자열이라면, ) ->] -> ) 로 닫혀야 한다. 즉, 소스코드 작성 시와 동일하다고 보면 된다. 따라서 (, [ 일때 push, ), ] 일때 동일 형태의 input일때만 pop 을 하면 된다. 문제에 함정으로 좀 시간을 쓰게 되었는데, stack 진입을 못 하는 조건에 대한 내용이 히든 케이스로 있다. ), ] 만 사용하는 코너 케이스를 확인하지 못하게 된다. 따라서 이 부분을 처리해 줘야 한다. 즉, 문제에서 주어진 예제는 다 통..

1003번: 피보나치 함수 (acmicpc.net) 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제: 피보나치 함수에서 0, 1이 호출되는 횟수를 구하여라. 제약 조건: 입력하는 숫자는 40이하의 자연수이다. 별 생각 없이 문제에 주어진 fibonacci 함수를 그대로 넣고 0, 1일때 카운트를 했더니 타임아웃이 났다. 피보나치 함수는 매번 나오는 말이지만, 재귀를 얼마나 효율적으로 축소할 수 있는가 를 따지는, DP의 입문격인 문제이다. 그러니 타임아웃이 나는걸 당연하게 생각하고 다시 접근해 봤다. 피보나치 함수는 f(n) = f(n-1)+ f(n-2) 이고, f(n)이 0, 1 이 아닌 경우에 f..