오늘 하루, develop

💡 문제 링크https://www.acmicpc.net/problem/1939 - 첫 풀이(실패)처음에 시도한 풀이는 아래와 같다. 출발지에서 도착지까지의 모든 경로를 구하면서 해당 경로 상에서 가장 작은 중량을 구하고,모든 경로의 값들과 비교해 그 중에서 가장 큰 중량을 구하려고 했다.그 과정에서 이미 구한 가장 작은 중량보다 더 작은 값은 가지치기하려고 했다. 조금 틀린 코드이기도 하지만 그 전에 우선 시간 초과가 났다."서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며" 라는 조건 때문에섬에 방문 처리를 할 수가 없어(백트래킹으로 dfs 후 visited를 다시 false 처리함)시간 초과가 난 것 같다.틀린 코드는 아래와 같다.더보기import java.io.BufferedReader..

💡 문제 링크https://www.acmicpc.net/problem/1202 💡 아이디어지난번 Comparator 관련 글을 작성한 후 연습이 하고 싶어 관련 문제를 찾아서 풀었다.온전히 스스로의 힘으로는 못하고 블로그를 참고했다.🥹 1번 아이디어 : 이중 for문가방 리스트와 보석 리스트를 만들고 가방은 오름차순, 보석은 내림차순으로 정렬한다.높은 가격의 보석부터 보석이 들어갈 수 있는 가방 중 가장 작은(무게 기준) 가방을 찾는다.이중 for문을 활용하면 300,000 * 300,000 이므로 시간 초과가 뜰 것이다. 2번 아이디어 : 이분 탐색가방 리스트와 보석 리스트를 만들고 가방은 오름차순, 보석은 내림차순으로 정렬한다.높은 가격의 보석부터 보석이 들어갈 수 있는 가방 중 가장 작은(무게..

💡 소개알고리즘 문제를 풀다 보면 특정 기준에 맞게 배열 또는 리스트의 요소를 정렬해야 하는 순간이 온다.그때 이따금씩 활용하게 되는 것이 Comparator 인터페이스인데, 오랜만에 구현할 때마다 헷갈려서 블로그를 찾아보게 돼서 미래의 나를 위해 간단하게 정리하고자 한다.이 글에서는 Comparator 인터페이스의 깊이 있는 내용보다는 (깊이 있는 내용은 더 좋은 블로그들에서 많이 다루고 있기에ㅎ) 알고리즘 문제 해결 시 알아야할 간단한 내용들을 작성하려고 한다. 💡 어떤 경우에 Comparator을 사용하면 될까?내가 Comparator를 사용한 경우는 아래와 같다.Arrays.sort()Collection.sort()new PriorityQueue()Comparator은 자료구조 내에서 정렬을 ..

💡 문제 링크https://www.acmicpc.net/problem/5052  💡 아이디어문자열 비교 횟수를 줄이기 위해 정렬을 우선 한다.앞뒤 문자열만 비교한다. (바로 뒤 문자열이 나를 포함하지 않는데, 그 이후 문자열이 나를 포함할 수는 없다. 정렬되었기 때문.) 💡 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Collections;import java.util.List;public class BOJ_G4_5052_전화번호목록 { public static int t; public sta..