힙과 트리는 꽤 비슷한 자료구조 같지만 명확한 차이가 있습니다. 트리를 다뤄야 하는 문제에서 힙을 다뤘을 때 생길 수 있는 문제점에 대해서 기록해보려고 합니다. 1. 힙(Heap) 항상 이진 트리 구조를 구현할 때 관성적으로 heap을 사용하곤 했는데요. heap 구조는 탐색에 적절하진 않습니다. parent node에 대해서 child node가 항상 차 있지 않는 경우가 있기 때문입니다. 주로 heap은 우선 순위 큐의 구현을 위해 사용합니다. [JS] 힙/우선 순위 큐 새로 짜봤습니다. Javascript에서 힙이 필요하면 매번 구현을 해줘야하는 정말.. 험난한 여정이 있는데요. 저번에 제가 대략적으로 공유한 코드가 모든 상황에서 쓰이기 힘들더라구요. 특히 pop에서 최상단 노드부터 dev-russ..

얼마전에 다익스트라 알고리즘을 다뤘었죠 [JS] 등산코스 정하기 - 다익스트라 알고리즘에 대해서 안녕하세요! 프로그래머스가 2022 카카오 인턴 코딩테스트 문제를 풀어줬네요. 이거 2sol 했는데ㅠㅠ 일단 등산코스부터 한번 볼까 합니다. 이 문제는 다익스트라(dijkstra) 알고리즘을 활용해야하 dev-russel.tistory.com 이번엔 플로이드-워셜입니다. 기능은 역시 "최소 경로 찾기"에 이용됩니다. 다만, 다익스트라와의 차이점이라고 한다면, 모든 정점에서의 최소 거리를 구한다는 점입니다. 노드의 시작 지점이 계속 바뀌는 문제를 다룬다면, 플로이드-워셜 알고리즘을 쓰기 적합한 문제일 것 같습니다. 전 이 문제를 풀다가 플로이드-워셜을 적용해야하는 걸 알았는데요. 예를 들어 모든 정점에서 갈 수..

올해 4월이었나 카카오 인턴 코테를 아무 준비 없이 경험삼아서 본 적이 있습니다. 근데 이제 거기서 나왔던 문제가 N X N 배열을 조금씩 회전하는 게 5번문제였던 기억이 납니다. ([0][0] => [0][1] / [1][0] => [0][0] 이런 느낌의 회전이었어요ㅠㅠ) 가운데 중점 기준으로 교차하는 직선 두개 그리면서 규칙성 찾다가 하지도 못하고 끝났었는데요. 갑자기 ptsd 오네요. 이 회사 코테는 참 배열 회전하는걸 좋아하나봐요. 2020년에도 2021년에도 배열 90도 회전하는 문제가 나왔었습니다. 이젠 뭐 90도는 다 잘한다고 생각해서 이런걸 내는건지.. 불평하면 달라질까요? 신입이면 하라면 해야죠! 일단 차근차근 90도 회전부터 다뤄보죠! 90도 회전은 그나마 합리적입니다. 몇 가지 규칙..