다익스트라4 [프로그래머스] 코딩테스트 공부 https://school.programmers.co.kr/learn/courses/30/lessons/118668 문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다. 코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다. 알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 0 이상의 정수로 표현됩니다. 문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다. 예를 들어, 당신의 현재 알고력이 15, 코딩력이 10이라고 가정해보겠습니다. A라는 문제가 알고력 10, 코딩력 10을 요구한다면 A 문제를 풀 수 있습니다... 2023. 11. 25. [카카오 2022] 등산코스 정하기 https://school.programmers.co.kr/learn/courses/30/lessons/118669 XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 산봉우리입니다. 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 서로 다른 지점을 이동할 때 이 등산로를 이용해야 합니다. 이때, 등산로별로 이동하는데 일정 시간이 소요됩니다. 등산코스는 방문할 지점 번호들을 순서대로 나열하여 표현할 수 있습니다. 예를 들어 1-2-3-2-1 으로 표현하는 등산코스는 1번지점에서 출발하여 2번, 3번, 2번, 1번 지점을 순서대로 방문한다는 뜻입니다. 등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며.. 2023. 11. 18. [다익스트라 레벨3] 부대복귀 문제링크 첫번째 풀이 (성공) 문제에 정해진 destination에서 다른 부대로 이동하기까지 최소비용을 구한다 => 몇일 전 공부한 다익스트라가 생각났다. 시작노드에서 각 노드까지 최소비용값을 저장할 distance 배열을 만든다 이 때 인덱스 = 노드값 동일하게 하기 위해 길이는 n+1이다 최소비용을 구하므로 Infinity로 초기화한다. roads를 순회하며 각 노드에 연결된 neighbors를 정리하여 양방향 그래프 graph를 만든다. (distance와 같은 길이) queue에 방문한 노드를 추가하는데 초기화로 시작노드 destination을 넣는다 queue.shift하여 시작노드의 값을 구하고, 2번에서 구한 graph에서 시작노드와 연결된 next를 구한다 시작노드에서 next 까지 최소.. 2023. 11. 3. [다익스트라] 배달 https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제정리 1번 마을에서 출발 K시간 이하까지의 마을에 배달을 한다. 배달이 되는 마을 갯수는? 1에서 각 마을까지 최단거리 배열을 구하고 그 중 최단거리가 K보다 작은 마을 갯수를 리턴한다 첫번째 풀이(성공) 하나의 시작노드에서 다른 노드로 이동, 최단기간 => 다익스트라 1. 그래프 생성 2. weightArr, queue 시작점 초기화 3. while queue 순회 3-1. 이웃노드찾기 3-.. 2023. 11. 1. 이전 1 다음
