본문 바로가기

Algorithm/BOJ172

[BOJ]17182번: 우주 탐사선 www.acmicpc.net/problem/17182 시작점에서 출발해서 모든 점을 전부 순회할 때 최솟값을 구하는 문제입니다. 문제 조건이 MST나 단순 다익스트라와는 약간 다릅니다. 1. 플로이드를 통해 모든 정점쌍 간의 최소거리를 구합니다. 2. N제한이 작으므로 순열을 통해 방문할 순서를 미리 정한 후 순서대로 방문해봅니다. 위 과정을 통해 가장 짧은 경로를 구할 수 있습니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ17182.cc 2020. 10. 6.
[BOJ]16987번: 계란으로 계란치기 www.acmicpc.net/problem/16987 시뮬레이션 문제입니다. 한 회차에 선택할 수 있는 계란이 여러 개이므로 백트래킹으로 구현하는 게 편리합니다. 1. 현재 부숴지지 않은 계란만 뽑기 2. 현재 부숴지지 않은 계란만 치기 3. 어떤 경우에도 기저 사례(맨 오른쪽 계란)까지 진행하기 위 세 가지만 잘 처리하시면 해결 가능합니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ16987.cc 2020. 10. 4.
[BOJ]16986번: 인싸들의 가위바위보 www.acmicpc.net/problem/16986 시뮬레이션 문제입니다. 문제 요구조건대로 상황을 나눠서 구현하면 됩니다. 더 간결한 코드는 아마 바킹독님 블로그 가시면 확인하실 수 있습니다 ㅎㅎ 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ16986.cc 2020. 10. 4.
[BOJ]14588번: Line Friends (Small) www.acmicpc.net/problem/14588 임의의 두 정점간의 거리를 한 번에 알려줘야 하므로 플로이드로 해결하는 게 적절합니다. 플로이드 노드의 갱신을 위한 점화식은 다음과 같습니다. if (dist[i][j] > dist[i][mid] + dist[mid][j]) dist[i][j] = dist[i][mid] + dist[mid][j] 코드(python): github.com/cotchan/algorithm/blob/main/python/BOJ/BOJ14588.py 코드(JAVA): github.com/cottory/algorithm/blob/master/BOJ/BOJ14588.java 2020. 9. 21.

티스토리툴바