싸피

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS의 대표적인 문제다. 1주일 전에 풀었는데 다시 풀려니깐 생각이 안나고 다시 코드를 찾아보게 돼서 정리하고자 한다. 미로는 배열의 처음부터 시작하고 N,M에 도착하면 끝난다. 그 중에서 가장 최단 거리로 이동할 수 있는 방법을 찾아야 한다. 나는 result 배열을 만들어서 구하고자 했다. 우선 전체 코드이다. package 단계별문제; import java.util.LinkedList; import java.util.Qu..

https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 색종이를 칸에 맞게 가장 최적으로 붙이는 개수를 구해야 하는 문제. 1,2,3,4,5의 nxn사이즈를 가진 색종이가 5장씩 주어지는데 처음에 가장 큰 사이즈부터 완탐을 돌리고 테케는 다 맞았는데 돌려보니 17%인가 18%에서 나가떨어졌다. 최적을 구해야 하니 가장 큰 것부터 돌리는 게 아니라 백트래킹으로 접근해야 문제를 풀 수 있었다. 우선 전체 코드를 보자 import java.util..

https://www.acmicpc.net/problem/19949 19949번: 영재의 시험 컴퓨터공학과 학생인 영재는 이번 학기에 알고리즘 수업을 수강한다. 평소에 자신의 실력을 맹신한 영재는 시험 전날까지 공부를 하지 않았다. 당연하게도 문제를 하나도 풀지 못하였지만 다행 www.acmicpc.net 알고리즘 수업을 수강한다는데 5지 선다의 객관식 10문제를 푼다고 한다. 대신 조건이 동일한 번호로 3개 연속 찍지 않는다는 조건이다. 입력으로 정답 10개가 주어지는데 한 문제에 1점씩 점수를 준다. 이 때 점수가 5점 이상인 모든 경우의 수를 구하면 된다. 문제의 조건 1. 정답이 3개 연속이 아닌 경우를 생각해야 한다. 2. 영재의 점수가 5점 이상인 경우 카운트를 해야 한다. 우선 전체 코드를 ..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 그래프를 공부하고 BFS를 배우면서 가장 기본적으로 접하게 되는 문제다. 그림을 보면 1번과 연결이 된 컴퓨터는 총 4대이다.(1번 제외) 이렇듯 1번 컴퓨터를 통해 바이러스에 걸린 컴퓨터의 수를 출력하면 된다. 우선 전체 코드를 보자 import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.ut..

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 최소 스패닝 트리(MST)에 대한 문제다. 더보기 최소 스패닝 트리란? 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 가중치의 합이 최소인 트리를 말한다. MST개념을 공부하면 가장 처음 접하게 되는 문제다. (골드 4지만 방법을 알면 실버급이라고 생각한다.) MST를 구하는 대표적인 방법으로는 크루스칼, 프림 2가지가 있다. 나는 이중에..