https://www.acmicpc.net/problem/30024 30024번: 옥수수밭 옥수수밭 주인 민석이는 한 해 동안 열심히 기른 옥수수를 수확하려고 한다. 옥수수밭은 $N$행 $M$열의 격자로 생각할 수 있는데, 격자의 각 칸에는 한 그루의 옥수수가 심어져 있다. 민석이는 각 www.acmicpc.net 알고리즘 분류 그래프 탐색(너비 우선 탐색: BFS) 우선순위 큐 Hint 시간 제한이 1초이고 K가 최대 10만이기 때문에 최악의 경우 O(N^2)이기 때문에 시간 초과가 발생합니다 우선 순위 큐의 알고리즘을 이용한다면 쉽게 접근이 가능합니다. 해설 #include #include #include using namespace std; int main() { // 입출력 시간 단축 코드 ios..

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 알고리즘 분류 그래프 탐색(깊이 우선 탐색: DFS) 해설 #include #include using namespace std; int main() { int N; cin >> N; int** G = new int* [N]; // 연결 그래프 배열 int** result = new int* [N]; // 출력 그래프 배열 for (int i = 0; i < N; i++) { G[i] = new int[N]; result[i]..

https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 알고리즘 분류 그래프 탐색(BFS, DFS) 해설 #include #include using namespace std; int main() { int N, M, ix, iy; cin >> N >> M; char** campus = new char* [N]; bool** visit = new bool* [N]; for (int i = 0; i < N; i++) { campus[i] = ..

https://www.acmicpc.net/problem/1932 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 알고리즘 분류 Dynamic Programming 해설 #include using namespace std; int main() { int N; cin >> N; int** triangle = new int* [N]; // 삼각형의 수를 저장하는 2차원 배열 int** score = new int* [N]; // 합계를 저장하는 2차원 배열 for (in..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 알고리즘 분류 BFS(너비 우선 탐색) 해설 #include #include using namespace std; int main() { int n, m; cin >> n >> m; int** map = new int* [n]; bool** visit = new bool* [n]; for (int i = 0; i < n; i++) { map[i] = n..

https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net Hint 신입 사원의 성적을 리스트로 묶어 서류 심사 점수 순으로 정렬합니다. 서류 심사 점수 1등의 신입 사원의 면접 성적 순위를 max_rank로 정합니다. 그 뒤 인덱스의 신입 사원들은 자동으로 서류 심사 순위가 낮으므로 max_rank보다 작아야(순위가 높아야) 신입 사원이 될 수 있습니다. 또한 새로운 신입 사원이 결정된 경우 그 신입 사원의 max_rank는 계속해..