본문 바로가기

백준

 (88)
[백준] 14503 로봇 청소기 (JAVA) 풀이 이 문제는 처음에 보았을떄는 난해하였으나 천천히 보면 크게 두가지로 볼수있다. 해당 위치에서 상하좌우로 탐색하는 경우와 탐색할 수있는곳이 없는 두가지가 있다. 첫번째는 재귀를 이용한 DFS처럼 하여 탐색을 한다, 이때 만약 탐색이 가능하다면 따로 boolean 변수를 이용해 확인을 한다. 이때 역시 재귀를 이용한 DFS를 이용해서 탐색한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main { public static int N, M; public static int[][] map; public st..
[백준] 14500 테트로노미노 (JAVA) 풀이 이 문제를 처음 접근할떄는 어떠한 규칙이 있는지 확인 하였다. 그러나 문득 어느 한점에서 DFS처럼 갈수있는 공간을 하나씩 만들다보면 테트로노미노를 대칭 혹은 회전시킨 도형이 나온다는것을 알아차리고 DFS로 하였다. 물론 이러면서 중복이 발생하는 경우도 있었지만 신경쓰지 않고 진행하였다. 그리고 마지막으로 ㅗ모양을 따로 처리를 해주어야 한다. 또한 중간에 Math.max함수를 사용할수 있음에도 사용하지 않은 이유는 풀이시간이 차이가 나기때문이다. 처음 통과하였을떄는 Math.max를 하였는 결과값이고 두번째는 삼항연산자로 하였는것이다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRead..
[백준] 9251 LCS (JAVA) 풀이 dp를 이용하여 푸는 문제이다 주의해야할점은 dp배열이 2차원이라는 것이다. 나는 아래의 블로그를 참고하였다. https://st-lab.tistory.com/139 [백준] 9251번 : LCS - JAVA [자바] www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAY.. st-lab.tistory.com 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class ..
[백준] 1753 최단경로 (JAVA) 풀이 위 문제는 자료구조에서 접할수있는 기본적인 그래프 문제이다. 이 문제에서는 전부 양의 간선이고 방향이 있기에 다익스트라 알고리즘을 사용하였다 또한 그래프를 탐색할때는 우선순위 큐를 사용했는데 우선순위큐를 사용한 이유에 대해서는 조금더 고민을 해보아야 할것 같다. 코드 import java.io.*; import java.util.*; class Main { static class Node implements Comparable { int end; int weight; public Node(int end, int wright) { this.end = end; this.weight = wright; } @Override public int compareTo(Node o) { return weight -..
[백준] 14502 연구소 (JAVA) 풀이 위의 문제는 BFS와 DFS를 적당히 조합하여 푸는 문제이다. 문제를 푸는 순서는 다음과 같다. 문제에서 벽을 3개를 세워 안전구역의 최대값을 구하라고 하였다. 우리는 벽을 세우고 바이러스를 퍼트리는 일을 한번에 할수 없으니 벽을 먼저 세우고 만약 세운 벽의 개수가 3개이면 바이러스를 퍼트리는 식으로 하였다. 벽을 세우는 과정은 브루트 포스로 처음부터 끝까지 모든 경우의 수를 확인 하였고 바이러스를 퍼트리는 과정은 퍼트리기전 바이러스의 위치를 큐에 전부 넣고 큐에 있는 바이러스 위치를 토대로 하나씩 뽑아 가면서 퍼트릴수있다면 퍼트리고 큐에 추가하는 방식으로 진행하였다. 코드 import java.io.BufferedReader; import java.io.IOException; import java..
[백준] 1011 Fly me to the Alpha Centauri (JAVA) https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 풀이 처음 보았을떄 어렵게 느껴져서 곰곰히 생각하다 스스로 반복문으로 해서 풀었다. 하지만 왜인지는 모르겠으나 오답처리가 되었고 다른 블로그를 보았다. 이번 문제의 경우는 카테고리가 수학이였는데 이러한 문제들을 풀때는 혼자 암산을 하거나 끄적거리면서 풀었는데 앞으로는 암산이 아닌 표형태로 풀어봐야 할것 같다. 풀이는 위의 블로그를 참고하였다. 코드 pa..
[백준] 1759 암호 만들기 (JAVA) https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 이 문제는 기존의 백트래킹문제를 풀어보았다면 쉽게 풀리는 문제였다. 기존의 백트래킹의 문제(N과M문제 시리즈들)들과는 다른점이라면 이번 1759번 암호만들기는 숫자가 아닌 문자가 주어졌다는 것이다. 하지만 그 뿐일뿐 숫자가 문자로 바뀌었다는것을 제외하고서는 전부 동일하다 사전식으로 출력을 한다든지 아니면 어떠한 조건이 있는 점이 말이다. 알고리즘의 개요는 다음과 같다 우선 입력값으로 L C값을 입..
[백준] 5639 이진 검색 트리 (JAVA) https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이 이 문제는 기본적인 BST이다. 필자는 이전에 학교에서 BST를 배웠는데 그때는 c언어로 해서 그렇게 크게 어렵지 않았다. 그러나 지금은 자바로 해서 c언어로 할때보다 새로운 느낌이었다. 아무튼 문제의 풀이를 하자면 자바에서는 포인터의 개념이 없기 떄문에 다음과 같이한다. 1. node라는 클래스를 만들고 attribute로는 값을 저장하는 num과 왼쪽과 오른쪽 자식을 가리키게..
[백준] 14889 스타트와 링크 (JAVA) https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 이 문제를 처음 보았을때는 개인적으로는 실버3 같이 느껴지지 않았다. 나는 처음에 사람들의 집중하기보다는 점수들의 조합에 집중해서 어려웠던것 같다. 알고리즘의 개요는 다음과 같다. 모든 사람들의 조합을 구하고 각 조합당 낼수있는 시너지들의 총합을 구하고 이를 스타트와 링크로 나누너 계산해 가장 작은값을 출력하면 된다. 자세한것은 코드를 보면서 이해가 될것이다. import java.io.BufferedReader..
[백준] 15650 N과 M (2) (JAVA) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 이 문제는 저번에 풀었던 N과 M (1)문제에서 오름차순이 추가되었다는것을 제외하고는 전부 동일하다. 그래도 다시한번 더 설명을 해놓을테니 혹시라도 이러한 문제를 처음풀거나 여전히 어려운 사람들은 보기 바란다. 이 문제는 DFS와 비슷한 백트래킹을 사용한다. 여기서 백트래킹이 무엇이냐 하면 유망하지않은 노드는 선택하지 않는다는것이다. 예를 들어 이번에 포스팅하는 문제를 예시로 들어 설명을 ..

티스토리툴바