안경잡이개발자

728x90
반응형

  해외 사이트에서 재귀 문제나 다이나믹 프로그래밍 문제를 공부할 때 좋은 교육용 자료를 찾아서 공유한다.

 

  ▶ 어떠한 재귀 문제도 해결할 수 있는 5가지 단계: https://www.youtube.com/watch?v=ngCos392W4w 

 

  ▶ 예시 문제: 피보나치(Fibonacci) 수열

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

 

[1단계] What's the simplest possible input? (가장 간단한, 가능한 입력은 무엇인가?)

 

  가장 간단한 형태의 입력을 선택하면 된다. f(0) = 0, f(1) = 1로 볼 수 있다.

 

[2단계] Play around with examples and visualize! (다양한 예제를 그려보며 놀기!)

 

  규칙을 찾기 위해서 다양한 예제를 그려보며 노는 것이 중요하다.

 

[3단계] Relate hard cases to simpler cases (어려운 문제와 쉬운 문제를 연결 짓기)

 

  재귀 문제의 가장 큰 특징은, 하나의 어려운 문제를 해결하기 위해 쉬운 문제를 조합해야 한다는 것이다. 예를 들어 피보나치 수열은 f(x) = f(x - 1) + f(x - 2)가 성립한다. 다시 말해 하나의 어려운 문제 입장에서는 자기보다 쉬운 2개의 문제를 해결하면, 자기 자신을 해결할 수 있다는 것을 의미한다.

 

[4단계] Generalize the pattern (패턴을 일반화하기)

 

  f(x) = f(x - 1) + f(x - 2)가 정당하다는 것을 확인하고, f(x) = f(x - 1) + f(x - 2) 형태로 일반항을 정의한다. 이때 초기 항은 f(0) = 0, f(1) = 1이다.

 

[5단계] Write code by combining recursive patterns with the base case (코드로 옮기기)

 

  이후에 해당 점화식을 다음과 같이 코드로 옮기면 된다.

 

def fibo(x):
    if x == 0 or x == 1:
        return x
    else:
        return fibo(x - 1) + fibo(x - 2)

print(fibo(10))
728x90
반응형

728x90
반응형

문제 유형: 구현

문제 URL: http://codeforces.com/contest/399/problem/A


  이 문제는 구현의 끝판왕 문제인 게시판 페이징(Paging) 문제입니다. 전체 페이지의 개수를 N, 현재 페이지를 P, 현재 페이지를 기준으로 왼쪽과 오른쪽에 몇 개의 페이지까지 표시할 지를 K라고 합니다. 이 때 << 3 4 (5) 6 7 >>와 같은 방식으로 페이징 처리를 하면 됩니다.


  왼쪽으로 페이지가 더 남았을 때는 "<<"를 출력하고, 오른쪽으로 페이지가 더 남았을 때는 ">>"를 출력합니다. 실제 게시판을 구현할 때도 비슷한 방식의 페이징 처리 알고리즘 구현해 본 경험이 있다는 점에서 재미있게 풀 수 있었습니다.


※ 예시 입출력 ※


input

17 5 2

output

<< 3 4 (5) 6 7 >> 

※ 정답 소스코드 ※
(컴파일 환경: GNU G++11 5.1.0)
#include <iostream>
#include <stdio.h>

using namespace std;

int main(void) {
	int n, p, k;
	cin >> n >> p >> k;
	// 왼쪽으로 이동이 가능한 경우 
	if(p - k > 1) {
		cout << "<< ";
	}
	for(int i = ((p - k > 1)? p - k : 1); i < p; i++) {
		cout << i << ' ';
	}
	// 현재 페이지를 출력 
	cout << "(" << p << ") ";
	for(int i = p + 1; i <= ((p + k < n)? p + k : n); i++) {
		cout << i << ' ';
	}
	// 오른쪽으로 이동이 가능한 경우 
	if(p + k < n) {
		cout << ">>";
	}
	return 0;
}


