본문 바로가기

알고리즘/백준22

99클럽 코테 스터디 10일차 TIL (18352번: 특정 거리의 도시 찾기) 문제https://www.acmicpc.net/problem/18352학습 키워드BFS 시도출발 도시부터 시작해서 연결되있는 가까운 도시를 탐색한다. 탐색하면서 이동한 거리를 저장하고, 만약 이동한 거리가 주어진 K와 같다면 정답에 추가한다. 풀이 및 코드List listAnswer : 거리 정보 K와 거리가 같은 도시의 목록Map> graph : 도시간 연결을 Map으로 표시했다. 예제 입력 1을 기준으로 1: {2, 3}, 2: {3, 4}와 같이 저장된다.boolean[] visited : 해당 도시를 이미 탐색했는지 판단하기 위한 배열int[] distance : 출발 도시 X부터의 거리를 저장하기 위한 배열 import java.util.*;import java.io.*;public class .. 2024. 11. 6.
99클럽 코테 스터디 8일차 TIL (2644번: 촌수계산) 문제https://www.acmicpc.net/problem/2644학습 키워드BFS 시도(성공) 촌수를 계산해야하는 두 번호(a, b)의 조상까지 탐색하면서 같은 조상이 있는 지점까지 탐색한다. 그 다음, 두 번호(a, b)에서부터 같은 조상의 위치까지 1씩 더해가면서 거리를 찾는다.(성공) a부터 시작해서 b까지 BFS를 통해 거리를 구한다.풀이 및 코드visited: 이미 탐색한 정점은 다시 탐색하지 않기 위해서 필요한 배열distance: a부터 시작해서 각 정점에 도달했을 때, 거리가 몇인지 저장하는 배열현재 정점에서 가까운 정점부터 시작해서 탐색하고, 각 정점에 도달할 때마다 거리를 저장한다. 만약 목적지에 도달했다면 해당 목적지의 거리를 반환하고, 목적지에 도달하지 못 했다면 -1을 반환한다.. 2024. 11. 4.
99클럽 코테 스터디 6일차 TIL (2805번: 나무 자르기) 문제https://www.acmicpc.net/problem/2805학습 키워드이분 탐색 시도입력 제한 사항을 제대로 읽지 않고 풀어서 시간 초과 발생. 주어진 나무들의 높이 중 가장 큰 높이부터 1씩 줄여가면서 M을 만족하는 가장 높은 나무의 높이를 계산했다. 나무 높이의 최대값은 1,000,000,000이므로, 1초를 훨씬 넘는다. 처음에는 시간초과를 했을 때, 입력 값이 많아서 그런줄 알고 BufferedReader와 StringTokenizer를 사용해서 입력을 받았다. 나무의 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.(성공) 이분 탐색을 통해 범위를 줄여가면서 최적의 해를 구하는 방식으로 풀었다. 풀이0부터 나무 높이의 최대값(1,000,000,000)까지 이분 탐.. 2024. 11. 2.
99클럽 코테 스터디 5일차 TIL (24444번: 알고리즘 수업 - 너비 우선 탐색 1) 문제https://www.acmicpc.net/problem/24444 학습 키워드BFS 시도BFS를 사용해서 풀면된다. 풀이무방향 그래프이므로 map에는 u와 v 양쪽 다 저장해야한다.put(u, v);put(v, u);각 정점이 출력된 순서를 저장하는 orders와 출력 순서를 기억하기 위한 orderIndex를 선언한다.탐색했는지 여부를 저장하기 위한 visited를 선언한다.BFS 방식으로 탐색하면서 각 정점이 추가되는 지점을 찾아 order에 기록한다.import java.util.*;public class Main { private static int N; private static int M; private static int R; private static Map> map; private .. 2024. 11. 1.

티스토리툴바