가장 먼 노드 문제는 노드로 주어지는 상황속에서 1부터 n까지의 관계 안에 가장 먼 노드를 찾는 문제이다. 즉, 위와 같은 모형이 주어지면 가장 먼노드인 5, 4, 6 의 개수 3을 return하면 된다. 우선 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 둘 중 어느 방식을 선택할 것인가에 대해 생각이 필요해보였다. 가장 먼 노드를 따져본다고 했을 때 가정을 해보았다. 그랬더니 순서가 대충 이렇게 나올 것 같다. 1 - 2 - 5(return) - 4 - 3(?) - 6 ... 어떻게 순서를 잡냐에 따라 다르겠지만 4에서 3으로 가는게 말이 될까? 2에서 이웃한 노드도 사실 상 3, 4, 5이기 때문에 2 - 3으로의 순서도 고려해볼 필요가 있다. 깊이 우선 탐색에서는 가장 먼 노드가 몇개있는지 ..
2018 KAKAO BLIND RECRUITMENT LEVEL 2 레벨 2문제 치고는 상당히 쉬운 문제라 고민하지 않고 풀었다. 단지 고민했던거라면 ArrayList의 사용이냐 LinkedList의 사용이냐였는데 일단 어느 하나 구현해보고 나서 무엇이 더 빠른지 체크만 하고 왜 그렇게 나왔는지에 대해서 공부해보기로 했다. 다만 알고리즘 LRU(Least Recently Used)을 사용한다고 나와있었는데, 그 알고리즘이 어떤 알고리즘인지 알 수 없던 터라 그 부분에 대해서는 어떤 개념인지에 대해 조사를 해보았다. LRU는 캐시 사이즈가 주어지는데, 그 사이즈 안에 있는 노드들이 있고 사이즈를 벗어나게끔 하나의 노드가 들어오게 되면 가장 오래된 노드를 버리고 새로운 노드를 받아들인다. 또한, 데이터 노드가..
2018 KAKAO BLIND RECRUITMENT LEVEL 2 LEVEL2인 뉴스클러스터링 문제만 해도 이렇게 까지 오래걸리지는 않았다. 그리고 문제가 나름 길었어도 풀 의욕은 있었는데 이 문제 만큼은 의욕이 떨어졌다. 계속되는 반복문에 일회성 계산이 아닌, 터뜨린 자리는 위에서부터 순차적으로 내려와 메꾸는 알고리즘 형태를 가지고 있어야 했기 때문이다. 물론, 더 나은 알고리즘으로 푼 사람들도 있겠지만 말이다. 중요한건 어떠한 참고서나 메소드 등을 활용하지 않았다는 점에서 문제를 풀었을 때 희열이 있었다. 내가 생각한 이 문제의 핵심적인 부분들은 다음과 같다. 1. 네모 확인하기 ---네모 형태가 없으면 break--- 2. 확인된 사항의 인덱스를 공백으로 변경(꼭 공백일 필요는 없다.) 3. 공백 ..
같은 Level 1이었던 비밀지도 편에서는 이렇게 오래걸리지는 않았지만, 다트 게임에서 시간을 오래 쓴 것 같다. 이유는, 조금 더 효율적인 방법이 있을 줄 알았다. 지속적으로 S, D, T에 대해 파악해야 하며, 한번에 들어오는 값에 의해서 숫자를 어떻게 분리할 것인지, option이 나왔을 때에 이전 점수에 대해 어떻게 처리할 것인지, 현재 값을 어떻게 - 시키는지 이런 잡다한 고민들 때문에 시작하기부터 애를 먹었다. 처음부터 비효율적이라고 생각하게 되면 시도조차 하지 않는 성격이기에 노가다성의 알고리즘 문제보다는, 효율적인 알고리즘을 생각해내는 것이 더 어울리는 것 같다. 이 문제가 무작정의 알고리즘 문제는 아니지만, 이해는 나름 쉽지만 구현하는데에 애를 먹기도 하고, 상수처럼 값을 집어넣어 하는 ..
