이 문제는 2022 카카오 인턴십 코딩 테스트 문제로, 이번에 본 2024 겨울 인턴십 코딩 테스트를 대비하기 위해서 풀었던 문제이다. 처음에 dp 로 시도했다가 테스트 케이스를 다 맞추지 못해서, 다익스트라를 적용해서 간신히 풀어내었다. 다익스트라도 자꾸 시간 초과가 나서 최적화를 하는데 애먹었다. 각각의 접근 방식을 정리해두고 최종적으로 AC 받은 다익스트라 알고리즘의 최적화 방법도 남겨 놓는다. 1. 기본 아이디어 1) 정상에서 다시 입구로 갈때 중복된 간선을 이용해도 되기 때문에, 입구에서 정상까지 가는 단일한 경로만 고려한다. 2) 다른 출발점이나 정상을 경유하는 경로는 고려하지 않는다. 위 두가지 아이디어를 전제로 두고 아래와 같이 알고리즘을 짰다. 2. DP [틀림] 1) 각 출발점에서 df..
전체 글
백준에서 골드 문제를 랜덤으로 돌리던 중 1414번 불우이웃돕기를 만나게 되었다. 한 30 ~ 40분 정도를 고민해서 풀이의 방향은 잡았었는데, 내 생각에 자신이 없어서 결국 풀이를 검색했다. MST(Minimum Spanning Tree) 라는 부류의 문제였고 MST 를 푸는 대표적인 알고리즘 중 하나인 크루스칼 알고리즘이 내 초기 아이디어와 거의 동일한 방법이었다는 것을 알게 되었다. '그냥 내 풀이대로 밀고나가볼걸' 이라는 아쉬움을 느끼긴 했지만, 확신할 수 없는(다시 말해 증명할 수 없는) 직관은 허무할 수 밖에 없다라는 결론에 도달하게 되었다. 크루스칼 알고리즘은 사실 간단하다. 그리디라는 기본 자세를 가지고 가지를 뻗어나가면 되는 것이다. 나 정도의 사람도 직관적으로 떠올릴 수 있는 방법이다...
이전글 [https://techforme.tistory.com/48] 이전글에서 서버를 이중화 하면서 authorization_request_not_found 오류가 나는 상황에 대한 해결책으로 ip hash 방식의 부하분산을 이야기 했었다. 이는 간단한 해결책이긴 했지만, 만약 부하 분산 방식을 round robin 으로 바꾸라는 요구사항이 생긴다면, 전혀 대응할 수 없는 미봉책이었다. (사실 Nginx 를 더 활용해 보고 싶어서 해봤다.) 근본적인 해결책이 필요했다. 이번 게시글에서는 OAuth Authorization 요청 정보를 서버 내부에 저장하지 않고 외부에 저장함으로써, Nginx 의 부하 분산 알고리즘과 상관없이 해당 문제를 해결할 수 있는 방법을 설명한다.1. 문제 상황 분석1) 문제 발..