전체 글 (191) 썸네일형 리스트형 변신 이동 게임( BOJ 15906 ) 문제 : https://www.acmicpc.net/problem/15906 15906번: 변신 이동 게임 첫 줄에 2차원 격자의 크기 N(1≤ N ≤ 500), 일반 모드에서 변신 모드로 변신하는 데 소모되는 턴의 수 t(0 ≤ t ≤ 500), 목표 지점의 행과 열의 번호 r(1 ≤ r ≤ N), c(1 ≤ c ≤ N)가 주어진다. 다음 줄에 www.acmicpc.net 문제 파악하기 게임 속 캐릭터를 (1, 1)에서 (r, c)까지 이동하는데 필요한 최소 턴 횟수를 구하는 문제입니다. 캐릭터는 1턴을 사용하여 상하좌우 인접한 1칸으로 움직이거나 t턴을 사용하여 변신 모드로 변신한 다음, 1턴을 사용하여 상하좌우 방향의 가장 가까운 워프 지점('#')으로 이동할 수 있습니다. 각각의 칸에서 이동할 수.. Mowing the Lawn( BOJ 5977 ) 문제 : https://www.acmicpc.net/problem/5977 5977번: Mowing the Lawn FJ has 5 cows whose efficiencies are 1, 2, 3, 4, and 5, in that order. He wants to choose some of the cows such that their total efficiency is maximized, but he cannot choose more than 2 consecutive cows. FJ chooses all cows but the third. The total effici www.acmicpc.net 문제 파악하기 N 마리의 소 중, 연속된 번호의 소를 K마리보다 많이 선택하지 않으면서 효율성이 최대가 되게.. 산만한 고양이( BOJ 14866 ) 문제 : https://www.acmicpc.net/problem/14866 14866번: 산만한 고양이 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 방의 수를 나타내는 정수 N(2 ≤ N ≤ 300,000)과 복도의 수를 나타내는 정수 M(1 ≤M ≤ 300,000)이 주어진다. 다음 M개의 각 줄에는 하나의 복도로 www.acmicpc.net 문제 파악하기 그래프의 사이클을 없애기 위해 제거해야 하는 정점을 찾는 문제입니다. 사이클을 이루는 정점마다 하나씩 제거해서 확인할 수 있지만, 정올 4번 문제답게 입력되는 정점의 개수가 300,000개로 어마어마합니다. 그렇기에 각각의 정점을 제거하는 O(n2) 알고리즘으로는 시간이 부족하며, 좀 더 효율적인 알고리즘이 필요합니다. 여기서 우리가 사용.. 동전 뒤집기( BOJ 1285 ) 문제 : https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 문제 파악하기 2006년 정보올림피아드 고등문제의 small 버전 문제입니다. N*N개의 동전을 뒤집어서 동전의 뒷면(T)이 최소로 보이게 만들었을 때, N*N개의 동전 중 뒷면(T)의 개수를 구하는 문제입니다. 동전은 행 또는 열을 선택한 다음, 선택한 행/열의 모든 동전(N개)를 뒤집을 수 있습니다. N의 범위가 크지 않지만, 나올 수 있는 경우의 수는 어마어마하기 때문에 단순히 .. Ignition( BOJ 13141 ) 문제 : https://www.acmicpc.net/problem/13141 13141번: Ignition 첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000) 두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100) 시작점 www.acmicpc.net 문제 파악하기 모든 간선을 불 태우는데 걸리는 최소 시간을 구하는 문제입니다. 보통 그래프 문제들은 정점에 초점을 맞췄다면 이번 문제는 간선에 초점을 맞춘 문제라고 할 수 있습니다. 간선은 인접한 정점에 불이 붙으면 1초에 1씩 불타며, 양 끝의 정점이 모두 불이 붙었다면 양쪽에서 불타게 됩니다. 문제를 해결하기 위해서는 어떤 정점.. 임계경로( BOJ 1948 ) 문제 : https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 문제 파악하기 임계경로의 길이 및 임계경로에 해당하는 간선의 개수를 구하는 문제입니다. 월드 나라를 그래프로 직접 표현해보면 시작과 종료 정점이 정해져있으며, 싸이클이 없는 그래프로 그려지기 때문에 손쉽게 임계 경로를 구하는 문제라는 걸 눈치챌 수 있습니다. 다만, 임계 경로에 해당하는 간선의 개수를 세기 위해서는 약간의 알고리즘이 필요합니다. 문제 해결하기 우.. 보석 모으기( BOJ 1480 ) 문제 : https://www.acmicpc.net/problem/1480 1480번: 보석 모으기 첫째 줄에 보석의 개수 N, 가방의 개수 M, 가방의 최대 한도 C가 주어진다. N은 1보다 크거나 같고, 13보다 작거나 같은 자연수이고, M은 1보다 크거나 같고, 10보다 작거나 같은 자연수이다. C는 1보 www.acmicpc.net 문제 파악하기 N개의 보석을 M개의 가방에 적절하게 넣어서 챙길 수 있는 보석의 최대 개수를 구하는 문제입니다. 각각의 보석은 1~20그램의 무게를 가지며, 가방에는 최대 C그램의 보석을 담을 수 있습니다. 만약 가방이 한 개라면 입력되는 범위 값이 작기 때문에 브루트 포스 알고리즘으로 충분히 해결할 수 있지만, 가방이 최대 10개까지 있을 수 있기 때문에 좀 더 효율.. 단절점과 단절선 개요 단절점과 단절선은 무방향 그래프에서 각각의 정점 또는 간선을 제거했을 때, 그래프가 나눠지게 만드는 정점(단절점) 및 간선(단절선)을 의미합니다. 단절점과 단절선은 모든 정점에서 DFS를 진행하면 구할 수 있지만, 단 1번의 DFS 탐색으로 모든 단절점과 단절선을 구할 수 있습니다. 그리고 이 개념은 방향 그래프에서 SCC를 나눌 때에도 사용할 수 있습니다. 단절점 구하기 단절점을 구하기 위해서는 DFS 탐색 트리를 만들어야 합니다. DFS 탐색 트리를 만들어서 정점에 방문한 순서대로 번호를 매기고, 각각의 정점에서 갈 수 있는 가장 낮은 위치를 찾는 알고리즘을 사용합니다. 여기서 말하는 가장 낮은 위치란 트리에서 높이가 낮은 정점을 의미하며, 우리는 방문 순서에 따라 트리를 만들고 있기에 방문 순.. 이전 1 ··· 3 4 5 6 7 8 9 ··· 24 다음
