Algorithm

매일 아침에 푸는 알고리즘에서 시작했다. 문제를 쓱 훑어보고 씻고 밥을 먹으면서 로직이 떠오르고 풀기 시작했다. 그리고 왜 안돼? 고통받은지 3일만에 에러를 잡았다. 3일 내내 코딩하진 않았지만 계속 마음 속 짐처럼 나를 괴롭혔다. 다 풀린 것 같은데 왜 안되는걸까?

조금 해맸던 문제라서 기록한다. 네비게이터 역할로 잘 풀었던 문제인데 직접 코딩하려니 머리가 멍해지는 경험을 했다. 조건에 걸릴 경우 Recursive Case 구상에서 햇갈렸던 것으로 보인다. 배열을 head와 tail로 나눈다. head에서 조건을 확인한다.

자바스크립트에서 최대 함수 호출 횟수를 구하는 코드. 재귀 구현할 때 참조하기 좋다. 코플릿에서 얼추 11000정도에 끝나고 크롬에서 9800회 정도에서 끝난다.

순열과 조합에 대해서 배우면서 반복문을 통한 구현부터 재귀를 통한 구현까지 익혔다. 그 중 활용도가 가장 높고 가장 난해한 재귀에 대해서 정리하는 글을 남긴다. 처음 이 코드와 설명을 봤을 때 이해하기가 굉장히 어려웠다.

스스로 시도하는 것도 좋지만 좌절할 정도로 어려운 문제는 답을 보는게 좋다. 답을 보더라도 설명할 수 있게 이해한다면 그걸로 괜찮다.

메모이제이션, 동적 프로그래밍의 기초같은 문제다. 처음 이 문제를 접하고 당황했다.무엇을 위해서, 어떤 해결 방안을 위해서 이런 동작이 생겼나 짚어보았다. 그 다음 코드를 한 줄씩 다시 써보면서 주석을 달았다.

비교적 앞부분에 만난 문제지만 정말 어려웠다. 이진탐색에 대한 깊은 이해가 없으면 푸는게 불가능하다. 수료한 이후 다시 보더라도 어려운 것은 마찬가지더라.

같은 탐색 알고리즘이지만 우선순위가 달라서 특정 상황에서 더 효율적인 경우가 있다.

정말 간단해보였다. 부등호 양 옆에 숫자만 잘 끼워넣으면 끝 아닌가? 한 번의 연산으로 풀리는 최적의 계산법이 있을 것이다. 이 예상은 보기좋게 빗나갔다.가장 큰 수를 찾을 때, 부등호 방향에 따라서 들어갈 수 있는 숫자가 달라진다. 이전에 포스팅한 스도쿠처럼,

가벼운 마음으로 들어갔다가 한 방 먹은 문제였다. 탐욕법을 집중적으로 공부하다가 만난 문제였다. 탐욕법이 얼핏 보기엔 쉬워보이는데 찬찬히 풀다보면 전혀 그렇지가 않다. 공식 같은 정해져있는 패턴이 있는게 아니라서 더 그런가.

요즘 탐욕법을 중점적으로 공부하고 있다. 카테고리에서 탐욕법이라고 쓰여있으면 무작정 풀고 본다. 사실 이전에 알고리즘 공부를 열심히 한 적 있는데, 그 때 만났던 최소 신장 트리 문제를 다시 만났다.

탐욕법을 풀다가 만난 흥미로운 문제다. 다양한 해결 방법이 있었는데, 효율이 가장 좋게 나오는 방식을 찾다가 흥미로워서 포스팅하려고 한다. 처음엔 정확히 어느 지점에 단속 카메라를 배치하려고 시도했다.

Heap으로 구현해야 된다. Heap 문제인데 Heap으로 풀면 효율성은 개선되지만 문제 푸는 시간이 부족하다니 아이러니하다.

2021 카카오 문제 중 하나다. 레벨 2라고 되어있는데 전혀 2같지가 않다. 하나의 문제에 두 개의 알고리즘을 적용해야 풀린다. 하나 하나는 레벨2라고 생각하면 납득이 가...나? 어려웠다. 특히 검색은 효율성이 높은 이분탐색을 사용해야 된다.

이분탐색의 핵심은 먼저 답을 정해놓고 그 답이 맞는지 찾아나간다.

JSON.parse(JSON.stringify(originalArray))