본문 바로가기

알고리즘/백준126

[Java] BOJ 13023번 ABCDE 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 DFS를 사용하여 해결했습니다. 문제를 이해하지 못해서 어려웠던 문제였습니다. 간단하게 설명하자면 DFS를 사용하여 문제에서 요구하는 ABCED 즉, 5개의 노드를 한 번에 탐색이 가능하다면 1을 출력하면 되는 문제였습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public clas.. 2021. 7. 15.
[Java] BOJ 17472번 다리 만들기 2 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 BFS와 Prim 알고리즘을 사용하여 해결했습니다. 자세한 내용은 코드의 주석을 참고해주세요. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.St.. 2021. 7. 15.
[Java] BOJ 5582번 공통 부분 문자열 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 풀이 DP를 사용하여 해결했습니다. 문제에서 나온 1번 예시를 풀어보면 ABRACA~ 를 S1이라 하고 인덱스는 i, ECADA~ 를 S2라 하고 인덱스는 j라고 한다면 S1[i] == S2[j]라면 이전까지 연속되는 부분 문자열에 새로 공통된 문자가 들어가므로 S1과 S2에 공통되는 이전 문자인 memo[i -1][j - 1]에 저장된 길이에 + 1을 하여 즉, memo[i -1][j - 1] + 1을 현재 위치에서 공통되는 연속된 부분 문자열인 m.. 2021. 7. 13.
[Java] BOJ 6593번 상범 빌딩 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 풀이 BFS를 이용하여 해결했습니다. 이때, 제 코드에서 Info 클래스의 생성자의 순서는 x, y, z이고 축의 사용은 building[z][y][x] 즉, z는 층, y는 행, x는 열로 사용했어서 주의해야 합니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.uti.. 2021. 7. 12.
[Java] BOJ 2668번 숫자고르기 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 풀이 DFS를 사용하여 해결했습니다. 문제를 잘못이해하여 생각보다 어렵게 해결했던 문제입니다. 문제에서 요구하는 것은 표가 주어졌을때, 표를 배열 arr이라고 생각하고 arr의 모든 인덱스 idx를 DFS의 시작점으로 탐색합니다. 만약 arr[idx] 가 찾고자하는 idx와 같다면 이는 문제에서 요구하는 조건에 맞아 떨어지므로 list에 추가하면 되고 다르다면 arr[idx]로 DFS를 수행하면 됩니다. 자세한 사항은 코드의 주석을 참고해주세요. 코.. 2021. 7. 9.
[Java] BOJ 2981번 검문 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 풀이 유클리드 호제법을 사용하여 해결했습니다. 수학과 관련된 알고리즘에 대해 부족함을 많이 느낄 수 있었던 문제였습니다. 정말 정리가 잘 된 블로그가 있어 링크를 남깁니다. [백준] 2981번 : 검문 - JAVA [자바] www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오 st-lab.tistory.com 코.. 2021. 7. 8.

티스토리툴바