오늘을 배우고 내일을 개발하다

문제 링크 : https://www.acmicpc.net/problem/18870

[문제]

수직선 위에 N개의 좌표 X₁, X₂, ..., X_N이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
X_i를 좌표 압축한 결과 X'_i의 값은 X_i > X_j를 만족하는 서로 다른 좌표 X_j의 개수와 같아야 한다.

X₁, X₂, ..., X_N에 좌표 압축을 적용한 결과 X'₁, X'₂, ..., X'_N를 출력해보자.

[입력]

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X₁, X₂, ..., X_N이 주어진다.

[출력]

첫째 줄에 X'₁, X'₂, ..., X'_N을 공백 한 칸으로 구분해서 출력한다.

[제한]

• 1 ≤ N ≤ 1,000,000
• -10⁹ ≤ Xi ≤ 10⁹

[알고리즘 분류]

• 정렬
• 값 / 좌표 압축

[해설]

이 문제는 좌표값들을 중복 없이 배열에 크기 순으로 나열했을 때 각 값들의 인덱스를 출력하는 문제였다.

따라서, 배열에 중복 제거 (unique), 정렬(sort)만 어떻게 수행하는지 안다면 쉽게 해결할 수 있는 문제라고 할 수 있다.
우선, 좌표를 입력받아 저장할 배열 두 가지를 선언한다. 여기에서 배열1은 출력할 압축된 좌표들의 순서를 담은 배열이고, 나머지 하나 배열2는 중복된 좌표들을 제거 및 정렬하여 저장할 배열이다.
반복문을 통해 좌표들을 입력받아 두 배열에 저장한 뒤, 중복 제거와 정렬을 수행할 배열에 정렬을 수행하고 중복된 값들이 제거된 배열의 크기 size를 선언한다.

마지막으로는 lower_bound()를 사용해서 배열1에 저장된 좌표들을 순서대로 가져와 각각의 인덱스를 출력할 것이다.
lower_bound()는 찾으려는 key 값보다 크거나 같은 요소를 배열에서 어떤 위치에 처음 등장하는지 찾는 용도로 쓰인다.
(자세한 사용법을 설명하기에는 너무 길어지므로 패스)
이 lower_bound()에서 lower_bound(배열명,범위,찾고자하는 요소) - 배열명 을 수행하게 되면 찾고자하는 요소의 인덱스를 알 수 있는데, 이를 공백으로 나누어 출력하면 해당 문제에서 요구하는 답을 구할 수 있다.

[정답 코드]

#include<bits/stdc++.h>
using namespace std;
int a[1100100],b[1100100],n;
int main(){
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&a[i]);
	b[i]=a[i];
  }
  sort(b,b+n);
  int size=unique(b,b+n)-b;
  for(int i=0;i<n;i++) printf("%ld ",lower_bound(b,b+size,a[i])-b);
}

[결과]

문제 링크 : https://www.acmicpc.net/problem/11659

[문제]

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합하는 프로그램을 작성하시오.

[입력]

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야하는 구간 i와 j가 주어진다.

[출력]

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

[제한]

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

[알고리즘 분류]

• 누적 합

[해설]

이 문제는1  ≤ N ≤ 100,000 와 1 ≤ M ≤ 100,000 라는 제한을 두고있어 단순히 반복문을 이용해 각 입력에 대해 계산을 진행해 출력하도록 한다면 시간초과가 일어나게 된다.
따라서, 입력을 받고 계산을 진행하는 것이 아닌, 이미 계산이 되고 난 후의 값을 배열에 저장해 출력하는 방법을 이용해야한다.
이를 위해서 문제가 원하는 것을 잘 생각해보아야 한다. 우선, 문제가 원하는 것은 특정 범위의 '누적 합' 인데, 이는 배열에 입력되고 난 후에 구할 수도 있지만, 입력과 동시에 누적시킬 수 있다는 것을 알아야한다.

즉, 원래 배열의 i인덱스 에 넣고자하는 값에 가지고 이전 인덱스 i-1의 값을 더하여 i인덱스에 저장하는 과정을 반복한다면 배열에는 자연스럽게 값이 누적되어 저장된다는 말이다.

또한, 여기에서 특정 범위 내에서의 누적 값을 구할 때는 가장 끝에 누적된 값 j에서 누적이 시작되는 범위인 i 이전까지의 누적값을 빼면 된다.

[정답 코드]

#include<ios>
int main(){
  int N,M,i,j,A[100000];
  scanf("%d%d",&N,&M);
  for(int a=1;a<=N;a++){
    scanf("%d",&A[a]);
    A[a]+=A[a-1];
  }
  for(int a=0;a<M;a++){
    scanf("%d%d",&i,&j);
    printf("%d\n",A[j]-A[i-1]);
  }
}

[결과]

문제 링크 : https://www.acmicpc.net/problem/11047

[문제]

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 동전의 가치 A_i가 오름차순으로 주어진다. (1 ≤ A_i ≤ 1,000,000, A₁ = 1, i ≥ 2인 경우에 A_i는 A_i-1의 배수)

