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

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

정규 표현식을 물어보는 문제가 가끔씩 있더라구요.매번 검색해서 어떻게 어떻게 해내긴 했는데 한 번 다뤄보는게 좋을 것 같습니다. 이 문제가 딱 그렇게 다루기 좋아보여서 가져와봤습니다. 정규 표현식 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..