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

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

[문제]

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)는 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

[출력]

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

[알고리즘 분류]

• 다이다믹 프로그래밍

[해설]

이 문제에서는 보기로 피보나치를 구현한 로직을 보여주고 있다. 물론, 제시된 보기와 같이 재귀함수로 피보나치 수를 구할 수는 있지만, 문제에서 요구하는 시간 제한인 0.25초를 만족할 수는 없다. (문제에서 최대 값으로 입력될 수 있는 40과 같은 수가 입력되면 많은 재귀가 발생하여 시간초과가 일어나기 때문이다.)
따라서, 시간 제한 요구를 만족하기 위해서는 피보나치 수들이 출력하는 0과 1의 개수 사이의 규칙성을 찾고 이를 미리 저장해 수가 입력되면 저장된 인덱스를 찾아 출력하는 방식으로 해결해야한다.
모든 수들의 0, 1이 출력되는 개수를 찾기 위해, 문제에서 보기로 주어진 로직을 사용해 각 피보나치 수들의 0과 1의 개수를 계산해본 결과 다음과 같은 결과가 나왔다.

숫자 = 0 에서 0이 출력된 횟수: 1, 1이 출력된 횟수: 0
숫자 = 1 에서 0이 출력된 횟수: 0, 1이 출력된 횟수: 1
숫자 = 2 에서 0이 출력된 횟수: 1, 1이 출력된 횟수: 1
숫자 = 3 에서 0이 출력된 횟수: 1, 1이 출력된 횟수: 2
숫자 = 4 에서 0이 출력된 횟수: 2, 1이 출력된 횟수: 3
숫자 = 5 에서 0이 출력된 횟수: 3, 1이 출력된 횟수: 5
숫자 = 6 에서 0이 출력된 횟수: 5, 1이 출력된 횟수: 8
숫자 = 7 에서 0이 출력된 횟수: 8, 1이 출력된 횟수: 13
숫자 = 8 에서 0이 출력된 횟수: 13, 1이 출력된 횟수: 21
숫자 = 9 에서 0이 출력된 횟수: 21, 1이 출력된 횟수: 34
숫자 = 10 에서 0이 출력된 횟수: 34, 1이 출력된 횟수: 55

각 숫자들에서 0과 1이 출력된 횟수를 보면 0을 제외하고는 모든 수의 0과 1의 출력 횟수에서 피보나치 수열의 규칙이 적용되는 것을 볼 수 있다.
이를 이용해 아래와 같은 로직을 구성할 수 있다.

[정답 코드]

#include <ios>
int T,N,zero[41]={1,0,1,1},one[41]={0,1,1,2};

int main() {
  scanf("%d",&T);
  for(int i=4;i<41;i++){
    zero[i]=zero[i-2]+zero[i-1];
    one[i]=one[i-2]+one[i-1];
  }
  while(T--){
    scanf("%d",&N);
    printf("%d %d\n",zero[N],one[N]);
  }
}

[결과]

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

[문제]

2019 HEPC - MAVEN League의 "비밀번호 만들기"와 같은 방식으로 비밀번호를 만든 경민이는 한 가지 문제점을 발견하였다. 비밀번호가 랜덤으로 만들어져서 기억을 못한다는 것이었다! 그래서 경민이는 메모장에 사이트의 주소와 비밀번호를 저장해두기로 했다. 하지만 컴맹인 경민이는 메모장에서 찾기 기능을 활용하지 못하고 직접 눈으로 사이트의 주소와 비밀번호를 찾았다. 메모장에 저장된 사이트의 수가 늘어나면서 경민이는 비밀번호를 찾는 일에 시간을 너무 많이 쓰게 되었다. 이를 딱하게 여긴 문석이는 경민이를 위해 메모장에서 비밀번호를 찾는 프로그램을 만들기로 결심하였다! 문석이를 도와 경민이의 메모장에서 비밀번호를 찾아주는 프로그램을 만들어보자.

[입력]

첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다.
두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번호가 공백으로 구분되어 주어진다. 사이트 주소는 알파벳 소문자, 알파벳 대문자, 대시('-'), 마침표('.')로 이루어져 있고, 중복되지 않는다. 비밀번호느는 알파벳 대문자로만 이루어져 있다. 모두 길이는 최대 20자이다.
N+2번째 줄부터 M의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소가 한줄에 하나씩 입력된다. 이때, 반드시 이미 저장된 사이트 주소가 입력된다.

[출력]

첫 번째 줄부터 M개의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소의 비밀번호를 차례대로 각 줄에 하나씩 출력한다.

[노트]

입출력 방식이 느리면 여러 줄을 입력받거나 출력할 때 시간초과가 날 수 있다.
C++을 사용하고 있고 cin / cout 을 사용하고자 한다면, main 함수 안에 cin.tie(NULL) 과 ios::sync_with_stdio(false)함수를 둘 다 호출해주고, endl 대신 개행문자 ( \n )를 쓰자. 단, 이렇게 하면 더 이상 scanf / printf / puts / getchar / putchar 등 C의 입출력 방식을 사용하면 안된다.
Java를 사용하고 있다면, Scanner와 System.out.println 대신 BufferedReader와 BufferedWriter를 사용할 수 있다. BufferedWriter.flush는 맨 마지막에 한 번만 하면 된다.

[알고리즘 분류]

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

[해설]

이 문제는 unordered_map 해시 구조를 사용할 줄 안다면 쉽게 해결할 수 있는 문제다. 우선, 사이트 주소와 비밀번호는 문자열로 입력받아야 하므로 해시 또한 문자열로 받도록 unordered_map<string,string> s;로 선언한다.
그리고, 주소와 비밀번호를 입력받을 변수 adr, pwd를 선언하고 반복문에서 이를 이용해 입력, 해시에 저장하는 과정을 N번 수행한다.
이렇게 저장된 해시는 반복문을 이용해 키 이름을 입력받아 호출하여 출력할 수 있다.

[정답 코드]

#include <iostream>
#include <unordered_map>
using namespace std;

int N,M;
string adr,pwd;
unordered_map<string,string> s;

int main() {
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin >> N >> M;
  while(N--){
    cin >> adr >> pwd;
    s[adr] = pwd;
  }
  while(M--){
    cin >> adr;
    cout << s[adr] << '\n';
  }
}

[결과]

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

[문제]

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형의 변의 길이는 1이다. 그다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.
파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개의 숫자는 1,1,1,2,2,3,4,5,7,9이다.
N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

[출력]

각 테스트 케이스마다 P(N)을 출력한다.

[알고리즘 분류]

• 수학
• 다이나믹 프로그래밍

[해설]

P(N), 나선에 있는 정삼각형의 변의 길이는 일정한 규칙을 가지고 크기가 정해진다. 이 문제에서 찾을 수 있는 규칙성은 l[i] = l[i-2]+l[i-3] 이다. ( 예시로 주어진 P(1)~P(10)의 값 1,1,1,2,2,3,4,5,7,9 를 보면 알 수 있다. )
이 규칙을 이용해 로직을 구성하면 아래와 같이 나타낼 수 있다.

[정답 코드]

#include<ios>
int T,N;
long long l[101]={0,1,1};
int main(){
  for(int i=3;i<101;i++) l[i]=l[i-2]+l[i-3];
  scanf("%d",&T);
  while(T--){
    scanf("%d",&N);
    printf("%lld\n",l[N]);
  }
}

[결과]

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

[문제]

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한 가지 예이다.

[입력]

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

[출력]

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

[알고리즘 분류]

• 다이나믹 프로그래밍

[해설]

아래의 문제와 비슷한 문제들은 모두 일정한 규칙성(공식)을 가지고 있다.
이 문제에서 제시하는 조건대로 생각해보았을 때 1 -> 1, 2-> 3, 3-> 5, 4-> 11, 5 -> 21  와 같이 각 입력값에 대해 보이는 것과 같은 결과가 나타나게 된다.
이 결과값들에서는 다음과 같은 규칙성을 찾을 수 있다. ( i는 각 결과값들의 인덱스, i = ( i - 1 + 2 * i - 2) % 10007 )

