만년다딱2의 개인공간

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 오늘도 알고리즘 오늘도 코테준비! 특정 상황에 맞게 특정 조건을 구현해 줘야 하는 문제입니다. 오른쪽 밑으로 내려오는 파이프는 괜찮지만 대각선으로 내려가는 파이프는 4칸을 필요로 한다는점! 그리고 파이프가 90도로 안꺽이기때문에 각 파이프 타입별로 기억하기 위해서 재귀를 돌때 파이프의 현재 상태를 들고 다녀야 한다는 점만 기억하시면 쉽게 접근하실 수 잇는 난이도라고 생각합..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 � www.acmicpc.net 도구를 늘리자! 알고리즘을 풀자! 최소 신장(스패닝) 트리를 만들어 보는 문제 '최소 스패닝 트리' 입니다. 최소 신장 트리를 만드는 알고리즘 프림과 크루스칼이 있는데요 저는 크루스칼 알고리즘을 통하여 구현해보았습니다. makeSet, find, union 연산을 통해 서로소 집합으로 대표자를 찾아가면서 서로 연결시키는 방식입니다. 최소 신장 트리..

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라고 생각했습니다. 가장 짧은 시간의 작업을 먼저 처리하는 방식으로 풀어보았습니다. 오름차순 정렬 이후 걸리는 시간들의 합으로 결과를 구할 수 있었습니다. 백준의 그리디 알고리즘..

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954 JUNGOL www.jungol.co.kr 1부터 N까지 갔다가 N에서 1로 돌아오는 최소 비용을 구하는 문제입니다. 가중치가 있는 방향 그래프임을 생각하면서 문제에 접근해봤습니다. 1 다음 부터 N까지의 순열을 먼저 구하고 그 순열마지막에서 1로 갈 수 있으면 최소 비용인지 아닌지를 확인하면서 했습니다. 처음에는 순열만 구하고 값들을 더해가는 방식으로 했을때 시간이 초과되었습니다. 그래서 이후에는 값을 들고다니면서 마지막 지점만 계산을 해주는 방식으로 하니 통과과 되었습니다. 이후 들고다니는 값이 최소값 보다 클 경우 가지치기가 되므로 싹뚝 해주었습니다. 방향 그래프의 문제 연습으로 괜찮은 ..