알고리즘문제

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 4 MB (하단 참고) 32854 12480 9700 36.561% 문제 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다..

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

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?contestProbId=AV5PoOKKAPIDFAUq&solveclubId=AYWesuzK3nUDFAQK&problemBoxTitle=6%EC%A3%BC%EC%B0%A8&problemBoxCnt=5&probBoxId=AYdFW2sakzMDFASR+ SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이 문제에서 가장 핵심인 곳은 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K깊이 만큼 지형을 깎을 수 있다는 점이다. K=4가 주어지면 이걸 1,1,1,1 or 1,1,2 이렇게 나눠서 깎는 것이..

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/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상정렬을 처음 배우고 풀은 문제다. 위상정렬은 큐, 스택 두 가지 방법으로 구현이 가능한데 큐를 대부분 많이 사용한다고 해서 큐로 구현하였다. 위상정렬은 순서가 있는 작업을 차례로 진행해야 할 때 순서를 결정하기 위해 사용하는 알고리즘이다. 문제에서 가중치가 안 주어진 유향그래프고 사이클이 없으니 위상정렬로 문제를 접근했다. 우선 전체 코드를 살펴보자...