이 규칙성을 가지고 로직을 구성해본다면 아래와 같은 코드를 나타낼 수 있다.

[정답 코드]

#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]+2*d[i-2])%10007;
  printf("%d",d[n]);
}

[결과]

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

[문제]

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 힘을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

n은 양수이며 11보다 작다.

[알고리즘 분류]

• 다이나믹 프로그래밍

[해설]

문제에서는 1, 2, 3의 합 만으로 주어진 숫자들을 나타낼 수 있는 경우의 수를 출력하라고 한다.

주어진 시간과 알고리즘 분류를 보면 단순히 반복문을 통해 경우의 수들을 구하는 것이 아니라, 문제에 존재하는 규칙을 알아야 풀 수 있는 문제였다.

해당 문제에서 찾을 수 있는 규칙성은 주어진 수 n을 나타낼 수 있는 1, 2, 3들의 합의 경우의 수는 (n-1)+(n-2)+(n-3)으로 나타낼 수 있다는 것이다.

예를 들면, 1은 { 1 }로 총 1개의 경우, 2는 { 1+1, 2 }로 총 2개의 경우, 3은 { 1+1+1, 2+1, 1+2, 3 } 으로 총 7개의 경우, 즉, (n-1)+(n-2)+(n-3) 으로 나타낼 수 있다.

이는 이후의 숫자들에도 적용되어 아래와 같은 로직을 구성할 수 있다.

[정답 코드]

#include<ios>
int n,x,d[]={0,1,2,4,7,13,24,44,81,149,274};

int main(){
  scanf("%d",&n);
  while(n--){
    scanf("%d",&x);
    printf("%d\n",d[x]);
  }
}

[결과]

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

[문제]

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

[입력]

각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

[알고리즘 분류]

• 자료구조
• 문자열
• 스택

[해설]

처음 입력 예시를 보면 복잡해보일 수도 있으나 "균형잡힌 세상" 문제에서는 입력되는 문자열 중 소괄호"()"와 대괄호"[]"에 대한 대칭 여부를 판단하는 것이 목적이므로 이외의 다른 문자열은 모두 무시하고 괄호에 관한 것에 대해서만 비교를 진행하면 된다.
그리고, 문자열 내에 존재하는 괄호의 대칭 여부는 스택 자료구조에 대해서 이해하고 있다면 쉽게 알아낼 수 있는 요소이다.
우선, 스택은 후입선출(Last In First Out) - "가장 나중에 들어온 것이 먼저 나간다" 의 자료구조이다. ( 탑을 쌓아놓고 위에서부터 층을 하나씩 제거하는 모습을 연상하면 된다. )

문제에서는 괄호가 한 번 열리면 적정한 위치에 닫는 괄호가 오는지를 판단하고자 한다. ( "( [ ) ]" 와 같이 서로 엉켜있는 괄호는 포함하지 않는다. )
따라서, 스택을 이용해 처음 괄호가 열리게 되면 "(" 혹은 "[" 를 스택 자료구조에 저장하고, 이에 대한 닫는 괄호 ")" 혹은 "]" 가 나타난다면 스택에서 top() 요소( 괄호가 대칭일 경우, 스택에서의 top() 요소는 항상 닫는 괄호에 대해 매칭되는 괄호 "(" 혹은 "[" 를 가진다. )를 제거하면 되는 것이다.

그리고 반복문의 마지막에서는 모든 괄호가 대칭이어서 스택의 괄호가 모두 제거되었거나, 문자열내에 괄호가 존재하지 않아 스택이 비어있는 경우에 yes를 출력하고, 반대로 스택에 괄호가 남아있다면 괄호가 대칭되지 않는 것이므로 no를 출력하면 된다.

[정답 코드]

#include <iostream>
#include <stack>
using namespace std;

int main() {
  while(1){
    string s;
    stack<char> stk;
    bool flag=0;
    getline(cin,s);
    if(s==".") break;
    for(int i=0;i<s.length();i++){
      if(s[i]=='('||s[i]=='[') stk.push(s[i]);
      if(s[i]==']'){ if(!stk.empty()&&stk.top()=='[') stk.pop(); else{ flag=1; break; } }
      if(s[i]==')'){ if(!stk.empty()&&stk.top()=='(') stk.pop(); else{ flag=1; break; } }
    }
    if(!flag&&stk.empty()) cout << "yes" << '\n';
    else cout << "no" << '\n';
  }
}