728x90
반응형

728x90
반응형

문제 유형: 수학

문제 URL: http://codeforces.com/contest/393/problem/A


  이 문제는 특정한 문자열이 주어졌을 때 그 문자열의 문자들을 재정렬해서 "nineteen"이라는 문자열을 몇 개나 만들 수 있는지 물어보는 문제입니다. 예를 들어 문자열 "xiineteenppnnnewtnee"이 주어졌을 때 이를 "xnineteenppnineteenw"와 같이 재정렬한다면 "nineteen" 문자열이 두 번 나오게 되는 것입니다. 따라서 위 경우 최대 2개 만들 수 있으므로 정답은 2입니다.


  또한 "nineteen"이라는 문자열의 개수를 셀 때는 전체 문자열을 앞에서부터 한 자씩 읽어 확인하므로 문자를 읽다가 건너 뛸 수 없습니다. 또한 문자 n은 끝과 시작이 이어질 수 있습니다. 예를 들어 "nineteenineteen"과 같이 나열하면 n의 개수가 5개여도 "nineteen"을 2번 찾을 수 있습니다.


  이 문제는 단순히 n, i, e, t 문자의 개수를 세서 풀 수 있습니다. "nineteen"은 n 3개, i 1개, e 3개, t 1개로 이루어집니다. 따라서 만들 수 있는 "nineteen"의 최대 개수를 구하기 위해서는 각 문자를 몇 개씩 가지고 있느냐를 기준으로 개수를 찾을 수 있을 것입니다. 특히 n은 끝과 시작이 이어질 수 있기 때문에 사실상 n은 2개만 있어도 하나의 "nineteen"을 구성할 수 있다고 고려해야 합니다.


※ 정답 소스코드 ※


(컴파일 환경: GNU G++11 5.1.0)

#include <iostream>
#include <stdio.h>
#include <limits.h>

using namespace std;

int main(void) {
	int nC = 0;
	int iC = 0;
	int eC = 0;
	int tC = 0;
	string input;
	cin >> input;
	for(int i = 0; i < input.size(); i++) {
		if(input[i] == 'n') nC++;
		else if(input[i] == 'i') iC++;
		else if(input[i] == 'e') eC++;
		else if(input[i] == 't') tC++;
	}
	int res = INT_MAX;
	if(nC > 3) {
		// n은 끝과 시작이 이어질 수 있습니다. 
		res = min(res, (nC - 1) / 2);
	}
	else {
		res = min(res, nC / 3);
	}
	res = min(res, iC);
	res = min(res, tC);
	res = min(res, eC / 3);
	cout << res;
	return 0;
}


728x90
반응형

728x90
반응형

Facebook Hacker Cup 2018 Qualification Round

나동빈

 

  페이스북 해커컵(Facebook Hacker Cup)은 특이한 방법으로 진행됩니다. 프로그램을 만들 때의 논리력을 중요시하기 때문에 언어의 제약이 없습니다. 그래서 문제를 푼 뒤에 소스코드를 제출할 때는 페이스북에서 제공하는 입력 파일(Input)을 받아서, 그것을 프로그램에 넣고 나온 결과(Output)을 그대로 제출하면 됩니다. 소스코드도 별도로 제출하긴 하는데 부정행위 검사용에 불과한 것 같습니다.



  실제로 문제를 푼 뒤에 답안을 제출할 때는 6분의 시간을 줍니다. 입력 데이터에 대해 6분 안에 올바른 결과 값을 도출해서 제출하면 되는 방식입니다.



  출력 파일 및 소스코드를 제출하면 다음과 같이 제출이 이루어집니다. 결과는 대회가 끝나야 제대로 나오는 것으로 판단됩니다.



1. Tourist

 

문제 설명

(페이스북 해커컵의 문제는 영어로 제공됩니다. 제가 임의로 번역한 겁니다.)

 

- N개의 장소가 있고 장소의 이름은 문자열로 주어집니다.

