전체 글

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, ..

https://www.acmicpc.net/problem/13164N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 1명 있어야 하고 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원 수가 같을 필요는 없다. 나뉘어진 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 티셔츠를 만드는 비용이 생길 때, K개의 조에 대해 티셔츠를 만드는 비용의 합을 최소로 하는 문제다. 문제 탐색하기- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정ex. 가능한 시간 복잡도, 알고리즘 선..

https://www.acmicpc.net/problem/182302 × N 크기의 바닥에 2 × 1 크기의 타일 A개와 2 × 2 크기의 타일 B개를 붙이려고 한다. 각 타일들에는 "예쁨"의 정도가 있고, 예쁨이 최대가 되도록 타일링을 하는 문제다. 문제 탐색하기- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정ex. 가능한 시간 복잡도, 알고리즘 선택입출력 제한1 ≤ N, A, B ≤ 2,000N ≤ 2 × B + A1 ≤ 예쁨 ≤ 1,000,000 예쁨이 최대가 되도록 하기 위해 입력받은 정수 A개와 B개를 정렬해야 한다. n이 홀수인 경우 A ..