❓문제https://www.acmicpc.net/problem/11657성능 요약메모리: 34456 KB, 시간: 788 ms분류그래프 이론, 최단 경로, 벨만–포드문제 설명N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.✍🏻풀이벨만 포드 알고리즘을 사용한다. 사이클을 확인은 아래 사이트를 참고하면 된다.https://growth-coder.tistory.com/2..

❓문제https://www.acmicpc.net/problem/1504성능 요약메모리: 126204 KB, 시간: 376 ms분류그래프 이론, 최단 경로, 데이크스트라문제 설명방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.✍🏻풀이우선 주어진..

❓문제https://www.acmicpc.net/problem/9655성능 요약메모리: 32544 KB, 시간: 36 ms분류수학, 다이나믹 프로그래밍, 게임 이론 문제 설명돌 게임은 두 명이서 즐기는 재밌는 게임이다.탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.✍🏻풀이N = 1 일 때는 상근이가 이긴다.N = 2 일 때는 창영이가 이긴다.N = 3 일 때는 상근이가 3개를 모두 가져가거나 1 개씩 가져가서 상근➡️창영➡️상근으로 상근이가 이긴다.이 상황으로 봤을 때 N..

❓문제https://www.acmicpc.net/problem/2630성능 요약메모리: 111040 KB, 시간: 116 ms분류분할 정복, 재귀문제 설명아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다..

❓문제https://www.acmicpc.net/problem/11404성능 요약메모리: 111660 KB, 시간: 164 ms분류그래프 이론, 최단 경로, 플로이드–워셜문제 설명n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.✍🏻풀이플로이드 워셜 알고리즘을 구현하면 된다.a에서 b로 가는데 중간에 다른 도시를 경유하는 경우와 한 번에 가는 경우 중 가중치가 최소인 경우를 기록하면 된다.가중치 계산이 끝나고 출력할 때 a에서 b로 갈 수 없는 곳..

❓문제https://www.acmicpc.net/problem/14500성능 요약메모리: 114816 KB, 시간: 152 ms분류구현, 브루트포스 알고리즘 문제 설명폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.정사각형은 서로 겹치면 안 된다.도형은 모두 연결되어 있어야 한다.정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.테트로미노 하나를 적절히 놓아서 테트로미노가 ..