난이도 ♦︎♢♢ | 시간제한 1초 | 메모리제한 128MB | 기출 2019 국가 교육기관 코딩테스트 [문제] 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다. 1. 숫자가 쓰인 카드들이 N ✕ M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략..
난이도 ♦︎♢♢ | 풀이시간 30분 | 시간제한 1초 | 메모리제한 128MB | 기출 2019 국가 교육기관 코딩테스트 [문제] 출제자는 큰 수의 법칙을 본인만의 방식으로 다르게 사용하고 있다. 이 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5인 46이 된다. 배열의 크기 N, 숫자가 ..
그리디 알고리즘이란, 현재 상황에서 지금 당장 좋은 것만 고르는 방법. 매순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 최단경로문제는, 플로이드 워셜 혹은 다익스트라 알고리즘 과 같은 알고리즘을 미리 알고 있어야 가능하다. *플로이드 워셜(Floyd Warshall) : 변의 가중치가 음이거나 양인 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이을 찾는다 *다익스트라(Dijkstra) 알고리즘 : 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘 위 알고리즘에 대해서는 추후 더 공부해보겠다. 보통 코딩테스트에서 출제되는 그리디 알고리즘 유형의 문..
