뚝딱뚝딱

https://softeer.ai/practice/6292

💡 슈퍼바이러스

• lv1의 "바이러스" 업그레이드 버전
• 입력받는 크기가 더 커지기 때문에, 단순히 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으로의 변환에서 데이터 손실이 있어 결과가 잘 나오지 않았었다.

https://softeer.ai/practice/6284

💡 바이러스

• 단순한 수학문제였다.
• 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으로 선언해주었다.

소프티어 lv2 "금고 털이" 문제 풀이 중 pair vector와 sort사용이 익숙치 않아 정리하는 글이다.

pair vector

vector<pair<int, int>> v;

vector에서는 한 요소에 두가지 값을 함께 넣으려면, 위와 같이 pair로 묶어서 정의해 주어야 한다.

"금고 털이" 문제에서 첫번째 int 요소에는 금속의 무게를 , 두번째 int 요소에는 금속의 가치를 저장해주었다.

각각의 값에 접근하려면, v.first, v.second로 접근할 수 있다.

sort

algorithm에서 정의한 정렬 함수 sort이다.

기본적으로 오름차순 정렬이고, pair vector의 경우 첫번째 값을 기준으로 오름차순 한다.

sort(v.begin(), v.end());

이렇게 하면 vector v를 첫번째 값인 금속 무게에 대해서 오름차순 정렬해준다.

그런데 나는 금속의 가치인 두번째 값에 대해서 내림차순 정렬하고 싶었다.

그래서 sort함수에, 따로 정의한 비교함수를 인자로 넣어, 이 기준으로 정렬해 주세요~라고 요청했다.

bool compare(const pair<int, int> &a, const pair<int, int> &b){
	return a.second>b.second;
}

 위와 같은 compare 함수를 정의해 주었다.

내가 헷갈렸던 점은, 부등호의 방향이다. 

처음에는 b쪽에 크다고 했는데, 이유는 정렬할 때 뒤에 있던게 컸었다..라고 생각한 것이다. 아무튼 나의 착각이고..

내림차순이 앞이 큰거니까, 먼저 위치한 a가 클 때 true로 정의해 주는 것이다.

반대로 오름차순이면? b쪽으로 부등호가 향해야 할 것이다.

이렇게 해서 기본 of 기본인 pair vector와 sort함수에 대해 정리해보았다.

다음에는 버벅거리지 않고 바로 구현하길~

https://softeer.ai/practice/6288

💡 금고 털이

• 무게가 W인 배낭, N개의 금속 종류가 있다.
• 최대의 가치를 갖도록 금속을 담는데, 무게 W를 넘지 않아야 한다.
• 금속은 1g당 가치를 갖는다.
• 따라서 높은 가치를 갖는 순서대로 배낭에 담아야 한다.
• 금속의 무게와 가치를 갖는 pair 벡터를 이용하였다.
• pair 벡터에서 두번째 요소인 가치에 따라 내림차순 정렬 하기 위해, 비교함수인 compare를 정의해주었다.
• 내림차순 정렬 후, 각 금속에 대해서, 무게가 현재의 W를 넘지 않으면, 그 무게만큼 넣고, 그렇지 않으면 W만큼 떼어다 넣기로 한다. 넣은 무게만큼 W에서 차감하는 방식이다.

전체 코드는 아래와 같다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

bool compare(const pair<int, int> &a, const pair<int, int> &b){
  return a.second>b.second;
}//두번째 요소를 기준으로 내림차순 하도록..

int main(int argc, char** argv)
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int W,N;
  cin>>W>>N;

  vector<pair<int, int>> v(N);
  for(int i=0; i<N; i++){
    cin>>v[i].first>>v[i].second;
  }

  sort(v.begin(), v.end(), compare);//두번째 요소를 통해 compare 하도록 비교함수 정의
  
  int value=0;
  for(int i=0; i<N; i++){
    if(W==0) break;
    int used=(v[i].first<=W)?v[i].first:W;
    value+=used*v[i].second;
    W-=used;
  }
  
  cout<<value;
  
   return 0;
}

pair 벡터 정렬만 할 줄 알면 되므로, 아주 쉽다.

https://softeer.ai/practice/6293

💡 징검다리

