본문 바로가기

Algorithm44

[백준] 11725. 트리의 부모 찾기 / Java https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 루트 노드인 1부터 DFS 탐색을 하기 때문에 DFS가 시작되는 노드가 부모가 되고, 이 노드에 연결되어 있으면서 아직 탐색되지 않은 노드를 찾는다면 그 노드가 자식 노드가 되게 된다. 다시 말해, 루트 노드로부터 아직 탐색되지 않은 노드를 탐색하며 해당 노드가 어느 노드로부터 왔는지를 찾아 parent[]에 저장한다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import j.. 2023. 5. 30.
[백준] 4963. 섬의 개수 / Java https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 풀이 일반적인 BFS 탐색문제의 흐름대로 풀 수 있는 문제였지만, 하나 특이한 점이라면 대각선 위치로도 이동할 수 있다는 조건이 있다는 점이었다. 추가적인 설명은 소스코드의 주석으로 이어진다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import jav.. 2023. 5. 29.
[백준] 14502 연구소 / java https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 풀이 이 문제는 BFS 카테고리의 문제 목록에서 발견했지만 실상은 BFS와 DFS를 복합적으로 사용해야 하는 문제였다. 각각이 사용되는 부분은 아래와 같다. DFS: 벽을 3개 세우는 경우의 수 탐색 BFS: 위 DFS에서 찾은 각 경우에 대해 바이러스를 퍼뜨리는 과정 탐색 다시 말해, DFS로 BFS를 할 케이스를 골라내는 것이다. 더불어 유의할 점으로 Deep Copy와 Swallow Copy의 차이.. 2023. 5. 29.
[Java] 자릿수별(n자리) Palindrome 수 개수 구하기 Palindrome 이란? 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 등이다. 수로 예를 들면, 3, 131, 1221 등이 palindrome 수이다. 문제상황 1 이상, 10, 000 이하 정수 n이 주어졌을 때 palindrome인 n자리 수의 갯수를 구하라. 풀이 코드 class Solution { public int solution(int n) { if (n == 1) { return 10; } long ans = 1; for (int i = 0; i < n; i += 2) { ans = (ans * (i == 0 ? 9 : 10)); ans %= 1_000_000_007; // 오버플로우 방지 } return (int)ans; } } 2023. 1. 30.

티스토리툴바