전체 글

https://www.acmicpc.net/problem/4803그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로(간선)가 있다면, 두 정점은 연결돼 있다고 한다. 연결 요소는 모든 정점이 서로 연결돼 있는 정점의 부분집합이다. 그래프는 하나 이상의 연결 요소로 이루어져 있다. 트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해 경로가 유일하다. 그래프가 주어질 때, 트리의 개수를 세는 문제다. 문제 탐색하기- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지..

https://www.acmicpc.net/problem/1916N개의 도시와 한 도시에서 다른 도시에 도착하는 M개의 버스가 있다. A번째 도시에서 B번째 도시로 가는데 드는 최소 비용을 출력하는 문제다. 문제 탐색하기- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정ex. 가능한 시간 복잡도, 알고리즘 선택입출력 제한1 ≤ N ≤ 1,0001 ≤ M ≤ 100,0000 ≤ 버스 비용 ≤ 100,000 가중 그래프의 한 정점에서 다른 정점으로 가는 최소 비용 경로를 구할 때, 다익스트라 알고리즘을 사용한다. 다익스트라 알고리즘link-state ro..

https://www.acmicpc.net/problem/183521번부터 N번까지의 도시와 M개의 단방향 도로가 존재하고, 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발해 도달할 수 있는 모든 도시 중 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 문제다. 문제 탐색하기- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정ex. 가능한 시간 복잡도, 알고리즘 선택입출력 제한2 ≤ N ≤ 300,0001 ≤ M ≤ 1,000,0001 ≤ K ≤ 300,0001 ≤ X ≤ N1 ≤ A, B ≤ N (A와 B는 서로 다른 자연수) 최..

https://www.acmicpc.net/problem/11725루트가 없는 트리가 주어지고 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 문제다. 문제 탐색하기- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정ex. 가능한 시간 복잡도, 알고리즘 선택입출력 제한2 ≤ N ≤ 100,000 트리를 탐색하기 위해 너비 우선 탐색(BFS)이나 깊이 우선 탐색(DFS)을 사용할 수 있다. BFS면 queue를 사용하고, DFS면 stack을 사용하거나 재귀 함수로 만들어 진행한다. 너비 우선 탐색(Breath First Search)queu..

https://www.acmicpc.net/problem/2116각 면에 1부터 6까지의 숫자가 적힌 주사위 N개를 쌓으려고 한다. 이때 주사위의 마주 보는 면에 적힌 숫자의 합은 반드시 7이 되진 않는다. 1번 주사위부터 N번 주사위까지 순서대로 쌓을 때, 두 개의 주사위에서 아래에 있는 주사위의 윗면과 위에 있는 주사위의 아랫면의 숫자는 같아야 한다. N개의 주사위를 세웠을 때 사각 기둥이 세워지게 되고, 사각 기둥의 4개의 옆면 중 어느 한 면의 숫자의 합이 최대가 되도록 쌓아 그 값을 구하는 문제다. 문제 탐색하기- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을..

https://www.acmicpc.net/problem/1713학생회장 후보를 일정 기간 동안 전체 학생의 추천에 의해 선정한다. 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보 수만큼 만들었다. 추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 아래와 같다.학생들이 추천을 시작하기 전, 모든 사진틀은 비어있음어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시됨비어있는 사진틀이 없는 경우현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시함현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우, 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제함사진틀에 게시된 사..

https://www.acmicpc.net/problem/5212 다도해의 지도는 R × C 크기의 그리드로 나타나고, 지도의 X는 땅을, .은 바다를 나타낸다. 50년 뒤에 인접한 세 칸 또는 네 칸에 바다가 있는 땅은 모두 잠겨버리고, 이로 인해 지도의 크기도 줄어든다. 지도의 크기는 모든 섬을 포함하는 가장 작은 직사각형이며, 50년이 지난 후에도 섬은 적어도 1개가 존재한다. 지도에 없는 곳 또는 지도의 범위를 벗어나는 칸은 모두 바다이다. 이때 50년 뒤의 지도를 구하는 문제다. 문제 탐색하기- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정..

https://www.acmicpc.net/problem/10157좌석이 C × R 격자형으로 배치된 공연장이 있고, 각 좌석의 번호는 (x, y)로 표시된다. 대기번호를 가진 사람들에 대해 (1, 1) 좌석부터 시작해 시계 방향으로 돌아가면서 비어있는 좌석에 관객을 순서대로 배정한다. 비어있는 공연장의 크기를 나타내는 자연수 C, R이 주어져 있을 때, 대기번호가 K인 관객에게 배정될 좌석 번호 (x, y)를 찾는 문제다. 문제 탐색하기- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정ex. 가능한 시간 복잡도, 알고리즘 선택입출력 제한5 ≤ C, ..