[출력]

첫째 줄에 K원을 만드는데 필요한 동전의 개수의 최솟값을 출력한다.

[알고리즘 분류]

• 그리디 알고리즘

[해설]

K원을 만드는데 필요한 동전의 최솟값을 구하는 법은 아주 간단한데, 이는 가지고 있는 동전 중 가장 액수가 큰 동전부터 차례대로 내려오며 0이 될 때까지 빼는 방법으로 구할 수 있다.
이를 로직으로 구현하면 아래와 같이 나타낼 수 있다.

[정답 코드]

#include<ios>
int N,K,cnt,c[10];

int main() {
  scanf("%d%d",&N,&K);
  int i=N-1;
  for(int i=0;i<N;i++) scanf("%d",&c[i]);
  while(K) {
    if(K-c[i]>=0) {
      K-=c[i];
      cnt++;
    }
    else i--;
  }
  printf("%d",cnt);
}

[결과]

문제 링크 : https://www.acmicpc.net/problem/9375

[문제]

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

[입력]

첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.

• 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
• 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.

모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.

[출력]

각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.

[알고리즘 분류]

• 수학
• 자료 구조
• 조합론
• 해시를 사용한 집합과 맵

[해설]

이 문제에서 의상 조합의 경우의 수를 구하는 법은 다음과 같다. = (의상 종류1의 개수+1) x (의상 종류n의 개수+1) - 1

( 1을 빼는 이유는 모두 안 입은 경우의 수를 빼는 것이다. )

따라서, 이 문제는 의상의 이름은 사용하지 않고, 의상의 종류와 map을 사용해 간단하게 해결할 수 있는 문제였다.

의상 종류 p라는 key에 입력되는 값을 map에 의상 종류의 개수 1과 함께 저장하고 그 key 값이 이미 map에 존재한다면 해당하는 key의 value에 +1 을 하는 식으로 의상 종류의 개수를 계산한다.

( map에서 key값은 중복될 수 없고 해당하는 key가 존재하지 않는 상태에서 map[key]++ 를 수행하면 key는 1의 value를 가지고 생성된다. )

그리고, 최종 계산식으로는 앞서 설명했던 공식을 이용해 r(결과값)x=(i.second+1)을 해주고, 거기에서 -1 한 값을 출력하면 값을 얻을 수 있다.

[정답 코드]

#include <bits/stdc++.h>
using namespace std;
int N,M;
string a,p;

int main() {
  cin >> N;
  while(N--){
    cin >> M;
    map<string,int> l;
    int r=1;
    while(M--){
      cin >> a >> p;
      l[p]++;
    }
    for(auto i:l) r*=(i.second+1);
    cout << r-1 << '\n';
  }
}

[결과]

문제 링크 : https://www.acmicpc.net/problem/1764

[문제]

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

[출력]

듣보잡의 수와 그 명단을 사전순으로 출력한다.

[알고리즘 분류]

• 자료 구조
• 문자열
• 정렬
• 해시를 사용한 집합과 맵

[해설]

해당 문제는 set 헤더를 사용하면 아주 간단하게 해결할 수 있는 문제였다.
문제에서는 "듣도 보도 못한 사람의 각 명단에서는 중복된 값이 존재하지 않고, 듣도 보도 못한 사람을 사전순으로 출력한다." 라고 하고 있다.
그렇기에, 원소들을 정렬(오름차순)된 순서로 저장하고, 중복된 원소를 허용하지 않는 set을 사용하면 쉽게 해결할 수 있다.

로직을 보면 아주 간단하다. h와 s라는 set을 선언하고, h에는 듣도 못한 사람의 이름들을 저장한다.
그리고, 보도 못한 사람의 이름을 입력받음과 동시에 h(듣도 못한 사람)에 그 사람의 이름이 존재하는지 h.count(이름) 으로 확인하고, 존재한다면 이 사람의 이름을 s에 저장한다.

이렇게 s에 듣도 보도 못한 사람들의 이름이 저장되었다면, s.size()를 먼저 출력해 듣보잡의 수를 출력하고, 사전순으로 정렬된 사람들의 이름을 차례대로 출력해주면 끝난다.

[정답 코드]

#include <bits/stdc++.h>
using namespace std;
int N,M;
string n;
set<string> h,s;

int main() {
  cin >> N >> M;

  while(N--){
    cin >> n;
    h.insert(n);
  }

  while(M--){
    cin >> n;
    if(h.count(n)) s.insert(n);
  }

  cout << s.size() << '\n';
  for(auto i : s) cout << i << '\n';
}

[결과]

문제 링크 : https://www.acmicpc.net/problem/11726

[문제]

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

[입력]

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

[출력]

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

[알고리즘 분류]

• 다이나믹 프로그래밍

[해설]

