❓문제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 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.테트로미노 하나를 적절히 놓아서 테트로미노가 ..

❓문제https://www.acmicpc.net/problem/14502성능 요약메모리: 116952 KB, 시간: 1284 ms분류구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 격자 그래프 문제 설명인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는..