알고리즘261 [BOJ]16562번: 친구비 문제: https://www.acmicpc.net/problem/16562 그래프 문제입니다. 1. 주어진 간선(친구 관계)을 활용하여 전체 N개의 노드를 몇 개의 컴포넌트로 나눕니다. - 예제의 경우 2개의 컴포넌트로 나뉩니다. (1-3, 2-4-5) 2. 각 컴포넌트를 탐색하기 위한 최소 비용을 구합니다. 3. 각 컴포넌트를 탐색하기 위한 최소 비용들의 합이 K 이하라면 모든 사람과 친구가 될 수 있고, K 초과면 불가능합니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ16562.java 2022. 3. 2. [2020 카카오 기출] 기둥과 보 설치(JAVA) 문제: https://programmers.co.kr/learn/courses/30/lessons/60061 sooooooyn님의 솔루션으로 해결하였습니다. (https://sooooooyn.tistory.com/32) 기둥과 보를 설치/삭제 시에 어떻게 따져주는 지에 따라 난이도가 달라지는 문제입니다. 서치했던 솔루션 중에 굉장히 심플한 솔루션이라고 생각합니다. 간단하게 두 가지로 모든 경우를 처리합니다. 1. kidoong[N][N], bo[N][N] 으로 기둥과 보를 표현 2. 삭제 입력이 들어오면 일단 삭제 시켜본 후에, 삭제 시킨 좌표와 연관이 있는 기둥이나 보가 설치 불가능하다고 판정이 나는 경우 롤백시킵니다. 코드: https://github.com/cotchan/algorithm/blob/.. 2021. 7. 1. [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. 이전 1 ··· 11 12 13 14 15 16 17 ··· 66 다음
