뚝딱뚝딱

소프티어 부트캠프 3기 코딩테스트를 보고 온 후기이다.

일단.. 2개는 완벽히 풀었다고 생각했는데, 갑자기 끝나고 나서 치명적인 실수를 해버린게 생각났다.

그리하여 예상은 1솔..

일단 전체적인 총평은.. 너~~무 어려웠다. 

문제 자체가 설명이 너무 길고, 복잡하기도 하고, 읽고 있는데 무슨 말인지를 모르겠다.

그래서 일단 간단해 보이는 문제를 먼저 풀이했는데, 하나는 모의 테스트에 나온 걸 입력 형태를 조금 변형해서 냈고, 그냥 똑같은 문제였다.

다른 하나는 계수기 만들기 문제인데, 하...이걸 진짜 열심히 생각해냈는데, 마지막에 답을 아무생각없이 내가지구.. 다 푼걸 딱 한번 생각을 못해서 틀린 케이스이다. 일단 테케는 통과했는데, 문제에서 예시로 나온 것만 넣어봤어도 바로 수정했을텐데, 내가 봤을 땐 트릭으로도 이 예제를 테케에 안넣어둔 것 같다.

너무 아쉬운 ... 코테였다.

그리고 소프티어 부캠 코테는 문제를 pdf 사진으로 첨부해놓는데, 처음에 이 pdf가 열리지 않아서 문제를 확인할 수가 없었다. 다행히 시스템 문제였고, 이것 땜에 전체가 20분 늦게 시작했다. (좀 서툰 느낌..?)

문제는 총 7문제, 시간은 6시 20분 부터 8시 40분까지 총 140분 봤다.

1번 문제는, 배?인가 어디에 입력으로 주어진 것들을 태우는데, 뭐 농부랑 뭐가 같이 타면 안되고..이런 조건이 엄청 많았다. 문제 이해부터 안되서 패스했다.

2번 문제는 bfs인 것 같기도 하고.. n개의 마을이 있고 연료가 k일 때 주어진 경로에서 물건을 사고 팔고.. 그때의 비용이며.. 아무튼 최종 답은 최대의 이익을 내는 경로와, 그 때의 최대 이익, 그리고 잔여 연료를 출력하는 것이었다.

소프티어 입력도 출력도 너무 복잡해서 솔직히 힘들었다.

3번 문제는 이전 부캠 코테 기출을 좀 더 난이도 높혀서 변형한 느낌. 

백준에 있는 쿼드 트리 문제 같은 느낌인데, 그런 배열을 하나 주고서는, 0은 물 1은 섬이라고 하고, 강의 넓이와 그 안에 있는 섬, 강의 넓이를 계속 출력하는 문제였다. 분할과 정복 문제 인 것 같다.

4번 문제는 모의고사로 나왔던 문제이다. 배열에서 연속적인 영역의 개수와 영역의 크기를 구하는 문제이다. bfs 문제이다.

5번 문제는 도메인 주소와 ip 주소를 이용하는 것이었는데, 입력으로 유형을 적어서 도메인을 등록하거나 검색하도록 하는 것이다. 이것도 너무 복잡..

6번 문제는 계수기 만들기 문제.. 이거 첨에 포기하려다가 끈질기게 잡고 겨우 풀어냈는데, 마지막에 출력 내는 과정에서 실수가 있었던 게 생각나 버려서 아깝게 1솔 버려졌다... ㅠㅠ

7번은 뭐였는지 기억이 안난다.

정말 하고싶었는데... 코드만 봐서라도 합격 시켜줄 순 없는 건가요...ㅠㅠ

좋은 소식으로 찾아왔으면!

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으로 선언해주었다.

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 즉, 벡터의 요소를 가리키기 때문에, 그 값을 가져오려면 앞에 *를 붙여야 한다.