- 1부터 N까지 인기가 많은 순서대로 주어집니다.

- 한 번 방문할 때 K개의 장소를 방문합니다.

- 구체적으로 어떤 장소를 방문할지 결정하기 위해서, 이미 몇 번 방문한 적이 있는지를 기준으로 N개의 장소를 오름차순 정렬합니다. 그리고 인기도가 많은 순으로 정렬하여 K개를 선택합니다.

- 즉 모든 장소에 대해서 방문한 횟수를 기준으로 먼저 선택하고, 방문한 횟수가 동일하다면 인기도가 높은 장소를 선택하면 됩니다.

- Alex는 이미 V-1번 방문한 적이 있습니다. 이제 V번째 방문을 하고자 합니다. AlexV번째 방문할 때 방문하게 될 K개의 장소를 출력하면 됩니다.

- T번의 테스트가 제공되고 매 테스트마다 N, K, V가 주어지고 N개의 장소명이 주어집니다.

- 1 <= T <= 80, 1 <= K <= N <= 50, 1 <= V 10^12


예제 입력

6

4 1 3

LikeSign

Arcade

SweetStop

SwagStore

4 4 100

FoxGazebo

MPK20Roof

WoodenSculpture

Biryani

4 3 1

LikeSign

Arcade

SweetStop

SwagStore

4 3 3

LikeSign

Arcade

SweetStop

SwagStore

4 3 10

LikeSign

Arcade

SweetStop

SwagStore

2 1 1000000000000

RainbowStairs

WallOfPhones

 

예제 출력

Case #1: SweetStop

Case #2: FoxGazebo MPK20Roof WoodenSculpture Biryani

Case #3: LikeSign Arcade SweetStop

Case #4: LikeSign SweetStop SwagStore

Case #5: LikeSign Arcade SwagStore

Case #6: WallOfPhones


문제 풀이

  문제의 조건을 보면 V가 최대 1,000,000,000,000까지 들어올 수 있습니다. 그래서 단순히 문제에서 요구하는 대로 매 번 정렬을 수행해서 최종적인 답을 도출하려고 하면 정해진 시간 안에 문제를 해결할 수 없을 겁니다. 그래서 최대 1,000,000,000,000 번을 실제로 다 방문하지 말고 어떠한 규칙을 발견할 수 있도록 애초에 문제에서 유도하고 있는 것입니다. 따라서 문제를 풀 때는 정확히 이러한 N, K, V의 범위. 즉 정의역에 대해서 가장 먼저 파악해야 합니다.

 

  만약에 장소의 개수가 5개라고 할 때, 차례대로 장소를 방문한다고 하면 i번째 장소를 방문하고자 할 때 인덱스는 어떻게 될까요?



  위와 같이 장소가 5개 있다고 해봅시다. 이 때 3번째 장소는 다음과 같이 인덱스 2에 해당합니다.



  그렇다면 9번째 장소는 어떻게 될까요? 다음과 같이 한 바퀴 돌아서 인덱스 3에 해당합니다.



  즉, i번째 장소의 인덱스를 구하려면 (i - 1) % N을 하면 됩니다. 이걸 왜 언급하는 걸까요? 그 이유는 이 문제는 슬라이딩 윈도우와 흡사한 알고리즘이 사용되기 때문입니다. 전체 배열의 크기가 N일 때 한 번 방문할 때 K개만큼 방문하면서 계속해서 원을 그리며 이동하면 됩니다.

 

  다만 방문 횟수가 동일한 경우에는 더 인기가 많은 장소부터 출력해야 하므로 슬라이딩 윈도우를 수행하며, 출력하기 전에 인덱스를 기준으로 장소의 이름에 대해 오름차순 정렬을 수행해주시면 됩니다.

 

  결과적으로 이미 V - 1번 방문을 했다고 가정하므로 V번 째 방문을 할 때는 (K * (V - 1)) % N + 1번째 장소부터 (K * (V - 1)) % N + K번째 장소까지 방문하여 출력하면 정답 처리를 받을 수 있습니다. (출력하기 직전에 인덱스를 기준으로 정렬을 해주시면 됩니다.)


