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

이 문제는 뭔가 이진 탐색을 써야할 것 같은 느낌이 딱 오는데.. 뭔가 어떻게 최댓값을 설정해야할 지 감이 안옵니다. 어떻게 이렇게 이해했는지 천천히 설명해보겠습니다 문제 요약 어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 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개의 보석을 구매하면 모든 종류의 보석을 적어도 하나 이상씩 포함하게 됩니다. 테스트케..

안녕하세요! 프로그래머스가 2022 카카오 인턴 코딩테스트 문제를 풀어줬네요. 일단 등산코스부터 한번 볼까 합니다. 이 문제는 다익스트라(dijkstra) 알고리즘을 활용해야하는 문제입니다. 문제를 읽기 전에 먼저 다익스트라 알고리즘에 대해 알아볼 필요가 있겠네요. 다익스트라(Dijkstra) 알고리즘: 간선에 가중치(weight)가 달라질 때.. 아래와 같은 그래프가 있다고 해볼까요? 간선에 적힌 노란 숫자는 그 노드로 가기까지 필요한 가중치(weight)라고 합니다. 가중치가 있는 경로에서는 bfs를 사용할 수 없습니다. 왜냐면 visited를 관리할 수 없기 때문입니다. 일반적인 bfs라면 노드 1에서 5를 향해 출발 할때 노드 4를 방문 처리하지만, 여긴 다릅니다. 가중치가 있기 때문에 노드 4를..

간만에 레벨2 문제네요.완전 탐색 문제입니다. 제가 푼 방법이 약간 비효율적인 것 같아서 "이사람은 이렇게 했구나"만 보셔도 충분할 것 같습니다.그럼 같이 볼까요? 문제 요약 n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 2 이상 100..