220911 일 Algorithms TIL

프로그래머스 2019 카카오 개발자 겨울 인턴십 징검다리 건너기 lev3

• 문제
• 카카오풀이
• 코드-파이썬
• 코드-자바

O(nlogm)의 방식

• 최대 몇 명까지 강을 건널 수 있는지를 변수로 두고 이를 이분탐색하는 방법이다.
  • x명이라고 가정했을 때 징검다리에 적힌 수에서 x를 뺏을 때 음수가 되면 x번째 애가 건널 때 0인 징검다리 이므로 해당 개수를 센다.

  • 연속된 0인 징검다리 수가 k보다 크거나 같으면, 불가능한 것으로 판단한다. 

• m은 max(징검다리 원소 값, 징검다리 길이)로 두었다.
• 파이썬
• 자바

O(N) 의 방식

• 슬라이딩 윈도를 이용하는 방식이다
• k칸으로 슬라이딩 윈도우 크기를 잡았을 때 해당 윈도우 안에 최대 값이 해당 윈도우를 건널 수 없는 사람의 수다.
• 예를 들어 k칸으로 슬라이딩 윈도우를 잡았을 때, 해당 윈도우 안의 최대값이 3이라고 한다면 3번째 사람은 가능하지만 4번째 사람이 건널라고 한다면 해당 윈도우의 모든 징검다리가 0이 되므로 건널수 없고 k+1만큼 점프를 해야 한는 상황이 생기게 된다.
• 슬라이딩 윈도우를 이동하면서 각 범위의 최대 값을 구하는 문제
• 저번에 풀었던 문제 를 참고해서 슬라이딩 윈도우에서 최대값을 구하는 문제를 해봤다.
• heapq를 이용한 방식 파이썬
• deque를 이용한 방식 파이썬
• ArrayDeque를 이용한 자바 방식

리트코드 122. Best Time to Buy and Sell Stock II

• 파이썬 알고리즘 인터뷰 p590
• 문제
• 코드-파이썬
• 현재값 기준으로 바로 직전의 값이 현재값보다 작다면, 현재값에서 직전 값을 뺀 값을 결과값에 더한다 (현재에 팔고, 직전 인덱스에서 사는 것)
• a - b - c 라고 생각해볼 때 a < b < c라면 result = (b - a) + ( c - b) 이고 (이는 결국 c-a 와 같다)
• a - b - c 라고 생각해볼 때 a > b and b < c and a < c라면 b에서 사서 c에서 파는 것이 제일 나으므로 result = c - b가 된다