#include <iostream>

#include <fstream>

#include <algorithm>

#include <vector>

 

using namespace std;

 

long long int n, k, v;

string a[50];

 

class Node {

  public:

    int rate;

    string name;

    Node(int rate, string name) {

      this->rate = rate;

      this->name = name;

    }

    bool operator <(Node other) {

      return this->rate < other.rate;

    }

};

 

int getIndex(int number) {

  return (number - 1) % n;

}

 

int main(void) {

  ifstream inFile("Tourist.txt");

  ofstream outFile("Tourist Answer.txt");

  int T;

  inFile >> T;

  for(int testCase = 1; testCase <= T; testCase++) {

    vector<Node> nodes;

    inFile >> n >> k >> v;

    for(int i = 0; i < n; i++) {

      inFile >> a[i];

    }

    for(int i = (k * (v - 1) % n + 1); i <= (k * (v - 1) % n + k); i++) {

      int index = getIndex(i);

      nodes.push_back(Node(index, a[index]));

    }

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

    outFile << "Case #" << testCase << ": ";

    for(int i = 0; i < nodes.size(); i++) {

      outFile << nodes[i].name << ' ';

    }

    outFile << '\n';

  }

  return 0;

}


2. Interception

 

문제 설명

(페이스북 해커컵의 문제는 영어로 제공됩니다. 제가 임의로 번역한 겁니다.)

 

-

- 위와 같은 형태로 표현되는 다항식이 있습니다.

- 이러한 다항식을 실제로 계산할 때는 연산자 우선순위가 덧셈(+), 곱셈(*), 지수 승(^) 순서입니다.

- 예를 들어 는 로 계산됩니다.

- 음수(-) 부호는 우선순위가 제일 높습니다.

- 0^01입니다.

- T번의 다항식(Polynomial)이 주어집니다.

- 다항식마다 최고 차수 N이 주어지고, 그 이후에 차수 N부터 0까지 차례대로 계수가 주어집니다.

- 계산하기 위한 다항식을 f(x)라고 했을 때 f(x) = 0이 되는 X의 개수를 출력하고, 각 라인에서는 각 X의 값을 오름차순으로 출력합니다.


예제 입력

2

1

1

1

4

9

0

-6

2

-2

 

예제 출력

Case #1: 1

0.0

Case #2: 0

 

부가 설명

주어진 예제 입력을 설명해드리자면 다음과 같습니다.

 

2: 테스트 케이스가 2

1: 첫 번째 테스트 케이스는 최고 차수가 1

1: 차수 1의 계수

1: 차수 0의 계수

4: 두 번째 테스트 케이스는 최고 차수가 4

9: 차수 4의 계수

0: 차수 3의 계수

-6: 차수 2의 계수

2: 차수 1의 계수

-2: 차수 0의 계수

 

첫 번째 테스트 케이스에서 들어온 입력은 다음과 같은 식입니다.



이제 이걸 f(x)로 표현하면 다음과 같습니다.



  그러므로 X0일 때 f(x)0이 될 수 있는 것입니다.


문제 풀이

  일단 문제에서 요구하는 연산자의 우선순위를 따랐을 때 모든 다항식은 지수함수으로 표현된다는 것을 이해하셔야 합니다. 왜냐하면 지수 연산(^)의 우선순위가 제일 낮기 때문입니다. 어떠한 입력이 들어와도 결과적으로 f(x)는 지수함수 형태에요. 이 때 일반적인 지수함수는 절대로 f(x) = 0이 될 수 없다는 것을 생각해보세요. 지수함수는 다음과 같이 생겼습니다.



