숫자 야구 게임은 소프트웨어 엔지니어링에 대해 배우다 보면 한 번씩은 보게 되고, 또 만들게 되는 간단한 숫자 게임입니다. 문제를 내는 알고리듬은 반복문이나 조건문, 입출력 등의 기본 기술에 대한 평가 방식으로도 이용됩니다. 문제를 푸는 알고리듬은 내는 알고리듬보다 조금 어려운 정도입니다. 굳이 하고 싶다면 여러 가지 기술을 사용해서 조금 더 똑똑한 알고리즘을 만들 수도 있습니다.
이 글은 숫자 야구 게임을 주제로 하는 글의 시작으로 여기선 내는 쪽을 다루려고 합니다. 그 후에 푸는 알고리듬을 다룬 뒤, 마지막으로 프로세스 간 통신 기술 인 인터 커뮤니케이션을 다뤄볼까 합니다.
그럼 숫자 야구 게임의 개념부터 설명하죠. 아래 그림을 참조해 주세요. 설명을 도와줄 초록이와 파랑이입니다.
숫자 야구 게임
숫자 야구 게임은 2명이 하는 게임입니다. 편하게 문제를 내는 쪽은 초록이, 푸는 쪽을 파랑이입니다. 초록이는 먼저 숫자 3개 혹은 그 이상을 선택해서 정답을 만듭니다. 숫자의 범위는 보통 (0 - 9) 혹은 (1 - 9)를 선택하지만, 난이도를 높이고 싶으면 숫자의 범위를 넓히거나, 개수를 늘려 줍니다. 일반적으로 중복 숫자는 없게 하지만 중복을 허용하는 변화도 있을 수 있겠네요.
파랑이는 예측한 숫자 조합을 초록이에게 제시합니다. 초록이는 파랑이가 제시한 숫자와 자신이 선택한 정답의 차이를 보고 스크라이크와 볼의 개수를 계산해 알려 줍니다. 계산 방법은 아래와 같습니다.
- 스트라이크 : 숫자와 위치가 일치
- 볼 : 숫자는 일치하지만 위치가 불일치
- 아웃 : 모든 숫자가 불일치
파랑이는 초록이의 계산 결과를 참조해서 초록이가 선택한 정답을 찾기 위해 다음 숫자 조합을 제시합니다. 이과정을 반복해서 파랑이가 초록이의 정답을 맞히면 파랑이가 이기게 됩니다. 초록이가 이기는 조건은 설정마다 다르지만 보통 초록이의 제시 기회를 제한하는 방식을 이용합니다. 제시 기회는 9번으로 많이 하며, 난이도에 따라 조정 가능합니다. 혹은 3 아웃제를 하기도 합니다만, 3 아웃으로 게임이 끝나긴 매우 어렵습니다. 3 아웃제는 사실 게임의 승패를 위한 규정이라기보다, 아웃으로 후보를 소거하는 방식을 제한하는데 가깝습니다.
일단 실제 소프트웨어 개발 전에 변수들을 선정해야겠죠. 난이도는 숫자의 개수로 합니다. 파랑이는 3개 혹은 4개의 숫자를 선택합니다. 혹시 모르니 더 큰 숫자에 대해서도 대응하게 합니다. 숫자의 범위는 0-9이며, 중복은 허용하지 않습니다. 답안 추측은 9회의 제한을 주고 3 아웃제도 시행합니다.
초록이의 구현
위에도 적었지만, 이 글에서는 초록이의 알고리듬 (문제를 내는 알고리듬)을 만들려고 합니다. 그럼 초록이가 해줘야 하는 일은 어떤 것들이 있을까요? 정리해 보면 아래와 같습니다.
- 정답을 만든다.
- 파랑이에게 추측 값을 받는다.
- 파랑이의 추측과 정답을 비교한다.
그럼 첫 번째 정답을 만드는 함수부터 만들어 보겠습니다. 가장 쉽게 만드는 건 이중 반복문을 이용하는 것입니다. 아래 예제가 숫자 야구 게임을 만들어 달라고 하면 10명 중 8,9 분이 만들어 오는 예제입니다.
// 정답 만들기.
void makeAnswer(vector<int> &answer, int dL){
//정답의 크기(dL) 지정.
answer.resize(dL);
// 정답을 만들기 위한 난수
srand(time(nullptr));
// 정답을 만듦.
for(int i = 0 ; dL > i ; i++){
// 정답 후보
int cand;
// 중복 여부
bool flag;
do{
cand = rand() % 10;
flag = false;
// 중복 검사.
for(int j = 0 ; i > j ; j++){
if(cand == answer[j]){
flag = true;
}
}
}while(flag);
answer[i] = cand;
}
}가장 쉬운 숫자야구 게임은 3개의 숫자를 이용하지만, 그 이상도 처리하기로 했으니 dL로 개수를 조작합니다. 만들어진 정답은 호출한 함수에 전달되어야 하는 call by reference로 전달받습니다. call by reference에 대한 정보가 필요하시면 아래 링크의 이전 글을 확인해 주세요.
2021.03.26 - [Program Language and Algorithm] - Call by Value and Call By Reference
Call by Value and Call By Reference
메모리 직접 접근이 가능한 소프트웨어 언어의 함수 호출 방법은 두 가지입니다. 하나는 call by value이고, 하나는 call by reference입니다. 자세한 개념은 전공서적이나 위키피디아를 통해서 습득하
sbinroom.tistory.com
정답은 당연히 실행 때마다 달라져야 하니, 난수를 이용합니다. c와 c++에서 난수를 이용하는 방법은 처음엔 srand(time(nullptr)) 로 난수 생성을 시작한 뒤, rand()로 integer 범위의 난수를 받아서 나머지 연산을 활용해 원하는 범위로 제한하여 이용합니다. 이 구조는 랜덤 시드로 시간 정보를 이용해서 난수를 만드는 방법입니다. 세부 내용이 궁금하시면, 난수 발생기에 대해 공부해 보세요. (저도 실무에 필요한 적은 지식만 가지고 있는 분야라서 글로 쓰긴 어렵네요.)
어쨌든 위 함수는 난수로 숫자를 만들고 10으로 나눈 나머지를 얻어서 0-9 사이의 숫자를 만들어 줍니다. 중복을 허용하지 않기로 했으니, 숫자가 중복되는지 확인해 주고, 중복되었다면 난수를 다시 생성합니다. 이 과정을 dL 만큼 반복해서 정답을 만들죠.
이 예제는 가장 일반적인 방법이지만, 저는 좋아하지 않습니다. 이유는 최대 구동 시간을 보장 못 합니다. 왜냐하면, 중복 시 재계산 알고리듬이 무한하게 반복될 수 있습니다. 물론 0-9 사이의 숫자 3개를 중복 없이 뽑는다고 했을 때, 중복 연산이 발생할 확률은 2회 차에서 10%, 3회 차에서 20%이니, 무한하게 구동될 가능성은 낮습니다. 하지만, 예전 글에서도 기재했듯 조엘 스폴스키의 책을 보면서 제가 크게 익힌 한 가지는 "소프트웨어 엔지니어는 소프트웨어의 구동 시간을 명확히 산출할 수 있게 만들어야 한다"였습니다.
상기 이유로 저는 위 예제 보다 아래 예제를 더 좋아합니다.
// 정답 만들기.
void makeAnswer(vector<int> &answer, int dL){
//정답의 크기(dL) 지정.
answer.resize(dL);
// 정답이 될수 있는 후보들(0-9)을 저장하기 위한 벡터
vector<int> cand(10, 0);
for(int i = 1 ; 10 > i ; i++){
cand[i] = i;
}
// 정답을 만들기 위한 난수
srand(time(nullptr));
// 정답을 만듦.
for(int i = 0 ; dL > i ; i++){
int idx = rand() % cand.size();
answer[i] = cand[idx];
cand.erase(cand.begin() + idx);
}
// 후보군 삭제.
cand.clear();
}이 예제에서는 함수 구동 시 후보군을 벡터로 저장합니다. 그 후, 난수를 후보군의 개수로 나눈 나머지를 얻어서 idx 값으로 이용합니다. 정답의 요소가 되는 값은 후보군 중에서 idx 번째 값이 되는 거죠. 선택된 후보군은 벡터에서 삭제함으로써 중복되지 않도록 합니다.
위 예제는 처음 예제 보다 분명 느릴 것입니다. vector를 만드는 것은 리소스가 많이 드는 작업이 아니지만, 중간에 원소를 삭제하는 건 많은 리소스를 요구합니다. 그래도 이 함수는 항상 같은 리소스를 소모합니다. 약간 강박증세 이긴 합니다만, 어쨌든 전 이쪽을 선호합니다.
그럼 두 번째 함수로 입력을 받는 함수입니다. 기능은 간단합니다. 파랑이에게 dL만큼의 추측 값을 받고, 중복된 추측 값이 있는지 확인합니다. 예제는 아래와 같습니다.
// 사용자 입력 받기.
// in : 입력 받은 데이터 반환 (call by reference)
// dL : 게임의 난이도.
int getInput(vector<int> &in, int dL){
in.resize(dL);
//설명문.
string info;
info += "Enter the ";
info += (static_cast<char>(dL) + '0');
info += " numbers ( ";
for(int i = 0 ; dL > i ; i++){
info += "0 ";
}
info += "is give up)";
// 설명문 제작 완료.
// 모든 입력이 0이면 강제 종료.
int sum = 0;
cout << info << endl;
for(int i = 0 ; dL > i ; i++){
cin >> in[i];
sum += in[i];
}
vector<int> sortedIn = in;
sort(sortedIn.begin(), sortedIn.end());
// unique 함수의 결과가 끝이 아닌 조건 = 중복 숫자 입력됨.
while(sortedIn.end() != unique(sortedIn.begin(), sortedIn.end())){
// 강제 종료 조건으로 인해 강제 종료.
if(0 == sum){
return 1;
}
// 중복 되었음을 밝히고, 새로운 입력을 받음.
cout << "Duplicated input" << endl;
cout << info << endl;
sum = 0;
for(int i = 0 ; dL > i ; i++){
cin >> in[i];
sum += in[i];
}
sortedIn = in;
sort(sortedIn.begin(), sortedIn.end());
}
return 0;
}이 함수는 파랑이에게서 dL 만큼의 숫자를 입력받아서, 반환합니다. 단 파랑이가 그만하고 싶은 경우 추측 값으로 0만 전달해서 의사를 표현하도록 합니다.
숫자 야구 게임은 초록이와 파랑이가 함께하는 interaction 게임입니다. 대화가 중요하니, 당연히 의사도 명확히 표현해 줘야 합니다. 먼저 파랑이에게 해줄 메시지( info )를 만들어 줍니다. 내용은 "dL 만큼의 추측 값을 달라, dL 만큼 0을 주면 포기한 것으로 간주하겠다."입니다. 함수가 호출될 때마다 출력문을 만들어 주는 것은 비효율이지만, 그렇다고 전역으로 만들거나 출력문을 전달받으면, 가독성도 낮아지고, 함수의 기능성도 저하됩니다.
파랑이의 추측 값을 받으면서, 각 추측 값의 합산 값(sum)을 갱신합니다. 파랑이가 포기를 원하면(0만 연속 입력) 종료해야 하는데, 이를 확인할 가장 쉬운 방법입니다.
입력을 받은 뒤에는 중복된 값이 있는지 확인합니다. 먼저 sort를 이용해 파랑이의 추측 값들을 정렬한 벡터를 만들고, unique함수로 중복 여부를 판정합니다. unique함수는 지정된 템플릿 영역에서 중복된 값이 연속되면, 하나의 값만 남기고, 템플릿의 뒤쪽으로 이동시킵니다. 반환 값은 중복된 값을 없앤 위치의 iterator를 반환합니다. 글로는 설명이 힘드네요. 관련 예제를 찾아보시는 게 좋을 것 같지만, 간단히 설명드리면, 1, 2, 2, 4, 2, 3과 같은 벡터를 unique함수에 begin()과 end()로 넣어주면, 1, 2, 4, 2, 3, 2와 같은 벡터로 변환하고, 마지막 2의 위치에 해당하는 iterator( end() -1에 해당)를 반환합니다. unique 함수는 보통 sort함수와 함께 사용합니다. 위 벡터를 sort함수에 넣으면 1, 2, 2, 2, 3, 4 가 되고, 이 결과를 unique함수에 넣으면, 1, 2, 3, 4, 2, 2로 벡터가 변하고, end()-2에 해당하는 iterator를 반환합니다. 여기에 erase함수를 사용하면 중복된 값 없이 정렬된 벡터를 얻게 됩니다. 아래 예제를 참고하세요. 주석은 해당 줄이 실행된 뒤 test의 원소들입니다.
vector<int> test{1, 2, 2, 4, 3, 2}; // 1, 2, 2, 4, 3, 2
erase(unique(test.begin(), test.end()), test.end()); // 1, 2, 4, 3, 2
sort(test.begin(), test.end()); // 1, 2, 2, 3, 4
erase(unique(test.begin(), test.end()), test.end()); // 1, 2, 3, 4sort와 unique 함수를 이용해서 중복 여부를 확인하고, 중복된 경우 sum이 0이면 파랑이가 포기한 상태이니, 반환 값 1로 함수를 종료합니다. 아니면, 중복 임을 밝히고, 재입력을 받습니다.
다음 함수는 정답 검사 함수입니다. 검사 결과를 전달할 jud 벡터와, 입력과 정답이 담긴 in과 ans 벡터, dL 등이 전달됩니다. 정답 검사는 간단히 2중 반복문으로 구동합니다. 사실 함수 자체가 단순해서 딱히 설명할 부분이 없는 함수입니다.
// 정답 검사
// jud : 결과
// in : 입력
// ans : 정답
// dL : 난이도
bool judge(vector<int> &jud, vector<int> &in, vector<int> &ans, int dL){
bool res = false;
// strike
jud[0] = 0;
// ball
jud[1] = 0;
// 단순 비교를 통한 결과 계산.
for(int i = 0 ; dL > i ; i++){
for(int j = 0 ; dL > j ; j++){
if(ans[i] == in[j]){
res = true;
if(i == j){
jud[0]++;
}else{
jud[1]++;
}
}
}
}
// res 가 false 면 아웃.
return res;
}마지막으로 전체 구동을 위한 main함수입니다. 위의 함수들을 상황에 맞춰서 구동합니다.
int main(int argc, char ** argv){
cout << "Enter the defficulty level (3 or 4) : ";
// 난이도
int dL;
cin >> dL;
// 3아웃 제도.
int oC = 0;
// 정답
vector<int> ans;
// 사용사 입력
vector<int> in(dL, 0);
// 결과 : 0 = 스트라이크 1 = 볼
vector<int> jud(2);
// 정답 만들기
makeAnswer(ans, dL);
// 9번의 기회 제공
for(int t = 1 ; 10 > t ; t++){
cout << "Round " << t << "/9 : ";
if(1 == getInput(in, dL)){
break;
}
if(judge(jud, in, ans, dL)){
cout << jud[0] << " Strike " << jud[1] << " Ball" << endl;
}else{
cout << "Out" << endl;
oC++;
// 아웃 카운트 확인.
if(3 == oC){
cout << "Three Out!" << endl;
break;
}
}
if(dL == jud[0]){
cout << "You Win !! Congratulation" << endl;
return 0;
}
}
cout << "You Lost ..." << endl;
return 0;
}가장 먼저 난이도를 입력받습니다. 3이나 4를 입력해 달라고 요청하지만 더 늘려도 문제는 없습니다. 3 아웃제가 적용됨으로, 아웃을 카운트 하기 위한 변수(oC)를 만들고, 정답과 파랑이의 추측 값, 결과 판결을 저장하기 위한 벡터인 ans, in, jud를 만들어 줍니다. 그 후 정답을 만드는 함수를 구동시켜서 ans를 업데이트합니다.
for문을 이용해 9번의 기회를 제공합니다. 각 기회에서는 먼저 파랑이의 입력을 받아 옵니다. 만약 파랑이가 포기하면 for문을 종료해서 프로그램을 종료합니다. 그 후, 결과 판정을 받아서, 결과에 따라 승리를 축하하거나, 결과를 파랑이에게 알려줍니다.
합친 코드는 아래입니다.
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <ctime>
using namespace std;
// 정답 만들기.
void makeAnswer(vector<int> &answer, int dL){
//정답의 크기(dL) 지정.
answer.resize(dL);
// 정답이 될수 있는 후보들(0-9)을 저장하기 위한 벡터
vector<int> cand(10, 0);
for(int i = 1 ; 10 > i ; i++){
cand[i] = i;
}
// 정답을 만들기 위한 난수
srand(time(nullptr));
// 정답을 만듦.
for(int i = 0 ; dL > i ; i++){
int idx = rand() % cand.size();
answer[i] = cand[idx];
cand.erase(cand.begin() + idx);
}
// 후보군 삭제.
cand.clear();
}
// 사용자 입력 받기.
// in : 입력 받은 데이터 반환 (call by reference)
// dL : 게임의 난이도.
int getInput(vector<int> &in, int dL){
in.resize(dL);
//설명문.
string info;
info += "Enter the ";
info += (static_cast<char>(dL) + '0');
info += " numbers ( ";
for(int i = 0 ; dL > i ; i++){
info += "0 ";
}
info += "is give up)";
// 설명문 제작 완료.
// 모든 입력이 0이면 강제 종료.
int sum = 0;
cout << info << endl;
for(int i = 0 ; dL > i ; i++){
cin >> in[i];
sum += in[i];
}
vector<int> sortedIn = in;
sort(sortedIn.begin(), sortedIn.end());
// unique 함수의 결과가 끝이 아닌 조건 = 중복 숫자 입력됨.
while(sortedIn.end() != unique(sortedIn.begin(), sortedIn.end())){
// 강제 종료 조건으로 인해 강제 종료.
if(0 == sum){
return 1;
}
// 중복 되었음을 밝히고, 새로운 입력을 받음.
cout << "Duplicated input" << endl;
cout << info << endl;
sum = 0;
for(int i = 0 ; dL > i ; i++){
cin >> in[i];
sum += in[i];
}
sortedIn = in;
sort(sortedIn.begin(), sortedIn.end());
}
return 0;
}
// 정답 검사
// jud : 결과
// in : 입력
// ans : 정답
// dL : 난이도
bool judge(vector<int> &jud, vector<int> &in, vector<int> &ans, int dL){
bool res = false;
// strike
jud[0] = 0;
// ball
jud[1] = 0;
// 단순 비교를 통한 결과 계산.
for(int i = 0 ; dL > i ; i++){
for(int j = 0 ; dL > j ; j++){
if(ans[i] == in[j]){
res = true;
if(i == j){
jud[0]++;
}else{
jud[1]++;
}
}
}
}
// res 가 false 면 아웃.
return res;
}
int main(int argc, char ** argv){
cout << "Enter the defficulty level (3 or 4) : ";
// 난이도
int dL;
cin >> dL;
// 3아웃 제도.
int oC = 0;
// 정답
vector<int> ans;
// 사용사 입력
vector<int> in(dL, 0);
// 결과 : 0 = 스트라이크 1 = 볼
vector<int> jud(2);
// 정답 만들기
makeAnswer(ans, dL);
// 9번의 기회 제공
for(int t = 1 ; 10 > t ; t++){
cout << "Round " << t << "/9 : ";
if(1 == getInput(in, dL)){
break;
}
if(judge(jud, in, ans, dL)){
cout << jud[0] << " Strike " << jud[1] << " Ball" << endl;
}else{
cout << "Out" << endl;
oC++;
// 아웃 카운트 확인.
if(3 == oC){
cout << "Three Out!" << endl;
break;
}
}
if(dL == jud[0]){
cout << "You Win !! Congratulation" << endl;
return 0;
}
}
cout << "You Lost ..." << endl;
return 0;
}아래 스냅숏은 dL을 3과 4로 했을 때 구동 화면을 보여줍니다.
흠. 오늘도 분량이 너무 기네요. 원래 코드가 길어서 그런 거 같습니다.
봐주셔서 감사합니다.
파랑이 구현 링크 입니다.
2021.03.30 - [Program Language and Algorithm] - C++로 만드는 숫자 야구 게임 : 문제를 푸는 알고리듬
C++로 만드는 숫자 야구 게임 : 문제를 푸는 알고리듬
이전 글에서는 초록이(문제를 내는 알고리듬)를 만들었으니 이번엔 파랑이를 만들어 주려고 합니다. 2021.03.29 - [Program Language and Algorithm] - C++로 만드는 숫자 야구 게임 : 문제를 내는 알고리즘 C+
sbinroom.tistory.com
'Program Language and Algorithm' 카테고리의 다른 글
| 중복 없는 수열 만드는 알고리즘 ( C++로 만드는 숫자 야구 게임 ) (0) | 2021.04.02 |
|---|---|
| C++로 만드는 숫자 야구 게임 : 문제를 푸는 알고리듬 (0) | 2021.03.30 |
| Call by Value and Call By Reference (0) | 2021.03.26 |
| 메모이제이션 : 중복 연산 해결 (러시안 페인트공 알고리듬) (0) | 2021.03.25 |
| 러시안 페인트공 알고리듬 (0) | 2021.03.25 |
