dotdotdot

https://www.acmicpc.net/problem/10282문제 설명최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오. 📌 시간 제한: 2초입력첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각 테스트 케이스는 다음과 ..

https://www.acmicpc.net/problem/23324문제 설명연두는 방금 "플로이드 와샬 알고리즘"을 공부했다. 이 알고리즘은 \( N \)개의 정점으로 이루어진 그래프에서, 모든 정점 쌍의 최단 거리를 \( O(N^3) \)에 구해준다.신이 난 연두는 자신이 좋아하는 그래프를 하나 가져왔다. 이 그래프는 \( N \)개의 정점과 \( M \)개의 양방향 간선으로 이루어진 단순 연결 그래프이며, 정점에는 \( 1, 2, \ldots, n \)으로 번호가 매겨져있다. 또한 딱 하나의 간선에만 1의 가중치가 있고 나머지 간선은 가중치가 0이다.이제 이 그래프에서 모든 정점 쌍의 최단 거리의 합을 구해보려고 한다. 즉, \( 1 \le i 연두는 신나서 코드를 짰지만 한참 동안 기다려도 결과가 ..

현실 세계에서 우리는 종종 어떤 출발지에서 목적지까지 가장 빠른 길, 가장 저렴한 경로, 혹은 가장 짧은 통신 경로를 찾아야 할 때가 있다. 이런 문제들은 그래프라는 수학적 구조로 표현할 수 있다. 그래프는 정점(노드)과 간선(정점 간 연결선)으로 구성되며, 간선은 이동에 필요한 비용, 거리, 시간 같은 가중치를 가진다. 그래프는 유방향(방향이 있는 간선)일 수도 있고, 무방향(양쪽으로 이동 가능한 간선)일 수도 있다. 다익스트라 알고리즘은 둘 모두에 적용할 수 있으며, 무방향 그래프에서는 각 간선을 양 방향 모두 등록해야 한다. 예를 들어, \( u \)와 \( v \) 사이에 간선이 있다면, \( u \to v \), \( v \to u \) 모두 추가해주어야 다익스트라 알고리즘이 정상 동작한다.문제..

https://www.acmicpc.net/problem/2580문제 설명스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.나머지 빈 칸을 채우는 방식은 다음과 같다.각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이..

https://www.acmicpc.net/problem/7562문제 설명체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 📌 시간 제한: 1초입력입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.출력각 테스트 케이스..

https://www.acmicpc.net/problem/5014문제 설명강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)강호가 G층에 도착..

우리가 알고리즘을 공부하면서 마주치는 수많은 문제들 — 예를 들면 미로 탈출, 경로 찾기, 친구 관계 분석, 조직도 순회 등 —은 겉보기에는 다양해 보이지만 결국 "대상들 간의 연결 관계를 어떻게 탐색할 것인가"라는 문제로 귀결된다.이때 필요한 개념이 바로 그래프(Graph)다. 그래프는 노드(정점)과 간선(연결선)으로 이루어져 있으며, 정점은 어떤 대상(예: 도시, 사람, 웹페이지 등)을, 간선은 그들 사이의 관계(예: 도로, 친구 관계, 하이퍼링크 등)를 나타낸다. 그래프를 활용한 문제를 해결하려면, 그래프 자체를 어떤 방식으로 표현할 것인가가 먼저 결정되어야 한다.이를 위해 보통 그래프를 코드로 표현하는 두 가지 방식, 즉 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency ..

https://www.acmicpc.net/problem/9465문제 설명상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성..

https://www.acmicpc.net/problem/2156문제 설명효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포..

https://www.acmicpc.net/problem/2579문제 설명계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.계단 오르는 데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.마지막..