어흥

문제 링크:https://school.programmers.co.kr/learn/courses/30/lessons/132266 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 주의할 점 - 한 지점부터 다른 지점까지의 최단 거리를 구하는 알고리즘은 대표적으로 다익스트라, 플로이드 와샬, 벨만포드가 존재 이때 N은 최대 10만이다 플로이드 와샬은 O(N^3) → TLE 발생 확률 매우 높아보인다 벨만포드는 간선에 음수가 있을 때 사용하는 다익스트라의 심화버전이지만 현재는 모든 간선에 1이라는 양수값만 있으므로 Pass 결국, 다익스트라 채택 - Sour..

문제 링크: https://www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 1. 주의할 점 - 늑대가 같은 지점에 최단 경로로 도착하는것보다 돌아서 가는게 빠를 수 있다(느릴 때, 빠를 때 적절히 이용) - 1번째 Node까지의 최단시간을 0으로 설정하지 않는다(0을 이용하여 돌아갈 수 있다) - d와 M의 범위가 크므로 Long Long을 이용한다 2. 구현 - Info 객체를 이용한 우선순위 큐를 ..

문제 링크: https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 1. 주의할 점 - 다익스트라 알고리즘에 대해 알고 있어야 한다 2. 구현 - 1번 Node부터 각 Node까지의 거리를 MAX로 초기화한다 - 간선에 대한 정보를 V[] 벡터에 담는다 - 우선순위큐를 사용하여 다익스트라 알고리즘을 구현한다 #define MAX 987654321 #include #include #include #include using namespace std; struct ..

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/81304 코딩테스트 연습 - 미로 탈출 4 1 4 [[1, 2, 1], [3, 2, 1], [2, 4, 1]] [2, 3] 4 programmers.co.kr 1. 주의할 점 - 10가지 Trap의 상태를 어떤 방식으로 저장할 것인가 - 최단경로 알고리즘인 다익스트라 알고리즘에 대해 알고 있어야 한다 2. 구현 (아래 색칠된 3개가 가장 중요한 비트마스크 수식) - Trap의 상태가 최대 10개다 + 다익스트라를 사용해야 할 것 같다 → Trap의 상태가 공용으로 설정되면 안된다 → 비트마스킹을 사용한다 - 현재 Node, 총 이동거리, 현재 Trap의 상태를 나타내는 Info 객체를 사용한다 - M..

문제 링크: https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 1. 주의할 점 - 초기화 작업을 거친다 - 다익스트라나 플로이드와샬 알고리즘에 대해 알고 있으면 해결할 수 있다(Tree라서 DFS도 간단히 가능) import java.util.*; import java.lang.*; import java.io.*; class Main { static final int MAX = 987654321; static int node,query; public static void main (Strin..

문제 링크: programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 1. 주의할 점 - 모든 정점이 서로 연결되어 있지 않다 - 3번의 다익스트라 알고리..

문제 링크: programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 1. 주의할 점 - 다익스트라 알고리즘에 대해 알고 있어야 한다 2. 구현 - 모든 간선에 대한 정보를 V[] 벡터에 담는다 - Check[]를 통해 1번 Node에서 부터 각 Node까지의 거리를 나타내며, 초기에 -1로 초기화한다 - 다익스트라 알고리즘을 통해 Check[] 배열을 모두 구하며, 이 과정에서 가장 먼 거리인 Longest가 초기화될 경우, Answer도 초기화한다. 만약 Longest와 같을 경우, Answer++..

문제 링크: www.acmicpc.net/problem/15971 15971번: 두 로봇 입력에서 두 번째 줄에 주어지는 방번호는 1과 2, 세 번째 줄에 주어지는 방 번호는 2와 3, …, i번째 줄에 주어지는 방 번호는 i-1과 i, …, N번째 줄에 주어지는 방 번호는 N-1과 N이다 (아래 입력과 www.acmicpc.net 1. 주의할 점 - 다익스트라 알고리즘에 대해 알고 있어야 한다 - O(NlgN)에 끝내도록 한다 2. 구현 - 같은 통로에 있을때까지 이동한다 → A에서 B까지 이동한다 - 1개의 변을 뺀다 → 빼는 1개의 변이 최단경로중 가장 값이 크면 움직인 거리가 최소가 된다 → 다익스트라 알고리즘 + 변의 최장 길이 저장 - Dist[] 배열을 통해 시작지점에서 각 지점까지의 최단거..