[결과]

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

[문제]

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

[알고리즘 분류]

• 수학

[해설]

문제에서 볼 수 있듯, 이번 문제는 N의 팩토리얼에서 0의 개수를 구하는 것이 목적이다.
N의 범위는 최소 0, 최대 500까지 주어지는데 이 때문에 직접 팩토리얼을 구해 0의 개수를 세려고 하면 숫자가 말도안되게 커져버려 일반적인 자료형으로는 담을 수도 없게 되어버린다.
따라서, 팩토리얼을 직접 구하는 것보다 일정한 규칙성을 찾는 것이 이번 문제의 포인트라고 할 수 있는데, 이 규칙성을 찾느라 좀 고생했던 것 같다.

이 규칙성을 찾기 위해서는 N에 대한 팩토리얼을 수행했을 때 0이 등장하는 수 N에 대한 규칙성을 알아야 한다.
예를 들어, 5!는 120인데 여기에서는 0이 한 번 등장한다. 그리고 문제에서 예시로 보여주는 10!은 3628800으로 0이 총 두 번 등장하게 된다. ( N이 가진 5의 배수의 수가 0의 개수라는 것을 알 수 있다. ex. 5는 5, 단 하나로 5의 배수가 1개, 10은 5와 10으로 5의 배수가 2개 )

여기에서 중요한 것은 5의 2,3,4...n승의 수들은 각각 5보다 5의 개수를 n-1개 만큼 더 가지고 있는 것과 마찬가지이기 때문에 N에 들어가는 5의 n승의 개수들도 같이 세어줘야 한다는 것이다.

결과적으로, 문제에서는 N의 범위를 최대 500까지로 제한하고 있기 때문에 500보다 작은 5^1 = 5, 5^2 = 25, 5^3 = 125에 대한 개수를 세어 모두를 더해주면 되는 것이다.

[정답 코드]

#include <stdio.h>

int main(){
  int N;
  scanf("%d",&N);
  printf("%d",N/5+N/25+N/125);
}

[결과]

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

[문제]

세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다.
예를 들어, 문서가 abababa이고, 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다. 세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다.
이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공배긍로 이루어져 있다.

[출력]

첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.

[알고리즘 분류]

• 문자열
• 브루트포스 알고리즘

[해설]

문서 검색 문제에서 요구하는 것은 두 번째로 주어진 문자열2가 첫 번째로 주어진 문자열1에 몇 번 들어가는지 '중복 없이' 세는 것인데, 이는 substr과 문자열 범위만 잘 지정하면 쉽게 풀 수 있는 문제였다.
중복 없이 문자가 얼마나 들어가는지 세야하는 것이기에 반복문을 통해 문자열1을 순회하면서 문자열1의 (i+문자열2의 길이) 범위가 문자열 2와 동일한지 검사하고, 동일하다면 결과값을 1 증가시킨뒤 반복문의 초기식 i에 (문자열2의 길이-1)을 더해 그 범위를 다음번에 건너뛰게 하는 식으로 문제를 해결할 수 있다.
(문자열2의 길이에서 -1을 하는 이유는 반복문의 증감식으로 인해 i가 1 증가하기 때문이다.)
또, 첫 번째로 입력된 문자열1의 길이가 문자열2의 길이보다 작음에도 비교연산을 수행하면 런타임 에러(out of range)가 발생하기에 조건문으로 이를 처리해주어야 한다.

[정답 코드]

#include <iostream>
using namespace std;

string d,w;
int r=0;

int main() {
  getline(cin,d);
  getline(cin,w);
  int wLen=w.length();
  if(d.length()<wLen) cout << 0;
  else {
    for(int i=0;i<=d.length()-wLen;i++) if(d.substr(i,wLen)==w) { 
      r++; 
      i+=(wLen-1); 
    }
    cout << r;
  }
}

[결과]