다만, 문제의 형태를 보면 항상 최종적으로는 X와 어떠한 식을 곱하도록 되어있습니다. 예를 들어 다음의 식을 고려해보세요 이 식은 다음과 같이 바뀝니다.



  즉 어떠한 다항식이 들어왔을 때 무조건 (어떠한 숫자 * X)의 지수 승 형태로 표현되는 것을 알 수 있습니다. 이게 힌트인데요. 일반적인 지수함수는 어떤 일이 있어도 그 결과 f(x) = 0이 될 수 없기 때문에 (어떠한 숫자 * X)를 이용하셔야 합니다. X = 0인 경우에는 f(x) = 0이 될 가능성이 존재하기 때문입니다. 다시 말해서 어떠한 입력 값이 들어오더라도 근이 한 개 존재하는 경우(X = 0), 근이 아예 존재하지 않는 경우 두 가지 경우 밖에 존재하지 않는다는 것입니다.

 

  이 때 실제로 특정한 f(x)에 대해 X = 0을 넣는 방식으로 답을 계산할 수도 있을 것입니다. 다만 저는 조금 더 문제를 분석해보았어요. 그랬더니 재미있는 규칙을 찾았습니다. 바로 항의 개수가 홀수일 때는 근이 없고, 항의 개수가 짝수일 때는 근이 있다는 겁니다. 종이로 그려보니까 다음과 같았어요.



  따라서 테스트 케이스마다 N을 입력 받아서 N이 홀수일 때와 짝수일 때를 구분해서 정답을 출력하면 문제를 쉽게 해결할 수 있습니다.


#include <iostream>

#include <fstream>

 

using namespace std;

 

