백준 알고리즘44 [BOJ]1162번: 도로포장(JAVA) 문제: https://www.acmicpc.net/problem/1162 JusticeHui님이 푸신 솔루션을 참고하여 해결하였습니다. (출처: https://justicehui.github.io/usaco/2019/07/12/BOJ1162/) 도로 포장에 대한 정보를 어떻게 나타내느냐가 중요한 문제입니다. 이 문제의 경우 다익스트라의 결과값인 dist[N]을 다음과 같이 응용해서 정의할 수 있습니다. dist[N][K]: 출발점 1번 도시에서 N번 도시까지 갈 때, K개의 도로를 포장해서 가는 최단거리. 이 때 저희가 원하는 정답 값은 아래와 같습니다. answer = min(dist[N][0],dist[N][1],dist[N][2],dist[N][3],dist[N][4],...,dist[N][K]) .. 2021. 6. 28. [BOJ]1590번: 캠프가는 영식 https://www.acmicpc.net/problem/1590 버스의 갯수 와 각 버스의 대수가 각 각 10만이므로 N^2 탐색을 하면 시간초과가 납니다. 그러므로 한 종류의 버스에 대해 영식이가 최소 몇 분을 더 기다려야하는지 계산할 때 logN만에 탐색해야 합니다. 그래야 NlogN으로 시간제한을 통과할 수 있습니다. 제가 logN으로 시간복잡도를 줄인 방법은 이분탐색입니다. 이분 탐색을 사용하여 버스 도착 시간의 상한과 하한을 계산해서 영식이가 탈 수 있는 최초 버스 시간을 구했습니다. 코드: https://github.com/cotchan/algorithm/blob/main/java/BOJ/BOJ1590.java 2021. 6. 23. [BOJ]1759번: 암호 만들기 www.acmicpc.net/problem/1759 시뮬레이션 문제입니다. 1. 주어진 문자열을 알파벳 오름차순으로 정렬합니다. 2. C개의 문자에서 L개의 문자를 뽑습니다. 3. 뽑은 L개의 문자가 주어진 조건을 만족하는지 확인합니다. 4. 3번에서 조건을 만족한다면 정답 문자열로 추가합니다. 1번에서 주어진 문자열을 정렬 후 뽑기 시작하므로 앞에서부터 뽑은 순서대로 정답을 구하면 됩니다. 코드: github.com/cotchan/algorithm/blob/main/java/BOJ/BOJ1759.java 2021. 4. 8. [BOJ]17142번: 연구소3(py) www.acmicpc.net/problem/17142 시뮬레이션 문제입니다. n개의 바이러스 위치 중에 m개를 뽑아서 최소를 찾는 문제이므로 조합(combination)을 통해 해결할 수 있습니다. 한 가지 주의 사항은 바이러스의 종류와 무관하게 빈 칸(0)만 채우면 됩니다. 그러므로 탐색을 종료 조건은 BFS로 채운 빈 칸의 숫자가 주어진 입력의 0칸 갯수와 동일하면 됩니다. 코드: github.com/cotchan/algorithm/blob/main/python/BOJ/BOJ17142.py 2021. 2. 3. 이전 1 2 3 4 ··· 11 다음
