만년다딱2의 개인공간

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 오늘도 알고리즘! 이번 문제는 여행가자 입니다. 문제 설명은 잘 되어 있는 문제이지만 결국 N 만큼의 2차원 배열을 받아서 그래프 연결이 되어있는지 안되어있는지를 묻는 문제입니다. 접근 방식은 Java의 서로소 방식으로 했습니다. makeSet 연산, findSet 연산, union 연산에 대해 공부를 하셨더라면 정말 쉽게 풀 수 있는 문제라고 생각합니다. 데이터를 받으면서 1이 있다면 두 지점을..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 오늘도 알고리즘! 쉬운 계단 수 라는 문제이다. 인접한 모든 자리 수의 차이가 1이 나는 수를 계단수라고 하고 길이가 N인 계단 수를 찾는 문제이다. 다이나믹 프로그래밍으로 풀 수 있는 문제이다. DP 배열을 2차원의 공간으로 생각하고 dp[ 길이 ] [ 0 ~ 9 ] 까지의 공간으로 반복문을 돌면서 계산해 나갈 수 있다. 첫번째 0을 제외한 첫 자리수에 대한 DP값은 1이다. 1, 2, ... , 9 이후 10의 자리 수 부터는 0으로 시작하는 수를 제외하곤 그 전 자리 수의 -1, +1 의 dp값을 더하면 ..

www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 오늘도 알고리즘! 이번에는 완전 탐색 문제인 테트로미노를 풀어보았습니다. 4개의 사각형으로 나올 수 있는 모양 중 나올 수 있는 최대값을 찾는 문제인데요 나올 수 있는 모양들을 모두 대입해보면서 그중 최대값을 탐색하면 됩니다! 접근은 간단하지만 꼼꼼히 조건문을 살펴주셔야 하겠내요. 주석으로 모양별 max비교값을 적어놓았으니 한번 보시면 좋겠습니다. 오늘도 알고리즘! 오늘도 코딩! 코테 파이팅! import j..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 오늘도 알고리즘! 오늘은 간단한 DP문제를 복습한번 해보았습니다. 정수삼각형이라는 문제인데요 위에서 얻을 수 있는 경로의 최대 합을 구하는 문제입니다 데이터 입력을 받으면서 현재 내 윗줄의 왼쪽과 내 윗줄의 바로 위쪽중 큰 값을 더해가면서 그중 최대값을 찾는 문제인데요 간단한 DP연습을 해보기 좋은 문제라고 생각합니다. 오늘도 코딩! 오늘도 알고리즘 파이팅! import java.util.Scanner; public class Main { public static vo..

https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라� www.acmicpc.net 오늘도 알고리즘! 그리디 알고리즘은 풀면 풀수록 사고력에 도움이 된다는 점! 그리디 알고리즘의 상위문제 컵라면 입니다. 먹을 수 있는 최대의 컵라면을 먹어야 하기 때문에! 컵라면을 기준으로 먼저 정렬을 합니다. 그 시간 대에 먹을 수 있는 컵라면의 수가 같다면?! 데드라인을 기준으로 정렬해 줍니다 (사실 큰 차이는 없어요, 이유는 밑에!) Comparable을 사용하여 정렬을 해줍니다. 이후 N+1만큼의..

https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 오늘도 알고리즘! 백준 2636 치즈 라는 문제입니다. 공기와 접촉하는 치즈의 바깥쪽 부터 테두리만 사라지고 공기는 치즈의 밖에있는 외부 공기가 있고 치즈의 안에 있는 내부 공기가 있습니다. 먼저 외부 공기를 2로 초기화 시켜서 눈에 보이도록 만든 다음 외부 공기 주변에 닿이는 치즈가 있다면 그 치즈는 사라집니다. 이것을 임시변수에 저장을 해두고 마지막으로 임시변수에 있던 값들을 clone 시켜 줍니다. 먼저 치즈의..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 오늘도 알고리즘! 직전에 포스팅한 파이프 옮기기 1 문제를 DP 방식으로 풀어보았습니다. 놓을 수 있는 위치에 관한 값들만 고려한다면 입력받으면서도 빠르게 처리할 수 있기때문에 속도에서 확연한 차이가 보입니다. 특정 파이프를 놓을 수 있는 위치에 대해서 DP 값을 본다면 쉽게 풀 수 있는 문제입니다. import java.util.StringTokenizer; import..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 오늘도 알고리즘! 아기 상어 뚜루루뚜둡.... 을 생각하시고 이 문제를 접근하셨으면 매우 혼나셨을 수도 있습니다. 아기상어가 물고기를 먹어가면서 먹을 수 있는 물고기들을 다 먹어가는데 걸리는 거리를 출력하는 문제입니다. 중요한 점은 상어의 현재 위치에서 먹을 수 있는 물고기를 만났을 때 큐를 탐색하면서 가장 짧은 거리의 물고기를 구하고 짧은 물고기가 여러마리라면 더 위에 있는 물고기를,..

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 오늘도 알고리즘! 다딱2의 알고리즘시간입니다! 참고로 저는 롤을 좋아합니다 '만년다딱2' 친추 많이주세요. 각 섬별로 다리를 연결할 수 있는데 길이 2이상인 다리부터 연결할 수 있다고 합니다. 섬의 갯수만큼 다리를 연결시켜서 최솟값을 구하는 문제입니다. 여기서 우리가 중심적으로 봐야하는 것은 왜 '최소 스패닝 트리가' 가 알고리즘 분류로 되어있느냐 입니다. 1. 먼저 입력값에..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 그리디 알고리즘을 정복 프로젝트!!! 그리디 알고리즘의 기초적인 예제 문제라고 볼 수 있는 문제입니다. ATM 순서대로 인출하는 시간의 합의 최솟값을 구하는 방법입니다. 모두 다 해보는 브루스 포스 방법도 있겠지만 이 문제에서 요구하는 사고방식은 SJF라고 생각했습니다. 가장 짧은 시간의 작업을 먼저 처리하는 방식으로 풀어보았습니다. 오름차순 정렬 이후 걸리는 시간들의 합으로 결과를 구할 수 있었습니다. 백준의 그리디 알고리즘..