• 징검다리 문제는 입력이 3*1000까지 이기 때문에 n^2으로 풀이할 수 있다.
• 계수 정렬을 이용하여 풀이한다.
• 각 돌의 계수를 저장하기 위한 크기가 N인 vector를 생성하고, 값을 1로 초기화해준다.
• 1로 초기화 해주는 이유는, 어떠한 돌을 밟더라도 하나의 돌은 밟은 것이므로 1로 시작한다.
• 0번째를 제외하고, 1번째 돌부터 N-1번째 돌까지 순회하면서, 현재 돌이 이전 돌 보다 큰지를 확인한다.
• 0번째 돌부터 현재 돌의 이전 돌까지 중, 현재 돌보다 작은지 확인하고, 작은 돌들 중에서도 가장 큰 계수를 가져오고, 그 값에 1을 더하여 현재 돌의 계수를 설정하는 방식이다.
• 이런식으로 모든 돌의 계수를 설정하고 나서, 가장 큰 계수를 반환하면 그것이 답이 된다.

• 원리
  예시1
  
  

• n=5일때 위와 같이 돌의 높이가 주어졌다고 하자.
• 3은 시작이고, 이전 돌이 없으며 첫 돌이므로 본인을 포함한 1의 값을 갖는다.
• 2를 보면, 앞의 돌인 3보다 작기 때문에, 본인을 포함한 1의 값을 갖는다.
• 1역시, 앞의 돌인 3,2보다 작기 때문에, 본인을 포함한 1의 값을 갖는다.
• 4는 앞의 돌인 3,2,1보다 크고, 이 중 가장 큰 계수 값이 1이므로, 1에 본인을 포함한 1을 더해 2의 값을 갖는다.
• 5는 앞의 돌인 3,2,1,4보다 크고, 이 중 가장 큰 계수 값이 2이므로, 2에 본인을 포함한 1을 더해 3의 값을 갖는다.
• 따라서 최종적으로 가장 큰 계수인 3이 최대로 건널 수 있는 돌의 개수와 같다.

• 예시2
  
  

• • n=7일때 위와 같이 돌의 높이가 주어졌다고 하자.
  • 1까지 앞의 내용과 같다.
  • 6는 앞의 돌인 3,2,1보다 크고, 이 중 가장 큰 계수 값이 1이므로, 1에 본인을 포함한 1을 더해 2의 값을 갖는다.
  • 7은 앞의 돌인 3,2,1,6보다 크고, 이 중 가장 큰 계수 값이 2이므로, 2에 본인을 포함한 1을 더해 3의 값을 갖는다.
  • 4는 앞의 돌인 3,2,1보다 크고, 이 중 가장 큰 계수 값이 1이므로, 1에 본인을 포함한 1을 더해 2의 값을 갖는다.
  • 5는 앞의 돌인 3,2,1,4 보다 크고, 이 중 가장 큰 계수 값이 2 이므로, 2에 본인을 포함한 1을 더해 3의 값을 갖는다.
  • 따라서 최종적으로 가장 큰 계수인 3이 최대로 건널 수 있는 돌의 개수와 같다.

이런식으로 동작하는 것이고, 2줄 for문을 거치기 때문에 n^2의 시간 복잡도가 발생한다.

전체 코드는 아래와 같다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char** argv)
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int N;
  cin>>N;

  vector<int> h(N);//높이를 담을 벡터
  for(int i=0; i<N; i++){
    cin >> h[i];
  }
  
  vector<int> cnt(N,1);//계수를 담을 벡터
  for(int i=1; i<N; i++){
    int cnt_max=0;//이전 계수 중, 돌의 높이가 현재 돌보다 작으면서, 계수가 가장 큰 것을 저장하기 위함
    
    for(int j=0; j<i; j++){
      if(h[i]>h[j]){//이전 돌이 현재 돌보다 작으면
        cnt_max = max(cnt_max, cnt[j]);
      }
    }

    cnt[i]=cnt_max+1;//이전 계수에 현재 돌까지 합쳐서 계수 설정
  }

  cout<<*max_element(cnt.begin(), cnt.end());

   return 0;
}

***참고로 vector의 max값을 반환하기 위해 vector에서 제공하는 max_element() 메서드를 사용했는데, 이 함수는 iterator 즉, 벡터의 요소를 가리키기 때문에, 그 값을 가져오려면 앞에 *를 붙여야 한다.