2021.04.04 TIL ⏫

무엇이든 꾸준히 하는 것이 가장 중요하다.
그렇다면 그 다음으로 중요한 것은?
주어진 시간을 효율적으로 쓰는게 아닐까?

Problem Solving 🧑🏻‍💻

내 친구같은 동생과 코드리뷰에 관련해서 줌 얘기를 했다. 나는 그동안 그날 그날 해보고 싶은 문제를 풀려고 노력했는데, 그렇게 풀다보니 같은 분류에 있는 다른문제를 볼 때마다 새롭고, 시간이 많이 걸리는 점이 있었다. 이제는 한 문제를 몇 일이고 풀어 볼라고는 하지 않지만 쉽게 다른 분류 문제로 넘어가는 점이 문제였다. 그래서 그 친구가 한 분류에 대해서만 2주간 집중해서 풀어보자고 해서 이번주부터 이분탐색에 대해 공부하기 시작했다. 확실히 한 테마에 중요한 키워드를 알고 풀어보니 다른 문제에도 쉽게 적용할 수 있었고, 이해가 되었다. 오늘은 내가 공부한 이분탐색에 대해 풀어 써 보려고 한다. 훗날 이분탐색에 충분한 이해가 되었다면 시리즈로 알고리즘 분류에 대해 써볼까 한다.

이분탐색 🕵🏻‍♂️

이분탐색이란 무엇일까?
내가 생각하는 이분탐색이란 주어진 답을 찾기위해 주어진 경우 수를 분할하여 빠르게 찾는 것이 아닐까 생각한다. 특히 시간(CPU)에 최적화 라고 생각한다.

이분탐색의 중요 키워드는 시작점,끝점, 그리고 중간점이라고 생각한다. 오름차순의 수를 중간부터 잘라서 정답에 가깝게 푸는 것인데, 빅오로 한다면 O(lgN)이다.

좀 더 자세하게는 나중에 더 공부해서 하나를 포스트 하기로 하고, 오늘은 이 키워드 + Upper/Lower Bound까지 공부했다. 이 키워드 개념을 공부하다보니 2문제를 쉽게 풀 수 있었고, 또 다른 문제는 Upper+Lower를 접목시킨 문제였다. 이 문제를 풀때 사실 처음에는 해쉬값을 생각해서 Dictionary에 접목시켜서 풀어 보았는데 풀리길래, 잠시 생각하다가 이분탐색으로도 접근해서 풀어보았다. 이분탐색으로 풀다보니 정답이 틀려서 해쉬로 푼 것으로 테스트케이스를 만들어 어디가 틀렸는지 반례를 찾을 수 있어서 또 하나의 경험을 얻은 것 같다.

고차함수 reduce

이분 탐색을 공부하면서 고차함수 중 reduce에 대해 좀 더 이해를 할 수 있는 기회였다.

기본적인 사용법은 다음과 같다.

array.reduce(0) { $0 + $1 }

확장하여 $0 과 $1 을 이용해서 많은 함수를 만들 수 있다는 것을 알았다.

trees.reduce(0){$0 + max(0, ($1 - saw))}

또한 함수 body에 한줄만 있을 때는 return도 필요없다는 점과 합치면

func cutLines(by num : Int ) -> Int {
     lines.reduce(0){$0 + $1/num}
 }

위와 같이도 사용할 수 있다.

결론

• 오랫만에 이해를 하면서 공부를 하는 것 같아 기분이 좋았다.
• 코드에 관한 설명이나 정리는 확실히 노션을 쓰는게 다양하고 예쁘다.
• t1이 져서 좀 슬프다.