본문 바로가기

ALGORITHM

 (212)
백준 14925 목장 건설하기 (Java) 1. 문제 링크 14925번: 목장 건설하기 랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다. 그는 목장을 하 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 목장을 건설 가능한 좌표는 true로, 건설 불가능한 좌표는 false로 저장한다. 건설이 가능한 좌표가 나왔으면 해당위치에서 (-1, 0), (-1, -1), (0, -1)의 dp 중 최솟값을 선택하고 1을 더한 값으로 저장한다. 2-1. 앞의 3 좌표는 정사각형의 각 모서리로 포함되는 위치들에서 나왔다 2-2. 그 중 제일 작은 값만큼만 건설이 가능하고, 지금 자리도 건설이 되니까 1을 더했다. 좌표마다..
백준 2775 부녀회장이 될테야 (Java) 1. 문제 링크 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 dp 중 쉬운 편에 속하는 문제이다. 0층에 살고 있는 사람들을 먼저 저장한다. 그것들을 바탕으로 아래층에 살고 있는 사람의 수를 더한다인 줄 알았는데 테케를 보고 점화식을 수정했다. map[i][j] = map[i-1][j]+map[i][j-1] 한 층 아래에 살고 있는 사람과, 옆 집에 살고 있는 사람의 수를 더하면 답이 나온다. 4. 코드 import java.io.BufferedReader; import java.io.InputStream..
백준 21736 헌내기는 친구가 필요해 (Java) 1. 문제 링크 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 BFS를 이용하여 벽이 아닌 공간을 전부 방문한다. P가 나올 경우 결과값을 1씩 더한다. 갈 수 있는 공간을 전부 가면 끝낸다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.io.IOExceptio..
백준 17070 파이프 옮기기 1 1. 문제 링크 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 하나씩 움직여보는 풀이와 dp 풀이가 있다. 첫번째 방식은 메모리는 402,508KB, 시간은 880ms 가 나온다. 두번째 방식은 메모리는 11,564KB, 시간은 76ms가 나온다. 확실히 dp가 성능 면에서 우수하다. 4. 코드 1) 구현, 시뮬레이션 import java.io.BufferedReader; import java.io.IOException; import java...
백준 10971 외판원 순회2 (Java) 1. 문제 링크 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 외판원 순회 문제로 전형적인 TSP 문제이다. 가장 적은 비용으로 순회를 해야하기 때문에 순열로 방문할 도시의 순서를 정했다. 또한 순회라는 것이 첫 출발점으로 다시 돌아오는 것이기 때문에 시작점은 1번으로 잡고 했다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.I..
백준 1874 스택 수열 (Java) 1. 문제 링크 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 입력받은 값이 지금 들어간 값보다 크면 값을 스택에 넣는다. 그 후에 입력받은 값이 들어가있는 값과 같으면 스택에서 꺼낸다. 입력받은 값이 들어가있는 값보다 작으면 top에 있는 것을 꺼낸다. push와 pop을 반복하면서 해당 수열이 나오는지 확인하면 된다. 4. 코드 import java.io.BufferedReader;..
백준 1966 프린터 큐 (Java) 1. 문제 링크 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 큐에 입력받은 문서의 번호와 중요도를 넣는다. 그리고 중요도는 따로 list에 저장해서 중요도가 가장 높은 문서를 찾기 위해 사용한다. 이 중요도는 Collections.reverseOrder()로 숫자가 큰 순서, 즉 내림차순으로 정렬한다. 큐에서 하나씩 빼면서 중요도가 가장 높은 문서가 아니라면 다시 큐에 넣는다. 중요도가 가장 높은 문서는..
백준 1463 1로 만들기 (Java) 1. 문제 링크 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 DP 문제인데 하향식으로 풀었다..ㅎㅎ N부터 3으로 나눠지는 경우, 2로 나눠지는 경우, 그리고 1을 빼는 경우로 해서 그 몫을 배열에 있는 값과 현재 수+1 값과 비교해서 작은 값을 넣는다. 1까지 진행하면서 배열의 1번에 저장된 값을 출력한다. 4. 코드 import java.io.IOException; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) throws IO..

티스토리툴바