int main(void) {

  ifstream inFile("Interception.txt");

  ofstream outFile("Interception Answer.txt");

  int T;

  inFile >> T;

  for(int testCase = 1; testCase <= T; testCase++) {

    int n;

    inFile >> n;

    for(int i = 0; i <= n; i++) {

      int x;

      inFile >> x;

    }

    outFile << "Case #" << testCase << ": ";

    if(n % 2 == 1) {

      outFile << 1 << '\n';

      outFile << "0.0" << '\n';

    else {

      outFile << 0 << '\n';

    }

  }

  return 0;

}


3. Ethan Searches for a String

 

문제 설명

(페이스북 해커컵의 문제는 영어로 제공됩니다. 제가 임의로 번역한 겁니다.)

 

- 문자열 매칭 알고리즘이란 문자열 A가 문자열 B 안에 포함이 되어있는지를 판단하는 알고리즘입니다.

- 다음의 Ethan이 작성한 문자열 매칭 알고리즘이 있습니다. 이 알고리즘은 잘못된 알고리즘입니다.

 

(1) ij1로 설정합니다.

(2) i > |A|일 때, TRUE를 반환합니다.

(3) j > |B|일 때, FALSE를 반환합니다.

(4) Ai = Bj일 때, ij1 증가시키고 (2) 단계로 이동합니다.

(5) i = 1일 때, j1 증가시키고 (2) 단계로 이동합니다.

(6) i1로 설정하고 (2) 단계로 이동합니다.

 

- A라는 문자열이 주어졌을 때, 우리는 문자열 AB라는 문자열 안에 포함이 되는데도 불구하고 Ethan의 알고리즘이 FALSE를 뱉는 문자열 B’를 찾아내고자 합니다.

- 문자열 B를 찾을 수 없을 때는 'Impossible'을 출력합니다.

- 테스트 케이스 T100개까지 주어질 수 있습니다.

- 1 <= A의 길이 <= 2,000

- 1 <= B의 길이 <= 10,000

 

예제 입력

4

ABACUS

FACEBOOK

XYZXZYX

FBFBF

 

예제 출력

Case #1: ASUCABABACUSA

Case #2: Impossible

Case #3: XZYXYZXYZXZYXYZXYZYX

Case #4: Impossible

 

문제 풀이

 

  먼저 문제를 접하기 전에 KMP 알고리즘에 대한 제 강의 노트를 한 번 보시고 오시기 바랍니다.

 

  KMP 알고리즘: https://blog.naver.com/ndb796/221240660061

 

  일단 Ethan의 알고리즘을 직접 C++ 소스코드로 구현해보겠습니다.

 

#include <iostream>

 

using namespace std;

 

bool contains(string a, string b) {

  int i = 1, j = 1;

  while(1) {

    if(i > a.length()) return true;

    if(j > b.length()) return false;

    if(a[i - 1] == b[j - 1]) {

      i++;

      j++;

      continue;

    }

    if(i == 1) {

      j++;

      continue;

    }

    i = 1;

  }

}

 

int main(void) {

  string a = "ABACUS";

  string b = "ASUCABABACUSA";

  cout << contains(a, b) << '\n';

  int result = b.find(a);

  cout << result;

  return 0;

}


  위 소스코드를 보시면 “ABACUS”는 분명히 “ASUCABABACUSA”에 포함이 되는데도 불구하고 Ethan의 알고리즘은 FALSE(0)라는 값을 반환하는 것을 알 수 있습니다. find() 함수는 C++에서 기본적으로 제공하는 문자열 매칭 함수입니다. find() 함수는 "ABACUS"가 포함되는 시작 인덱스인 6이라는 값을 내뱉는 것을 알 수 있습니다. 그렇다면 이 문제를 풀기 위해서는 어떻게 해야 할까요? Ethan의 알고리즘을 직접 손으로 차근차근 해보면 쉽게 이해하실 수 있습니다. 문자열이 일치하는지 하나씩 검사하는 알고리즘인데요, 접미사와 동일한 접두사가 존재하는 경우를 캐치하지 못한답니다.

 

  따라서 하나씩 검사하다가 불일치 할 때 위치에서의 접미사와 동일한 접두사가 존재하는지 확인해야합니다. Ethan의 소스코드는 그러한 경우를 캐치하지 못하고 넘어가는 불완전한 소스코드니까요.

 

  예를 들어 FBFBFKEthan의 소스코드의 결함을 보여주는 예시입니다. FBFBFBFK와 비교했을 때 하나씩 검사하다가 FBFBFKFBFBFBFK가 불일치가 발생합니다. 이 때 접미사와 접두사는 FBFB로 동일하게 구성됩니다.

 

A: FBFBFK

B: FBFBFBFK

 

  이러한 경우 실제로는 문자열이 포함됨에도 불구하고 Ethan의 함수는 이를 감지할 수 없습니다. 따라서 Ethan 함수의 결함을 지적하기 위해서는 하나씩 검사하다가 불일치 할 때 위치에서의 접미사와 동일한 접두사가 존재하는 문자열 B를 만들면 됩니다.

 

  다만 불일치하기 직전까지는 일단 AB가 일치했다는 것을 이해하셔야 합니다.

 

A: FBFBFK

B: FBFBFBFK

 

  위 경우를 보시면 일단 FBFBF까지는 일치했습니다. 그 이후에 KB가 서로 다른 겁니다. 따라서 불일치 할 때 위치에서의 접두사와 접미사가 일치하려면, 불일치하기 직전까지 검사했던 일련의 문자열들도 당연히 접두사와 같아야 합니다. 예를 들어 FBFF 두 개가 존재할 겁니다.

 

  다시 말해서 하나씩 검사하다가 불일치 할 때 위치에서의 접미사와 동일한 접두사가 존재하는 문자열 B’를 만들기 위해서는 문자열 A에서 이미 접두사와 접미사가 일치하는 문자열 쌍이 존재해야만 합니다. 예를 들어 FACEBOOK은 접두사와 접미사가 일치하는 문자열 쌍이 하나도 존재하지 않습니다. 그렇기 때문에 Ethan의 함수에서의 결함을 찾을 수 없는 예시가 되는 겁니다.

 

  이제 문자열 ‘FBFBF’를 고려해봅시다. 이것도 Ethan의 함수의 결함을 찾을 수 없습니다.

 

A: FBFBF

B: FBFB?

 

  위 경우를 보시면 물음표 위치에 F를 넣는다고 하면 문자열 일치가 발생해버리고, K와 같이 다른 문자를 넣는다고 하면 불일치 할 때 위치에서의 접미사와 동일한 접두사가 존재할 수 없습니다. 모순이 발생하는 거죠. 분명히 접두사와 접미사가 일치하는 경우는 'F', 'FB', 'FBF' 세 개가 존재함에도 불구하고 이러한 문제가 발생했습니다. 여기에서 하나의 사실을 유추할 수 있습니다. 바로 접두사와 접미사가 일치하는 연속된 경우의 뒤에 하나 이상의 여분 문자가 필요하다는 것입니다.

 

  예를 들어 FBFBK'F', 'FB'라는 두 개의 접미사와 동일한 접두사가 존재할 수 있습니다. 이제 'F'‘FB'는 연속되어 있으므로 ’FB'만 고려하겠습니다. 이 때 잘 살펴보시면 'FB'의 뒤에 K라는 하나 이상의 여분 문자가 존재합니다. 그래서 이 KF로 바꾸어주고, 뒤에 BK를 붙여줌으로써 다음과 같은 문자열을 만들 수 있어요.

 

B: FBFBFBK


  이렇게 만들게 되면 Ethan의 함수에 존재하는 결함을 밝힐 수 있게 되는 것입니다. 따라서 문제를 해결하기 위한 방법은 다음과 같습니다.

 

< Ethan의 함수에 존재하는 결함을 밝히는 방법 >

 

1. 접두사 및 접미사 쌍 테이블을 만들기

2. 접두사와 접미사가 일치하는 연속된 경우의 뒤에 하나 이상의 여분 문자가 존재하는지 확인하기

 

  예를 들어 ‘XYZXZYX’의 접두사 및 접미사 쌍 테이블은 다음과 같습니다.



  보면 ‘XYZXZYX’는 인덱스 3의 값이 1이라서 접두사와 접미사가 일치하는 부분 문자열이 존재하는 겁니다. 이 때 인덱스 4가 여분 문자로 존재합니다. 따라서 다음과 같은 문자열을 만들 수 있어요.

 

XYZXYZXZYX

 

  다시 말해 XYZX에서 그 뒤로 YZXZYX를 넣어준 겁니다. 이것은 접두사와 접미사가 일치할 수 있는 부분이 인덱스 3‘X’이므로 그 뒤로 접미사를 제외한 YZXZYX를 넣어준 것이라고 할 수 있습니다. 이런식으로 만들게 되면 ‘XYZXYZXZYX' 안에 'XYZXZYX’가 포함되어 있음에도 불구하고 Ethan의 함수는 이를 찾아내지 못합니다. 이제 이 내용을 소스코드로 옮기면 됩니다.


#include <iostream>

#include <fstream>

#include <vector>

 

using namespace std;

 

vector<int> makeTable(string pattern) {

  int patternSize = pattern.size();

  vector<int> table(patternSize, 0);

  int j = 0;

  for(int i = 1; i < patternSize; i++) {

    while(j > 0 && pattern[i] != pattern[j]) {

      j = table[j - 1];

    }

    if(pattern[i] == pattern[j]) {

      table[i] = ++j;

    }

  }

  return table;

}

 

int main(void) {

  ifstream inFile("Ethan.txt");

  ofstream outFile("Ethan Answer.txt");

  int T;

  inFile >> T;

  for(int testCase = 1; testCase <= T; testCase++) {

    outFile << "Case #" << testCase << ": ";

    string pattern;

    inFile >> pattern;

    vector<int> table = makeTable(pattern);

    bool find = false;

    for(int i = 1; i < table.size(); i++) {

      // 접두사와 접미사가 일치하는 '연속된 경우'의 뒤에 '하나 이상의 여분 문자가 존재'하는지 확인

      if(table[i] <= table[i - 1] && table[i - 1] != 0) {

        // 찾았을 경우 문자열 생성

        find = true;

        // 앞 부분 출력

        for(int j = 0; j < i; j++) {

          outFile << pattern[j];

        }

        // 뒷 부분 출력

        for(int j = table[i - 1]; j < pattern.size(); j++) {

          outFile << pattern[j];

        }

        outFile << '\n';

        break;

      }

    }

    if(!find) {

      outFile << "Impossible\n";

    }

  }

  return 0;

}

728x90
반응형

728x90
반응형

본 포스팅에는 오류가 있습니다. 시간날 때 수정하겠습니다.


  일반적으로 우리가 알고 있는 대수학의 표기법인 중위 표기법을 컴퓨터에게 계산하도록 만들고 싶으면 후위 표기법으로 변환한 뒤에 계산하는 과정이 필요합니다. 실제로 계산기 등이 내부적으로 수행하고 있는 방법이기도 합니다. 재미있는 점은 중위 표기법을 후위 표기법으로 바꿀 때는 오직 스택(Stack)만 있으면 됩니다. 스택을 적절히 활용하면 처리할 수 있다는 점이 매우 큰 특징입니다.


  컴퓨터가 수식을 계산하는 방법은 다음의 두 절차를 따르면 됩니다.


 ① 중위 표기법을 후위 표기법으로 변환하기


  중위 표기법을 후위 표기법으로 바꿀 때는 다음의 절차를 따르면 됩니다.


  1) 피연산자가 들어오면 바로 출력합니다.

  2) 연산자가 들어오면 자기보다 우선순위가 높거나 같은 것들을 빼고 자신을 스택에 담습니다.

  3) 여는 괄호 '('를 만나면 무조건 스택에 담습니다.

  4) 닫는 괄호 ')'를 만나면 '('를 만날 때까지 스택에서 출력합니다.


  한 번 중위 표기식 ( a + b - c ) * d * e을 위 공식에 따라서 후위 표기법으로 변환해봅시다.


  변환 결과: a b + c - d e * *


  숫자를 이용해 표현해봅시다. ( 5 + 6 - 7 ) * 1 * 5 이 경우도 다음과 같이 변환할 수 있습니다.


  변환 결과: 5 6 + 7 - 1 5 * *


  이러한 과정을 의사코드로 표현하면 다음과 같습니다.


