코딩 레시피

Algorithms/Graph 검색 결과

해당 글 8건

[프로그래머스] 길 찾기 게임(C++)

길 찾기 게임(Level 3) 문제 전체 문제 보기 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 접근법 이번 문제는 주어진 노드들의 정보를 활용하여 이진트리를 만들고, 만들어진 이진트리를 활용하여 전위 순회와 후위 순회를 한 결과를 배열에 저장하는 문제입니다. 이진트리를 만들기 위해서는 부모 노드 → 자식 노드 순으로 트리에 삽입할 경우 구현의 복잡도를 많이 줄일 수 있습니다. 그래서 주어진 nodeinfo를 다음과 같이 y값을 기준으로 정렬 후 Tree에 삽입하였습니다. Tree 구현에 대한 설명은 아래에..

Algorithms/Graph 2021. 11. 23. 16:58

[BOJ 1389] 케빈 베이컨의 6단계 법칙(C++)

케빈 베이컨의 6단계 법칙(Silver 1) 문제 전체 문제 보기 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 접근법 모든 사람에 대해서 각 사람들까지 관계 단계를 모두 계산해야 합니다. 이럴 경우 플로이드 워셜 알고리즘을 사용할 수 있습니다. 모든 사람들 관계에 대한 2차원 테이블을 만듭니다. 그리고 플로이드 워셜 알고리즘을 활용하여 관계의 최단 거리를 구합니다. 이 거리들의 합이 바로 케빈 베이컨의 수가 됩니다. 이 수가 가장 작은 사람을 출력하면 정답을..

Algorithms/Graph 2021. 9. 22. 16:24

[프로그래머스](플로이드 워셜)합승 택시 요금 (C++ / 2021 KAKAO BLIND)

합승 택시 요금 (Level 3) 문제 전체 문제 보기 코딩테스트 연습 - 합승 택시 요금 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 접근법 이 문제는 합승을 통해서(혹은 합승을 하지 않을 수 있음) 가장 요금을 절약할 경우의 금액을 출력해야 합니다. 예를 들면 ..

Algorithms/Graph 2021. 9. 11. 13:26

[BOJ 1504] (Dijkstra)특정 최단 경로(C++)

특정 최단 경로(Gold 4) 문제 전체 문제 보기 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 접근법 이 문제는 양의 가중치를 간선을 가진 그래프에서 최단 경로를 찾는 문제의 변형이다. 출발 노드 1에서 도착 노드 N까지 가는 도중 v1과 v2 노드를 반드시 지나야 한다. 그리고 아래의 그림처럼 1 → v1 → v2 → N으로 가는 경로와 1 → v2 → v1 → N 으로 가는 경로 두 가지가 존재하고 이 둘 중 더 가까운 경로의 거리를 출력해야 한다. 알고리..

Algorithms/Graph 2021. 9. 11. 12:45