G417 BOJ G4 1967 트리의 지름 JAVA 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 읽기 일단 해당 문제는 트리.. 이지만 잊지 말아야 할 것은 트리도 어쨌든 그래프라는 것이다. 이 문제를 풀기 위해서 어떻게 할 지 고민하다가, 처음에는 플로이드 워샬이 생각났다. 모든 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이기에, 이를 조금 수정하면 최장 거리를 구하는 것도 할 수 있을 것이라 생각했다. 그래서 알고리즘을 다시 살펴봤는데, 시간 복잡도가 V^3이라 어림도 없었다. (해당 문제에서 V = 10000이다) 두.. 2024. 4. 6. BOJ G4 9019 DSLR JAVA 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제 읽기 일단 해당 문제를 읽고 나서는 완전 탐색 말고는 딱히 방법이 떠오르지는 않았다. 그래서 DFS와 BFS를 생각했고, DFS는 깊이 우선 탐색이라 끝이 없을 것 같아서.. 백퍼 시간 초과 날 거 같았다. 그래서 최소 연산의 개수를 구하는 것이기 때문에 BFS를 바로 적용해서 해결했다. 문제 풀기 문제는 크게 어렵지 않다. 주어진 명령어마다 요구사항에 따라서 정확하게 구현한다면 틀리지는 않을 것이다. 또한 같은 숫자로 또 탐색하지 않도록 하기.. 2024. 3. 27. BOJ G4 13913 숨바꼭질4 JAVA 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 읽기 해당 문제는 가장 빨리 갈 수 있는 시간, 그리고 그 때의 루트를 출력해야 한다. 이전에 가장 빨리 갈 수 있는 시간을 문제는 풀어봤던 기억이 있다. 하지만 이 문제는 루트까지 출력해야 한다! 즉, BFS + 루트 출력 문제라 볼 수 있다. 문제 풀기 BFS를 쓰는 이유는, 당연하겠지만 최소 시간을 구하기 때문이다. 이 문제는 완전 탐색을 해야 하는데, DFS, BFS 중에서 고르라면 최소 시간만 얻으면 되기 때문에 주.. 2024. 3. 22. BOJ G4 9177 단어섞기 JAVA 9177번: 단어 섞기 입력의 첫 번째 줄에는 1부터 1000까지의 양의 정수 하나가 주어지며 데이터 집합의 개수를 뜻한다. 각 데이터집합의 처리과정은 동일하다고 하자. 각 데이터집합에 대해, 세 개의 단어로 이루어 www.acmicpc.net 문제 읽기 문제를 처음에 읽었을 때에는 모든 경우의 수를 따지는 방법을 생각했다. 단순하게 생각하면 dfs가 직관적이라 dfs를 생각했지만, 복잡도를 생각했을 때 단어의 길이가 200이기 때문에 dfs를 수행하면 지수 시간이기 때문에 불가능했다. 그래서 bfs로 접근했다. 문제 풀기 bfs로 풀었는데, 사실 처음에는 visited가 필요 없다고 생각했다. 처음에 다음 그림을 그렸었다. 이렇게 오른쪽, 아래쪽 두 방향으로 내려가면 경우의 수를 구했을 때 방문 처리는.. 2024. 3. 18. 이전 1 2 3 4 5 다음