------------------------------------------------------------------------------------------------


void translation(exp) {

while((token = getChar(exp)) != NULL) {

if(token == 피연산자) print(token);

else if(token == ')') {

while(stack[top] != '(') print(pop());

pop();

}

else {

while(getPriority(stack[top]) >= token) print(pop());

push(token);

}

}

while((token = getChar(exp)) != NULL) print(token);

}


------------------------------------------------------------------------------------------------

 ② 후위 표기법을 계산하기


  후위 표기법을 계산할 때는 다음의 절차를 따르면 됩니다.


  1) 피연산자를 만나면 스택에 담습니다.

  2) 연산자를 만나면 스택에서 두 개의 연산자를 꺼내서 연산한 뒤에 그 결과를 스택에 담습니다.

  3) 연산을 마치고 스택에 남아있는 하나의 피연산자가 연산 수행 결과입니다.


  후위 표기식: 5 6 + 7 - 1 5 * *

  계산 결과: 20


  이러한 과정을 의사코드로 표현하면 다음과 같습니다.


------------------------------------------------------------------------------------------------


void calculate(exp) {

int x, y, z;

while((token = getChar(exp)) != NULL) {

if(token == 피연산자) push(token);

else if(token == 연산자) {

x = pop();

y = pop();

z = y 연산자 x;

push(z); 

}

}

print(pop());

}


------------------------------------------------------------------------------------------------


728x90
반응형