백준34 [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]15591번: MooTube (Silver) www.acmicpc.net/problem/15591 류트님 풀이(ryute.tistory.com/30)를 참고하여 해결하였습니다. N,Q 제한이 5000으로 작은 편입니다. 때문에 하나의 쿼리를 O(N)에 해결해도 O(QN)에 해결가능합니다. O(N)에 해결할 수 있는 방법은 하나의 쿼리당 BFS를 한 번 돌리면 됩니다. 주어진 동영상 v에 대해서 인접한 정점을 방문하면서 간선 가중치가 k이상인 정점만 방문합니다. 그러면 동영상 v와 연결되어있으면서 가중치가 k미만(== 유사도 k미만)인 정점은 제외됩니다. 코드: github.com/cotchan/algorithm/blob/main/cpp/BOJ/BOJ15591.cc 2021. 3. 31. 이전 1 2 3 4 ··· 9 다음