이 문제는 다이나믹 프로그래밍으로 분류되어 문제에서 규칙성을 찾아 해결해야하는 문제이다.
문제에 필요한 규칙을 찾는 방법은 다양하겠지만, 필자의 경우에는 1×2, 2×1 타일들이 들어갈 수 있는 경우의 수들을 직접 그려보고 2×3 --> 3, 2×4 --> 5, 2×5 --> 8으로 피보나치 수열 규칙성이 적용되는 것을 확인하여 이를 해결할 수 있었다.

[정답 코드]

#include<ios>
int n,d[1001]={1,1};

int main(){
  scanf("%d",&n);
  for(int i=2;i<=n;i++) d[i]=(d[i-1]+d[i-2])%10007;
  printf("%d\n",d[n]);
}

[결과]

문제 링크 : https://www.acmicpc.net/problem/5525

[문제]

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 P_N이라고 한다.

• P₁ IOI
• P₂ IOIOI
• P₃ IOIOIOI
• P₄ IOIOI...OI ( O가 N개 )

I 와 O 로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 P_N이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

[출력]

S에 PN이 몇 군데 포함되어 있는지 출력한다.

[제한]

• 1 ≤ N ≤ 1,000,000
• 2N+1 ≤ M ≤ 1,000,000
• S는 I와 O로만 이루어져 있다.

[서브태스크]

[알고리즘 분류]

• 문자열

[해설]

이 문제에서 요구하는 것은 입력된 s라는 문자열에 대해 "N+1 개의 I와 N개의 O가 번갈아 반복되는 문자열이 몇 번 나오는가?" 이다.
따라서, 본인도 처음에는 substr(), find() 등을 사용해 문제를 해결해보려 했으나 서브태스크의 조건 1번 밖에 만족하지 못해 50점만을 받았다.
때문에, 제약 조건 없이 문제를 해결할 수 있는 빠른 계산 알고리즘이 필요했다.
문제를 해결하기 위해서 아래와 같은 로직을 사용했는데, 동작 방식은 다음과 같다.

• i 인덱스의 문자가 'I' 인지 확인하고, 맞다면 i+1 번과 i+2 번째 인덱스를 합쳐서 문자열이 IOI가 완성된다면 반복문을 실행한다.
• 반복문 (조건 : i+1 = O, i+2 = I) 내에서는 k=N이 될 때까지 인덱스를 뛰어넘으며 확인하고 목표하는 문자열을 찾는다.
• 반복문 내의 k--는 오른쪽으로 i+2 만큼 이동하면서 k값이 바뀌지 않도록 1을 빼주는 역할을 함 ( k값이 커지면 문자열의 개수 계산 과정에서 답이 맞지 않게됨 )
• 위의 과정을 반복하면서 주어진 s 문자열 내에서 N+1 개의 I와 N개의 O가 번갈아 반복되는 문자열이 몇 번 나오는지 계산한다.

[정답 코드]

#include<iostream>
using namespace std;
int N,M,cnt=0;
string s;

int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  cin >> N >> M >> s;
  for(int i=0;i<M;i++){
    int k=0;
    if(s[i]=='I'){
      while(s[i+1]=='O'&&s[i+2]=='I'){
        k++;
        if(k==N){
          k--;
          cnt++;
        }
        i+=2;
      }
    }
  }
  cout << cnt;
}

[결과]

문제 링크 : https://www.acmicpc.net/problem/1931

[문제]

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹쳐지지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

[입력]

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2³¹-1보다 작거나 같은 자연수 또는 0이다.

[출력]

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

[알고리즘 분류]

• 그리디 알고리즘
• 정렬

[해설]

이 문제는 설명에서 볼 수 있듯, 회의의 시작시간과 끝나는 시간을 받아 모든 회의들 중 가장 일찍 회의가 시작하는 시간 ~ 가장 회의가 늦게
끝나는 시간 사이에서 진행할 수 있는 회의의 최대 개수를 찾는 것이다.
이를 찾기 위해서는, 회의 시간들의 끝나는 시간을 오름차순으로 정렬하여 끝나는 시간 중 최솟값, i=0번 인덱스의 끝나는 시간을 첫 번째로 기준잡아 i+1 인덱스의 회의 시작시간과 i 인덱스의 끝나는 시간 중 끝나는 시간이 더 크다면 다음 인덱스 회의 시간과 비교, 작다면 기준을 i+1 인덱스의 끝나는 시간으로 옮김과 동시에 cnt에 +1을 한다.
그리고 위의 과정을 반복적으로 수행하면 진행할 수 있는 회의의 최대 횟수를 찾을 수 있다.

[정답 코드]

#include<bits/stdc++.h>
using namespace std;

int main(){
  int N,b,e;
  vector<pair<int,int>> t;
  cin >> N ;
  for(int i=0;i<N;i++){
	cin >> b >> e;
	t.push_back(make_pair(e,b));
  }
  sort(t.begin(),t.end());
  int time=t[0].first,cnt=1;
  for(int i=1;i<N;i++){
	if(time<=t[i].second){
	  cnt++;
	  time=t[i].first;
	}
  }
  cout << cnt;
}

[결과]