본문 바로가기

분류 전체보기109

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.
99클럽 코테 스터디 4일차 TIL (24479: 알고리즘 수업 - 깊이 우선 탐색 1) 문제https://www.acmicpc.net/problem/24479 학습 키워드DFS 시도DFS 풀이각 정점의 출력 순서를 저장해야하기 때문에 각 정점의 순서를 저장하고 있는 visitedOrders와 순서를 기록하는 order를 선언한다.각 정점마다 연결된 간선을 저장하기 위해 map을 선언한다.모든 정점을 map에 추가하고, u와 v를 입력 받아 map에 추가한다. 양방향으로 추가하기 위해 u에 v를, v에 u를 추가한다.통해 모든 정점을 깊이 우선 탐색으로 탐색하면서 visitedOrders에 저장한다.visitedOrders에 저장된 정점의 모든 순서를 출력한다. 이때 방문하지 않은 정점은 초기값인 0으로 저장되어 있기 때문에 문제에서 출력으로 요구하는 '시작 정점에서 방문할 수 없는 경우 0.. 2024. 10. 31.

티스토리툴바