본문 바로가기

Algorithm283

[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.
[BOJ]18223번: 민준이와 마산 그리고 건우 www.acmicpc.net/problem/18223 다익스트라 응용 문제입니다. 최단 경로 내에 특정 경로가 포함되어 있다면 TRUE, 아니면 FALSE 입니다. 이런 경우에는 before[targetNode]라는 리스트를 만들어서 targetNode 이전에 어디를 방문했었는지 저장해놓습니다. 단, 어떤 노드를 새로 방문을 했을 때 목적지로부터 거리가 갱신되는 경우는 두 가지인데요. 1) 목적지로부터 거리가짧아지는 경우 2) 목적지로부터 거리가 이전과 같은 경우 이렇게 두 가지가 있습니다. 일반 다익스트라면 1번만 저장하면 되지만 지금은 2번도 경우의 수로 따져줘야 합니다. 그러므로 1번의 경우에는 이전에 저장한 before[targetNode]를 전부 지워버리고 새로 시작하고 2번의 경우에는 befo.. 2020. 9. 21.

티스토리툴바