앙박의 기술서

Two-Pointer는 배열같은 자료구조를 효율적으로 탐색하기 위해 두 개의 포인터를 활용하는 알고리즘이다.   보통 O(n^2)을 O(n)으로 단축시킬 수 있고 자료구조 양 끝에서 시작해 중앙으로 향한다. 42. Trapping Rain Water 문제를 가져왔다.  아쉽게도 문제 푸는 도중 우연찮게 해답을 봐버렸다. 여러분은 그런 일 없도록 주의 바란다. n 개의 양수로 이루어진 배열이 주어진다.n 개의 양수는 각각 벽의 높이를 의미한다.n개의 벽으로 이루어진 구조물에 비가 온다면 물은 얼마나 고였을까?  예를 들어, 입력으로 {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}의 배열이 들어왔다고 해보자.  이 배열을 토대로 만든 구조물에는 다음 그림처럼 빗물이 고인다.  그럼 정답은 ..

1-Dimension Dynamic Programming 유형의 문제를 풀어볼 거다.  LeetCode 사이트의 "198.House Robber" 를 가져왔다.  내용은 다음과 같다.1. 일렬로 늘어서 있는 집들을 도둑질 할 거다.2. 붙어 있는 두 집을 연속해서 도둑질 하면 경찰한테 잡힌다.3. 집마다 도둑질할 수 있는 돈이 다르다.4. 경찰한테 안 잡히고 최대한 많은 돈을 얻을 수 있는 방법은?# 예시 입력: {2, 4, 7, 3}   출력: 9입력: {9, 3}           출력: 9   자! 여기서 잠깐 멈추고 먼저 문제를 풀어보자. 위에 문제 링크를 달아놨으니 직접 가서 풀어봐도 된다.  사용할 언어도 자유고 풀이 방법도 자유다.  참고로 나는 C++로 DP를 사용해서 풀었다.  #incl..