문제https://www.acmicpc.net/problem/1094 1094번: 막대기지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대www.acmicpc.net 어떻게 풀 것인가?지금부터는 코틀린으로 문제를 풀어보려고 한다. 자바로도 연습하고, 코틀린으로도 연습하기 위해서 시작했다. 조만간 파이썬도 익혀서 문제를 풀어보려고한다. 알고리즘 문제를 풀때 다양한 언어로 연습한다면 그 언어에 대한 라이브러리나 함수 혹은 자료구조 사용에 대해서 익힐 수 있기 때문이다. 자 그렇다면, 이 문제는 무엇인가 간단한 수학 문제였다. 스틱의 길이는 64이다. 원하는 길..
문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 어떻게 풀 것인가? 처음에 문제를 보았을 때 난처했다. 무엇을 말하고자 하는지 잘 모르겠다는 생각이 들어서, 아래에 알고리즘 분류를 참고하였다. 위상정렬?? 이라고 하는 알고리즘에 대해서 공부하게 되었다. 그래프가 주어졌을때, 노드마다 연결된 간선에 방향이 존재하고, 어떤 특정한 노드를 방문하기 위해서는 해당 노드에 진입 가능 이후에 방문이 가능할때 위상정렬을 사용한다고 한다. 위 문제..
문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 어떻게 풀 것인가? 이 문제는 (0, 0)에서 bfs를 실행하여 문제에서 주어진 그림 1, 2, 3과 같이 바깥공기와 2면 이상이 닿은 치즈들을 녹이면서 몇 초 후에 치즈가 전부 없어지는지 구하는 문제이다. 여기서 유의해야할 점은 바깥공기와 내부의 밀폐된 공기를 구분해야한다. -1 인 곳 : 바깥 공기가 존재하는 곳 0인 곳 : 안쪽 공기가 존재하는 곳 1인 곳 : 치즈가 존재하..
문제 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 어떻게 풀 것인가? 기존의 다익스트라 알고리즘을 사용해도 무방하나, 다만 최단경로가 지나온 노드들을 보여줘야 하고, 그리고 지나온 노드들의 갯수를 보여줘야 한다. 이에 나는 route로 지나온 노들을 담으며, 이후에 while 문을 이용하여 routes에 정답의 경로들을 전부다 담는 로직을 세웠다. 출발 노드 -> 목적 노드까지는 모든 노드를 거치지 않을 수도..
문제 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 어떻게 풀 것인가? 처음에 보고 조금 당황스러웠다. DP로 풀기에는 너무나도 큰 수 이다. 아마 처음에 단순 DP로 접근했다면 분명히 시간초과가 발생했을 것이다. 그렇다면 이러한 시간초과 부분을 획기적으로 줄일 수 있는 것이 무엇이 있을까? 바로 행렬이다. 사실 백준알고리즘을 많이 풀어본 이들이라면 위와 같은 피보나치 문제들은 많이 봐왔기 때문에 아래와 같은 점화식은 익숙할 것이다. D(n+2) = D(n+1) + D(n) ( D0 = 0, D1 = 1, n >= 0)..
문제 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 어떻게 풀 것인가? 문제를 읽어보자. 예제 1에서 "mirkovC4nizCC44" 이라는 문자열에 "C4"라는 문자열이 포함되어있으면 모두 없애야 한다. 케이스로 살펴보자. Case 1 : mirkovC4nizCC44 => mirkovnizCC44 Case 2 : mirkovnizCC44 => mirkovnizC4 Case 3 : mirkovnizC4 => mirkovniz(정..
문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 어떻게 풀 것인가? 최단경로 다익스트라 알고리즘을 사용하여 풀어야하는 문제이다. 하지만 무조건 V1와 V2를 지나야 한다. 해결법은 간단하다. 시작점 -> V1 까지 가는 최단경로 비용 V1 -> V2 까지 가는 최단경로 비용 V2 -> 목적지 까지 가는 최단경로 비용 즉, 최단경로를 3번 사용하여 위3개의 최단경로 비용의 합을 구하면 된다. 단 ..
문제 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 어떻게 풀 것인가? 문제를 잘 읽어보자. 웜홀에 들어가면 시간은 뒤로간다. 그말인 즉슨 현재 간선 간의 가중치가 시간이라는 점에서 웜홀의 간선은 음의 가중치를 갖는 것이다. 다시말하면 다익스트라 알고리즘으로는 풀 수가 없다. 그렇다면 문제에서 요구하는 것은 무엇일까? 바로 벨만 - 포드 알고리즘이다. 즉, 현재 문제가 원하는 것은 벨만 포드 알고리즘을 이용하여 음수 사이클이 발생..