안녕하세요! 이 문제는 플로이드-워셜 알고리즘을 알고 있다면 3분만에 해결할 수 있습니다. 플로이드-워셜 알고리즘이 어떤 상황에서 쓰이는 지 알고 있는가? 를 물어보는 문제네요. 문제 요약 밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. "무지"는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. "무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 "어피치"에게 합승을 제안해 보려고 합니다. 위 예시 그림은 택시가 이동 가능한 반경에 있는 6개 지점 사이의 이..

안녕하세요. 어제 공유드린 제가 새로 짠 힙을 응용할 시간이 되었군요. [JS] 힙/우선 순위 큐 새로 짜봤습니다. Javascript에서 힙이 필요하면 매번 구현을 해줘야하는 정말.. 험난한 여정이 있는데요. 저번에 제가 대략적으로 공유한 코드가 모든 상황에서 쓰이기 힘들더라구요. 특히 pop에서 최상단 노드부터 dev-russel.tistory.com 문제는 되게 쉽습니다. 같이 한 번 볼까요? 문제 요약 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다. I 숫자 큐에 주어진 숫자를 삽입합니다. D 1 큐에서 최댓값을 삭제합니다. D -1 큐에서 최솟값을 삭제합니다. 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,..

Javascript에서 힙이 필요하면 매번 구현을 해줘야하는 정말.. 험난한 여정이 있는데요. 저번에 제가 대략적으로 공유한 코드가 모든 상황에서 쓰이기 힘들더라구요. 특히 pop에서 최상단 노드부터 왼쪽 노드, 오른쪽 노드를 비교해줘야하는데, 이 과정에서 undefined와 관련해서 많은 오류가 있는 걸 확인했습니다. 새로 짠 코드를 공유해드릴게요. Heap.js class MinHeap { constructor() { this.heap = [null]; } push(val) { this.heap.push(val); let currentIndex = this.heap.length - 1; let parentIndex = Math.floor(currentIndex / 2); while (parentInd..

이 문제는 뭔가 이진 탐색을 써야할 것 같은 느낌이 딱 오는데.. 뭔가 어떻게 최댓값을 설정해야할 지 감이 안옵니다. 어떻게 이렇게 이해했는지 천천히 설명해보겠습니다 문제 요약 어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 a kg과 은 b kg이 전달되어야 합니다. 각 도시에는 번호가 매겨져 있는데, i번 도시에는 금 g[i] kg, 은 s[i] kg, 그리고 트럭 한 대가 있습니다. i번 도시의 트럭은 오직 새 도시를 짓는 건설 장소와 i번 도시만을 왕복할 수 있으며, 편도로 이동하는 데 t[i] 시간이 걸리고, 최대 w[i] kg 광물을 운반할 수 있습니다. (광물은 금과 은입니다. 즉, 금과 은을 동시에..

정규 표현식을 물어보는 문제가 가끔씩 있더라구요.매번 검색해서 어떻게 어떻게 해내긴 했는데 한 번 다뤄보는게 좋을 것 같습니다. 이 문제가 딱 그렇게 다루기 좋아보여서 가져와봤습니다. 정규 표현식 Javascript에선 주로 string 형식의 문자열에서 원하는 값이 있는지 찾기 위해서 사용합니다. 일반적으로 웹에서 이메일 형식의 input을 받는다던가, password에 특정 규칙을 만족하는지 등에서 쓰입니다. 다만, 코딩테스트에서 다루는 정규 표현식의 성격은 약간 다를 수 있을 것 같습니다. 보통 이런 식으로 묻는 경우가 많습니다. 어떤 특정 자리에 이 문자가 들어가는지? 이 자리에 모든 문자가 올 수 있을 때 만족하는 문자는? 이스케이프 문자를 다 외우는 건 약간 비효율적인 것 같습니다. 검색하면 ..

어제 했던 등산 코스 문제를 보고나니 이문제.. 정말 선녀네요. 길게 말할 것도 없습니다. 그냥 가볼까요? 문제 요약 어피치는 너무 부자라서 보석을 사러가면 진열대의 특정 구간의 모든 보석을 싹쓸이합니다. 이 때 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매합니다. 가장 짧은 구간을 찾아 return해주세요. 예를 들어 아래 진열대는 4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE) 8개가 진열된 예시입니다. 진열대 번호 1 2 3 4 5 6 7 8 보석 이름 DIA RUBY RUBY DIA DIA EMERALD SAPPHIRE DIA 진열대의 3번부터 7번까지 5개의 보석을 구매하면 모든 종류의 보석을 적어도 하나 이상씩 포함하게 됩니다. 테스트케..