132 Pattern 문제 내용 좌측, 우측, 가운데 순으로 숫자의 크기가 결정되는 값이 있는가를 확인 하는 문제이다. 예를 들자면 [3,1,4,2]의 경우 좌측 값 1 우측 값 2일 경우 가운데 4의 값이 가장 큼으로 132패턴을 만족한다. 접근 방법 모든 수를 순회하는 방법이 가장 쉽다. 예를 들자면 왼쪽을 left 오른쪽을 right라고 했을 때, left와 right를 고정하고 가운데를 순회 시키면 된다. 이렇게 되면 left, right full search로 n^2 그리고 가운데 search 횟수 포함해서 $ O(n^3) $ 이 되게 된다. 이것을 최적화 하기위해서 min 값을 관리할 수 있다. 예를 들자면 index 2 값 4일때 min은 1이라는 것을 알 수 있다. left와 right를 ..

문제 내용 숫자로 구성된 Array가 있다. 해당 Array와 동일한 길이의 0으로 채워진 Array가 있을 때 연속된 Sub Array를 1 증가 시킬 수 있다면, 몇번의 Sub Array 증가 Operation이 필요한가? 접근 방법 [1,2,3,2,1] 이 있을 때 우리는 어떻게 계산을 해야하는가? 전체 Array에 1을 한번 채워서 [1,1,1,1,1]을 만들고 다시 중간에 [0,1,1,1,0]을 채우고, 마지막으로 [0,0,1,0,0]을 채우면된다. 그럼 조금더 복잡한 값을 생각해 보자. [3,1,5,4,2]를 계산해 보자. 가장 하단에서 부터 11111을 채우고, 다시 2단에서 10111을 채워 넣어야 한다. 그런데 연속된 Sub Array를 1 증가시키는 Operation만 가능함으로 100..

Regular Expression Matching 문제 내용 s와 p라는 문자열이 주어진다. p는 일반 영문자와 아래 2개의 char로 구성될 수 있다. `.` : 단 한개의 모든 char 종류와 동일하다 `*` : * 직전에 오는 char가 0개 이상 존재 할 수 있다. s와 p가 동일한 문자열이 가능한지 비교하라 접근 방법 가장 쉬운 방법 부터 생각을 해보자 `*` wildcard가 없는 경우를 생각하자. 단순히 왼쪽에서 오른쪽으로 s와 p의 index를 하나씩 움직여 가면서 모든 문자열이 동일한지 확인 하고 만약에 동일하지 않은 것이 나오면 false를 return 하면된다. 주의 해야할 것은 `.`이 모든 문자열을 대치 할 수 있다는 것이다. 그러면 wildcard가 들어간다고 생각해 보자. 이 ..

Basic Calculator 문제 내용 숫자, 더하기, 빼기, 중괄호 '(' ')' 그리고 ' ' 스페이스로만 구성된 계산식을 계산 하시오 풀이 방법 기본적으로 후위연산을 통해서 해당 문제를 푸는게 학교에서 배우는 방법이다. 자세한 내용은 www.programmersought.com/article/93565454512/ 여기를 참고 하면 되는데 간단하게 순서를 설명하자면 아래와 같다. 1. Stack을 2개로 유지한다 2. 1번 Stack은 숫자와 Operand(연산자) 로 이루어진 Stack이다. 3. 2번 Stack은 Operand(연산자)와 '(' 왼쪽 대괄호로 이루어진 Stack이다. 4. 2번 Stack에서 ')' 좌측 대괄호를 만나면 2번 Stack에 있던 Operand를 1번 Stack으로..