본문 바로가기

알고리즘 풀이/백준

 (48)
[백준] 5639번: 이진 검색 트리 - JAVA 🔗 문제 링크 BOJ 5639번: 이진 검색 트리 1️⃣ 트리 직접 그리기 📝 풀이 과정 전위 순회의 경우 처음 탐색한 값이 항상 root이기 때문에 먼저 처음 값을 root로 설정해 주었다. 이후 반복문을 돌며 Node에 insert함수를 구현해 현재 노드의 값보다 작으면 왼쪽 자식, 크면 오른쪽 자식으로 넘어가 null일 경우 해당 노드를 생성해주고 아니라면 재귀적으로 다시 탐색하는 방식으로 구현해주었다. 트리가 모두 완성되면 후위 순회 함수를 구현해 왼쪽 자식, 오른쪽 자식, 현재 노드 순으로 탐색해 출력해 주었다. 💻 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; publi..
[백준] 2638번: 치즈 - JAVA 🔗 문제 링크 BOJ 2638번:치즈 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 📝 풀이 과정 문제에서 외부 공기라는 개념이 존재하기 때문에, 가장자리는 항상 공기이므로 먼저 [0, 0]에서부터 BFS를 통해 0인 칸은 모두 10으로 변경해주었다. 이후 반복문을 돌며 치즈 칸에서 상하좌우 칸의 합이 20이상일 경우 외부 공기가 2칸 이상 존재한다는 것을 의미하므로 외부 공기로 변화시키는 BFS를 위한 Queue에 삽입한다. 반복문을 돌며 Queue 내부에 있는 값들을 10으로 변경하고 접촉한 공..
[백준] 15591번: MooTube (Silver) - JAVA 🔗 문제 링크 BOJ 15591번: MooTube (Silver) 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 📝 풀이 과정 문제를 보면 N까지의 영상이 존재하는데 영상끼리 가는 경로는 무조건 존재하며, 개수는 N - 1개라고 주어진다. 이것으로 주어진 그래프가 Spanning Tree(신장 트리, 최소 연결 부분 그래프)임을 알 수 있다. 따라서, 만약 A → B로가는 연결이 끊어진다면 A → B로는 갈 수 없게 되며 A에서 출발해 B에서 연결된 다른 간..
[백준] 1932번: 정수 삼각형 - JAVA 🔗 문제 링크 BOJ 1932번: 정수 삼각형 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 📝 풀이 과정 위층부터 차례로 누적하며 아래층으로 내려왔을 때, 가장 최대가 되는 수의 합을 구하는 문제이다. 문제대로 해결하는 방법도 있겠지만, 그렇게 되면 제일 마지막 층의 합을 구했을 때 다시 한 번 반복을 돌며 최대값을 찾아야 된다고 생각했다. 이를 반대로 아래에서 위로가며 최대값을 누적하는 방식으로 답을 구했다. for (int i = N - 1; i > 0; i--) { for (int j = 0; j < i; j++) nums[i-1][j] += Math.max(nums[i]..
[백준] 1786번: 찾기 - JAVA 🔗 문제 링크 BOJ 1786번: 찾기 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 📝 풀이 과정 주어진 문자열(T)에서 패턴 문자열(P)를 찾아 인덱스를 구하면 되는 간단한 문제이다. 하지만, 범위가 각각 $1,000,000 = 10^6$이므로 단순하게 문자열을 찾는 이중반복문으로 문제를 해결하려고 하면 $O(NM) = 10^{12}$으로 시간초과가 발생하게 된다. 따라서, 효율적으로 문자열을 찾는 알고리즘인 KMP 알고리즘을 사용해야 한다. 처음 문제를 풀 때, 기존 KMP에서 인덱스를 저장하는 ..
[백준] 1238번: 파티 - JAVA 🔗 문제 링크 BOJ 1238번: 파티 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1️⃣ 플로이드-와샬 📝 풀이 과정 학생(i)가 이동하는 경로는 i -> X -> i이다. 따라서 이동하는데 걸리는 시간은 (i -> X) + (X -> i)이므로 학생마다 걸리는 시간을 모두 구할 수 있는 플로이드-와샬 알고리즘이 생각났다. ⏱ 시간 복잡도 플로이드 와샬의 경우 시간복잡도가 $O(N^3)$인데, 학생의 수는 최대 1000이므로 세제곱을 하여도 $10^9$ 이므로 1초이내에 해..
[백준] 1149번: RGB거리 - JAVA 🔗 문제 링크 BOJ 1149번: RGB거리 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 📝 풀이 과정 만약, N번 집의 색이 빨간색이라면, N + 1의 집의 색깔은 초록색이나 파란색으로 칠하는 경우밖에 존재하지 않는다. 다시 말하면 N번 집의 색이 빨간색이라면 N - 1의 집의 색은 초록색이나 파란색이라는 의미가 된다. 따라서, i번째에서 가장 적은 비용으로 빨간색을 칠하는 경우는 $dp[i][0] = Min(dp[i-1][1], dp[i-1][2]) + cost[i][0]$가 되고..
[백준] 1043번: 거짓말 - JAVA 🔗 문제 링크 BOJ 1043번: 거짓말 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 📝 풀이 과정 진실을 아는 사람이 한 사람이라도 파티에 있게 되면 해당 파티의 사람들은 모두 진실을 알게 된다. 따라서, 진실을 아는 사람과 파티에 참가한적 없는 사람끼리만 존재해야 거짓말을 할 수 있는 파티이다. 같은 파티에 참가한 사람들끼리 연결을 해준 뒤, 진신을 알게된 사람을 기준으로 DFS를 돌며 같은 파티에 참가한 사람들에게 모두 진실을 알려준다. 같은 파티에 참가한 사람들을 모두 진실을 알거나, 모르는 경우이기 때문에 ..

티스토리툴바