N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
[입력] 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
[출력] 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
✅ 문제 풀이
처음에 시간초과가 발생했던 접근법
miro라는 함수를 호출하여 (0,0)부터 출발하고, 동,서,남,북에 있는 값이 1이면 각각의 위치에서 miro함수를 재귀호출하는 방식을 통해 count해 나간다.
만약 miro함수에서 현재 위치가 (n-1,m-1)이면 현재까지의 count값과 answer값을 비교해서 작은 것을 answer로 갱신한다.
-> 이렇게 되면 n이 커질수록, 재귀호출 양이 많아져 시간 초과가 발생한다.
queue를 이용해 재귀호출을 하지않고 count하는 방식으로 문제를 해결!
miro함수에 queue를 하나 생성한다. 이 queue는 pair로 <<행,렬>, count>로 데이터를 갖고 있다.
queue에 {{0,0},1}을 추가해서 (0,0)위치에서 1카운트 된 것을 queue에 집어넣는다.
다음의 과정은 queue가 빌때까지 실행한다.
queue의 front에서 행의 값을 r에, 열의 값을 c에, count를 count에 넣는다.
이제 여기는 방문한 것이므로 arr값을 0으로 바꾸어준다.
현재 위치가 (n-1,m-1)인지 확인해서 맞다면, 현재의 count값과 기존의 최소 count가 저장된 answer를 비교해서 더 작은 값으로 갱신해준다.
그리고 for문을 통해 현재 위치에서 상,하,좌,우에 있는 값이 1이면 queue에 해당 좌표와 현재의 count에서 +1한 값을 카운트로 넣어주고, 방문했음을 표시하기 위해 해당 위치의 arr값도 0으로 갱신해준다.
miro함수가 끝나고 나면 answer에는 최소 이동 값만이 저장된다.
✏ 코드 전문
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
int n, m;
int answer = 10000;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
void miro(vector<vector<int>> &arr) {
queue<pair<pair<int, int>, int>> q;
q.push({ { 0, 0 }, 1 });
arr[0][0] = 0;
while (!q.empty()) {
int r = q.front().first.first;
int c = q.front().first.second;
int count = q.front().second;
q.pop();
if (r == n - 1 && c == m - 1) {
answer = min(answer, count);
return;
}
for (int i = 0; i < 4; i++) {
int x = r + dx[i];
int y = c + dy[i];
if (x >= 0 && x < n&&y >= 0 && y < m&&arr[x][y] == 1) {
q.push({ {x,y}, count + 1 });
arr[x][y] = 0;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
vector<vector<int>> arr(n);
for (int i = 0; i < n; i++) {
string str;
cin >> str;
for (int j = 0; j < str.length(); j++) {
arr[i].push_back(str[j] - '0');
}
}
miro(arr);
cout << answer;
}
재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.
각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.
입력 3 2 2 1 5 13 29
출력 1 5 67863915
✅ 문제 풀이
주어진 조건을 보면, n개의 사이트가 항상 일정한 순서대로 m개의 사이트와 연결되어야 하기 때문에, 순서를 고려하지 않는 경우의 수만 구하면 된다.
따라서 m개의 사이트 중 n개를 고르는 조합 문제이다.
mCn을 코드로만 구현하면 된다.
mCn의 수식을 보면 m에서 하나씩 줄여가면서 n개의 수를 곱하고, 1부터 n까지를 곱한 값을 나누어 주면 총 경우의 수와 같다.
☑ 코드 전문
#include<iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
for (int i = 0; i < T; i++) {
int n, m;
cin >> n >> m;
long answer = 1;
int k = 1;
for (int j = m; j > m - n; j--) {
answer *= j;
answer /= k;
k++;
}
cout << answer << "\n";
}
return 0;
}
입력받는 크기가 더 커지기 때문에, 단순히 for문으로 해결하려고 하면, 시간초과가 발생한다.
따라서 분할과 정복을 통해 해결해야 한다.
즉 입력받은 n을 절반씩 쪼개가면서 분할 하고, 다시 합해가면서 전체 문제를 해결하는 방식이다.
이를 위해 solve라는 함수를 생성할 것이고, solve안에서는 solve함수를 재귀적으로 호출하면서 절반씩 나누어 해결한다.
코드를 통해 살펴보자.
public static long solve(long P, long N){
if(N==1) return P;
long res = solve(P, N/2);
if(N%2==0){
return (res*res)%D;
}
else{
res*=res;
res%=D;
return (res*P)%D;
}
}
solve함수는 배수인 P와 거듭 수인 N을 입력으로 받는다.
N이 1이면 P를 반환한다
그렇지 않다면, res를 선언하여 N의 절반만큼 P를 거듭 제곱한 값을 solve를 통해 구하고 저장한다.
만약 N이 짝수였다면, res를 두번 곱한 것에 1000000007을 나눈 나머지 값을 반환하면 된다.
만약 N이 홀수라면, res를 두번 곱한 것에 1000000007을 나눈 나머지에 P를 한번더 곱해주고 또 1000000007을 나눈 나머지를 반환하면 된다. 왜냐하면 홀수의 경우 나누었을 때 나머지 1이 있기 때문에, P를 한번더 곱해주어야 한다는 의미이다.
위의 solve함수를 통해 P의 n거듭제곱 하여 1000000007로 나눈 나머지를 구할 수 있으며, 최종적으로는 k에 곱했어야 했기 때문에, K에 곱한 값에 다시한번 1000000007로 나눈 나머지를 구하면, 답이 된다.
전체 코드는 아래와 같다.
import java.io.*;
import java.util.*;
public class Main {
static long D = 1000000007;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long K = scanner.nextLong();
long P = scanner.nextLong();
long N = scanner.nextLong();
N*=10;
long res = solve(P,N)*K;
res%=D;
System.out.println(res);
}
public static long solve(long P, long N){
if(N==1) return P;
long res = solve(P, N/2);
if(N%2==0){
return (res*res)%D;
}
else{
res*=res;
res%=D;
return (res*P)%D;
}
}
}
이 문제를 풀면서 한가지 알게 된 사실은, long 타입을 입력받을 땐 nextLong으로 받아야 한다는 점이다.
주 언어였던 c++에서 코테를 위한 java를 병행하여 배우면서 입력을 사용한지 얼마 안되었는데, next~가 세부적으로 존재한다는 것을 알게되었다. nextInt로 받으니 long으로의 변환에서 데이터 손실이 있어 결과가 잘 나오지 않았었다.
lost_num이라는 int형 변수에 lost배열의 크기를 저장해두고, 최대로 빌려준 후 남은 학생 수를 저장하도록 하여, n에서 lost_num을 빼 답을 구할 것이다.
n+1 크기의 배열 arr을 생성해서, reserve를 참고해 여벌을 가진 번호에 1을, 아니면 0으로 초기화한다.
근데, 여벌을 가져온 학생 중 도난을 당할 경우 자신의 옷을 입어야 한다. 따라서 lost배열과 arr배열을 비교해서, lost에 있는 번호가 arr배열에서 값이 1이면 0으로 만들고, lost_num을 1 빼준다. 만약 해당하지 않으면 stack에 lost값을 넣는다.
stack이 비워질 때까지, 하나씩 빼가면서 arr배열에서, 현재 peek값+1 또는 peek값-1 번호가 1의 값을 가질 때 둘 중 하나 먼저 해당되는 것을 빌리도록 하고, 그 arr값을 0으로, lost_num을 1 빼준다. 그리고 pop한다.
최종 answer는 n에서 lost_num을 뺀 값이다.
여기서 주의할 점은, lost 배열을 사용하기 전에, 오름차순 정렬해야 한다는 점이다. 로직은 동일했는데, 두 테케에서 자꾸 실패가 떠서 왜 그런가 하고, 정렬을 해봤더니 해결됐다. 항상 입력 배열이 정렬되어 주어질 것이라 장담하지 말고, 정렬하고 시작하는 습관을 기르자.
그리고 나의 풀이 방식의 경우, lost를 오름차순 정렬한 후에, lost 크기만큼 순회하면서 stack에 넣었다. stack에 넣으면 작은 값부터 들어가고, 나올때는 큰 값부터 나오기 때문에, lost+1번호가 여벌이 있는지를 먼저 확인하도록 하였다. 만약 작은 값부터 나오게 짰다면, lost-1번호가 여벌이 있는지를 먼저 확인하도록 해야, 최대의 값을 가질 수 있을 것이다.
전체 코드는 아래와 같다.
import java.util.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = 0;
int[] arr = new int[n+1];
Arrays.fill(arr,0);
for(int i=0; i<reserve.length; i++){
arr[reserve[i]]++;
}
int lost_num=lost.length;
Stack<Integer> st = new Stack<>();
Arrays.sort(lost);
for(int i=0; i<lost.length; i++){
if(arr[lost[i]]==1){
arr[lost[i]]--;
lost_num--;
}else{
st.push(lost[i]);
}
}
while(!st.isEmpty()){
if(st.peek()<n&&arr[st.peek()+1]==1){
arr[st.peek()+1]--;
lost_num--;
}
else if(st.peek()>1&&arr[st.peek()-1]==1){
arr[st.peek()-1]--;
lost_num--;
}
st.pop();
}
answer=n-lost_num;
return answer;
}
}
K에 P를 N번 곱한 후 그값을 1000000007로 나눈 값을 출력하는 문제인데, 그냥 곱할 경우에는 int나 long에 완전히 담을 수 없을 정도로 숫자가 커지기 때문에, 일정한 값으로 나누어 져야 한다.
K에 P를 곱한 후 1000000007로 나눈 나머지를 K에 다시 저장한 후, 그 나머지에 P를 곱하고 또 1000000007로 나눈 나머지를 K에 저장하는 식으로 해결할 수 있다. 이를 N번 반복한다.
어떻게 그게 가능할까?
만약 K=3, P=5, N=3,D(나누는 값)=13이라고 해보자. 1R : 3*5=15, 15%13=2 2R : 2*5=10, 10%13=10 3R : 10*5=50, 50%13=11 답:11 한번에 했을 때 : 3*5*5*5%13 = 375%13=11 답 11
결과는 동일하다.
15*5%13==(13*5%13)+(2*5%13) 위와 같이 15 는 13,2로 분배될 수 있기 때문이다. 어차피 13만큼의 몇배던 13의 배수이므로 그 나머지는 0이되기때문에, 2만큼에 몇 배수를 한 것의 13으로 나눈 나머지만 구하면 된다.
전체 코드는 아래와 같다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long K = scanner.nextInt();
int P = scanner.nextInt();
int N = scanner.nextInt();
int d = 1000000007;
for(int i=0; i<N; i++){
K=(K*P)%d;
}
System.out.println(K);
}
}
참고로 입력 값인 K와 P를 곱했을 때의 최대값의 범위가 10^18~10^19까지 나올 수 있기 때문에 계속해서 갱신되어야 할 K는 long으로 선언해주었다.
누적합 배열을 v라고 할 때, 만약 K=2이면 v[2]-v[0]은 두번째 값까지 더한 값에서 0번째 값까지 더한 값을 빼준 것이고, 이 값은 첫번째값과 두번째값을 더한 것이므로, 단순히 빼기를 통해 구간의 합을 구할 수 있고, 이로써 중복적인 더하기 연산을 피할 수 있으므로 시간을 단축할 수 있다.
예시
예시
주어진 예시에서 5개만을 가져와 보았다.
주어진 5개의 숫자값들이 위의 배열과 같을 때, 아래 v배열은 각 값들의 누적합을 차례로 1번 인덱스부터 채워넣는다.
하나씩 살펴보면, v[1]에는 첫번째 값인 3을, v[2]에는 두번째값까지 더한 값(3+(-2))인 1을, v[3]에는 세번째값까지 더한...
이제 K가 2이므로, 연속한 두 값씩 더한 값을 구해보자. 이는 이미 구해둔 v[K]-v[0] 연산만을 통해 구할 수 있다.
첫번째 연속합을 max로 지정해주고, for문을 통해 K+1부터 N까지 진행하면 된다.
이 방법은, cin으로 숫자값들을 받을 때, 동시에 배열에도 누적합을 더해 놨기 때문에, 이 값을 이용해 차 연산만 해주고, 그 연산 결과가 가장 큰 값을 반환하면 되므로, 시간효율이 아주 좋다!
아래는 전체 코드이다.
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N,K;
cin>>N>>K;
vector<int> v(N+1,0);
for(int i=1; i<N+1; i++){
int temp;
cin>>temp;
v[i]=v[i-1]+temp;
}
int max=v[K];
for(int i=K+1; i<N+1; i++){
max=(max<v[i]-v[i-K])?v[i]-v[i-K]:max;
}
cout<<max;
return 0;
}
이전에 유사한 누적합 문제를 풀어봐서 문제를 보자마자 바로 "누적합!!!"하며 풀 수 있었다.
코딩테스트를 준비하면서 여러 문제를 풀다보니, 점점 문제의 유형이 눈에 보이기 시작한 것 같다.
