[프롤로그]
자그마치 약 2주라는 시간을 들여서 풀었던 문제였다. 삽질을 하면서 현타도 여러 번 왔었고, 과연 내가 옳은 길을 가고 있는 것인가?라는 의문도 끊임없이 들었고, "내가 무엇을 놓쳤지?"라는 생각이 이 문제를 해결하기 전까지 내 머릿속을 떠나지 않았다. 해결하지 못했던 문제를 쉽게 잊어버리지 못하는 나의 성격은 포기하자는 생각을 하려던 나를 오히려 문제에 대해 더 고민하도록 만들었고, 결국 나를 문제 해결의 길로 이끌었다.
풀이 후 인터넷에 나와있는 다른 풀이들은 살펴보았는데, 내가 특이하게 풀긴 한것 같다. 고민한 시간만큼 이번 글에서는 풀이과정을 조금 자세하게 나열해 보려고 한다.
[해결 과정]
1. 확률 저장하기
입력받은 정보를 어떻게 하면 효과적으로 저장할 수 있을지 생각해보자.
예를 들어 A팀이 B팀을 이길 확률이 0.3, 비길 확률이 0.1, 질 확률이 0.6이라고 해보자.
B팀의 입장에서 보면 이길 확률은 0.6, 비길 확률은 0.1, 질 확률은 0.3이다.
A팀과 B팀이 경기를 끝낸 후에는 두 팀의 실적이 동시에 정해지기 때문에 A팀이 B팀을 상대로 이기고/비기고/질 확률은 B팀이 A팀과 이기고/비기고/질 확률과 동시에 정해진다고 볼 수 있는 것이다.
그리고 확률 수치를 보면 상대팀끼리 서로 대칭적으로 나타나는 것을 볼 수가 있는데, 이를 어떻게 하면 효과적으로 저장할 수 있을까?라는 고민을 해보다가 아래와 같은 표 형태로 저장하기로 했다.
각 칸에는 [행에 있는 팀]이 [열에 있는 팀]을 이길 확률이 들어간다. 같은 팀 끼리 경기를 하는 경우는 없기 때문에, 행과 열에 있는 팀 이름이 모두 같은 칸에는 아무런 값도 들어가지 않는다.
그래서 값을 어떻게 넣어야 되느냐 하면?
앞서 A팀이 B팀을 이길 확률이 0.3, 비길 확률이 0.1, 질 확률이 0.6이라고 했던 예시를 들어보자
이렇데 되면 A행 B열에 있는 칸에 0.3을 집어넣는다.
그리고 A가 B에게 질 이길 확률이 0.6이라 했으니, B가 A를 이길 확률도 0.6이 된다. 따라서 B행 A열에 0.6을 집어넣는다.
이러면 비길 확률은 어떻게 계산해야할까?
이미 이길 확률과 비길 확률을 저장했기 때문에 비길 확률을 따로 저장할 필요가 없다. 1-이길확률-질확률=비길 확률이기 때문이다. 따라서 이 경우에서 A와 B가 비길 확률은 1-[A행 B열 값]-[B행 A열 값]=0.1이 된다.
문제를 보면 서로 다른 팀끼리 6번의 입력이 주어지는데, 4 팀 중에서 2팀을 선택하는 경우의 수 6(4C2)와 일치하여 문제의 입력만으로 모든 경기의 확률을 계산할 수 있다. 한 경기당 표를 2칸씩 채움으로써 16칸 중 같은 팀을 나타내는 4칸을 제외한 12칸을 모두 채우면 된다.
<확률을 입력받는 input 함수(인자 : 확률 저장 배열, 팀 이름 문자열 배열)>
void input(double percent[][4], char team_names[][11]) {
double win, draw, lose;
char teama[11] = { 0, };
char teamb[11] = { 0, };
scanf("%s %s %lf %lf %lf", teama, teamb, &win, &draw, &lose);
getchar();
int teama_position = findindex(team_names, teama);
int teamb_position = findindex(team_names, teamb);
percent[teama_position][teamb_position] = win;
percent[teamb_position][teama_position] = lose;
}
2. 모든 경우의 수 발생시키기
경기는 총 6번 독립적으로 진행된다(독립 조건은 문제에 제시되어있음). 이기고/비기고/지는 3가지 경우가 6번 독립적으로 발생하여 총경우의 수는 3^6개가 된다. 이 모든 경우의 수를 어떻게 발생시킬 것인가?
나의 경우에는 재귀 함수를 가장 먼저 떠올렸다.
배열이 한번 채워질 때마다 완성된 배열을 인자로 넘겨줘서 계산 작업을 처리할 것이다.(총 3의 6 제곱만큼 처리 함수가 호출될 것)
0은 승리, 1은 무승부, 2는 패배를 의미한다.
<모든 경우의 수를 발생시키는 test 함수(인자 : 확률표, 경우의 수 저장공간,현재 결정해야할 경우의수 배열 인덱스, 누적 확률을 저장할 주소, 확률을 구하고자 하는 팀 인덱스>
void test(double percent_table[][4], int choice[], int choice_index, double* presult, int index) {
if (choice_index == 5) {
for (int i = 0; i < 3; i++) {
choice[choice_index] = i;
*(presult) += get_percent(percent_table, choice, index);
}
}
else {
for (int i = 0; i < 3; i++) {
choice[choice_index] = i;
test(percent_table, choice, choice_index + 1, presult, index);
}
}
}(get_percent에서 구한 각 경우의 수가 실현된 확률을 따로 마련해둔 변수에 누적해서 저장한다.)
3. 확률 계산하기
경기가 진행될 경우의 수가 하나 나오면, 해당 경우의 수로 특정 팀이 이길 확률을 구하기 위해서는 총 2가지의 확률을 구해야 한다.
1. 해당 경우로 경기가 진행될 확률 구하기
2. 해당 팀이 상위 2위에 들 확률 구하기
3-1. 해당 경우로 경기가 진행될 확률 구하기
확률을 계산할 때도 표를 이용할 것이다.
2번 과정에서 구했던 경우의 수 중 하나가 다음 배열이라고 가정해보자
배열을 다음과 같이 표로 옮긴다.(왼쪽 위부터 순서대로 옮겼다.)
이렇게 대각선 기준 오른쪽 위 6칸을 채웠는데, 이렇게 하면 두 팀 간 6번의 경기 결과를 겹치지 않고 모두 담을 수 있다.
여기에 1번에서 작성했던 확률 표를 가져와보자
여기 두 가지 표를 이용해서 해당 경우로 경기가 진행될 확률을 구할 수 있다.
예를 들어 A는 B를 이길 확률이 0.3인데, 이 경우의 수에서는 A가 B를 이겼으므로 해당 경기가 성립될 확률은 0.3이다.
다음 예시로는, A와 C와의 경기를 들 것인데, A가 C를 이길 확률은 0.2고, 이 경우에서는 A와 C가 비겼다. 따라서 해당 경기가 성립될 확률은 1-[A행C열 = 0.2]-[C행A열 = 0.7] = 0.1이 된다.
이런 식으로 6개 경기에 대한 확률은 모두 구해준 후 모두 곱해주면 6번의 경기가 주어진 경우에 성립할 확률을 구할 수 있다.(확률을 모두 곱해주는 이유는 한 경기가 다른 경기에 영향을 미치지 않기 때문이다.)
<3-1을 구현한 함수, possibility에 각 확률을 곱해서 누적시킨다. (인자 : 확률표, 현재 경우의 수 배열, 팀 인덱스)>
double get_possibility(double percent_table[][4], int choice[], int index) {
int board[4][4] = { {0,}, };
int choice_index = 0;
for (int i = 0; i < 3; i++) {
for (int k = i + 1; k <= 3; k++) {
board[i][k] = choice[choice_index++];
}
}
double possibility = 1.0;
for (int i = 0; i < 3; i++) {
for (int k = i + 1; k <= 3; k++) {
if(board[i][k] == 0){
possibility *= percent_table[i][k];
}
else if (board[i][k] == 1) {
possibility *= (1.0 - percent_table[i][k] - percent_table[k][i]);
}
else {
possibility *= percent_table[k][i];
}
}
}
return possibility;
}
3-2. 해당 팀이 상위 2위 안에 들 확률 구하기
순위를 구하기에 앞서 각 팀이 얻는 총점을 모두 구해야 한다. 우선 B팀의 총점을 구해보자
탐색 기준은 [(구하고자 하는 팀 이름)행 (구하고자 하는 팀 이름) 열] 칸을 기준으로, 맨 위에서부터 아래로 내려온 다음, 기준 칸을 만난다면 오른쪽으로 가는 방향으로 탐색할 것이다.
앞선 풀이 방식대로라면 승패를 세로축에 있는 팀 이름 기준으로 따져야 하는데, 파란색 칸을 보면 승점을 구하고자 하는 팀 이름이 세로축이 아닌 가로축에 있는 것을 볼 수 있다. 따라서 파란색 칸을 탐색할 때에는 승점을 더할 때 반대로 더해야 한다는 것을 인지하고 있어야 한다.(이번 예시에서는 0, 즉 A의 승리라고 기록되어 있기 때문에 B의 승점을 더하지 않는 것이다. 만약 2라고 적혀있다면 승점 3점을 더할 것이다.)
따라서 승점을 계산하는 방식은 다음과 같다.
파란색 영역에서:
0 : 승점 없음
1 : 승점 1
2 : 승점 3
초록색 영역에서:
0 : 승점 3
1 : 승점 1
2 : 승점 0
아래의 그림들을 참고하여 이 방식으로 A~D까지의 승점을 모두 구해준다.(B는 했으므로 그림 생략)
<특정 팀의 승점을 구하는 get_score 함수>
int get_score(int index, int choice[]) {
int board[4][4] = { {0,}, };
int choice_index = 0;
for (int i = 0; i < 3; i++) {
for (int k = i + 1; k <= 3; k++) {
board[i][k] = choice[choice_index++];
}
}
int sum = 0;
int x = index, y = 0;
for (; y < index; y++) {
if (board[y][x] == 0)
sum += 0;
else if (board[y][x] == 1)
sum += 1;
else
sum += 3;
}
for (x = index + 1; x < 4; x++) {
if (board[y][x] == 0)
sum += 3;
else if (board[y][x] == 1)
sum += 1;
else
sum += 0;
}
return sum;
}
다음으로는 특정 팀이 순위에 들 확률을 구한다. 순위와 함께 동점자 수를 미리 구해놓는다.
만약 동점자로 인해 1~2등에 속한 인원이 3명이 넘어간다면 추첨을 해야 한다. 순위별로 추첨을 해야 하는 상황을 분석해보자.
1등에 속했을 때 동점자 2명 이상, 2등에 속했을때 동점자 1명 이상일 때 추첨을 진행한다.
따라서 2등 이내일 때 (순위+동점자수)가 3 이상일 때 추첨을 진행하는 것이다. 추첨을 할 때 만약 1등이면 당첨 확률은
2 / (동점자수+1)이고, 2등이면 1 / (동점자수 + 1)이다.(문제 풀 때 추첨 시 당첨 확률을 1등일 때랑 2등일 때를 같게 해 놓은 것이 오류라는 것을 한참 동안 모르고 있었다...)
이외의 상황에서는 2등 이내면 100%, 2등 초과면 0%라고 확률을 구할 수 있다.
<결승 진출 확률을 구하는 get_qa_percent 함수(인자 : 4팀의 승점이 담긴 배열, 진출 확률을 구하고자 하는 팀 인덱스>
double get_qa_percent(int score_list[], int index) {
int same_rank = 0;
int rank = 1;
for (int i = 0; i < 4; i++) {
if (score_list[i] > score_list[index])
rank++;
else if (score_list[i] == score_list[index] && index != i)
same_rank++;
}
if (rank >= 3)
return 0.0;
else if (rank <= 2 && (same_rank + rank) > 2) {
int pnum = same_rank + 1;
return ((3 - rank) * 1.0 / pnum);
}
else
return 1.0;
}
3-1과 3-2에서 확률을 곱하면 2번 풀이에서 전달받은 경우의 수에서 특정 팀이 다음 라운드에 진출할 확률을 구할 수 있다.
<index번째 팀의 진출 확률을 구하는 get_percent 함수 (인자 : 확률표, 현재 경우의 수 배열, 팀 인덱스)>
double get_percent(double percent_table[][4], int choice[], int index) {
double percent = get_possibility(percent_table, choice, index);
int score_list[4] = { 0, };
for (int i = 0; i < 4; i++) {
score_list[i] = get_score(i, choice);
}
percent *= get_qa_percent(score_list, index);
//percent *= 1;
return percent;
}4. 계산된 확률 구하기
3번 풀이에서 구한 확률은 3^6가지의 경우의 수 중 1가지에 대하여 구한 확률이다. 모든 경우의 수는 동등하게 이루어지기 때문에 3^6가지의 경우의 수에 대해 3번 풀이과정을 반복해서 확률을 구하고, 이 확률들을 모두 더하면 된다.
이렇게 하면 특정 하나의 팀이 다음 라운드에 진출할 확률을 구할 수 있다.
<test함수에 들어있는 확률 합 누적 코드>
*(presult) += get_percent(percent_table, choice, index);5. 모든 팀에 대하여 진출 확률 구하기
문제에서는 모든 팀에 대하여 진출 확률을 구하라고 했으므로 대상 팀들을 하나씩 인자로 전달해주면서 문제에서 구하라는 값을 구해주면 된다.
<main 함수에 들어있는 출력 코드>
for (int i = 0; i < 4; i++) {
double p = 0;
int choice[6] = { 0, };
test(percent, choice, 0, &p, i);
printf("%.10f\n", p);
}
★. 추가로 사용한 코드
<findindex함수> - 문자열 배열을 입력받아 해당 팀이 몇 번째 인덱스에 있는지 구하는 함수이다.
int findindex(char strs[][11], char* str) {
int result = -1;
for (int i = 0; i < 4; i++) {
if (!(strcmp(strs[i], str))) {
result = i;
break;
}
}
return result;
}
[전체 코드]
#pragma warning(disable:4996)
#include <stdio.h>
#include <string.h>
int findindex(char strs[][11], char* str) {
int result = -1;
for (int i = 0; i < 4; i++) {
if (!(strcmp(strs[i], str))) {
result = i;
break;
}
}
return result;
}
int get_score(int index, int choice[]) {
int board[4][4] = { {0,}, };
int choice_index = 0;
for (int i = 0; i < 3; i++) {
for (int k = i + 1; k <= 3; k++) {
board[i][k] = choice[choice_index++];
}
}
int sum = 0;
int x = index, y = 0;
for (; y < index; y++) {
if (board[y][x] == 0)
sum += 0;
else if (board[y][x] == 1)
sum += 1;
else
sum += 3;
}
for (x = index + 1; x < 4; x++) {
if (board[y][x] == 0)
sum += 3;
else if (board[y][x] == 1)
sum += 1;
else
sum += 0;
}
return sum;
}
double get_qa_percent(int score_list[], int index) {
int same_rank = 0;
int rank = 1;
for (int i = 0; i < 4; i++) {
if (score_list[i] > score_list[index])
rank++;
else if (score_list[i] == score_list[index] && index != i)
same_rank++;
}
if (rank >= 3)
return 0.0;
else if (rank <= 2 && (same_rank + rank) > 2) {
int pnum = same_rank + 1;
return ((3 - rank) * 1.0 / pnum);
}
else
return 1.0;
}
double get_possibility(double percent_table[][4], int choice[], int index) {
int board[4][4] = { {0,}, }; // 승패여부
int choice_index = 0;
for (int i = 0; i < 3; i++) {
for (int k = i + 1; k <= 3; k++) {
board[i][k] = choice[choice_index++];
}
}
double possibility = 1.0;
for (int i = 0; i < 3; i++) {
for (int k = i + 1; k <= 3; k++) {
if(board[i][k] == 0){
possibility *= percent_table[i][k];
}
else if (board[i][k] == 1) {
possibility *= (1.0 - percent_table[i][k] - percent_table[k][i]);
}
else {
possibility *= percent_table[k][i];
}
}
}
return possibility;
}
double get_percent(double percent_table[][4], int choice[], int index) {
double percent = get_possibility(percent_table, choice, index);
int score_list[4] = { 0, };
for (int i = 0; i < 4; i++) {
score_list[i] = get_score(i, choice);
}
percent *= get_qa_percent(score_list, index);
return percent;
}
void test(double percent_table[][4], int choice[], int choice_index, double* presult, int index) {
if (choice_index == 5) {
for (int i = 0; i < 3; i++) {
choice[choice_index] = i;
*(presult) += get_percent(percent_table, choice, index);
}
}
else {
for (int i = 0; i < 3; i++) {
choice[choice_index] = i;
test(percent_table, choice, choice_index + 1, presult, index);
}
}
}
void input(double percent[][4], char team_names[][11]) {
double win, draw, lose;
char teama[11] = { 0, };
char teamb[11] = { 0, };
scanf("%s %s %lf %lf %lf", teama, teamb, &win, &draw, &lose);
getchar();
int teama_position = findindex(team_names, teama);
int teamb_position = findindex(team_names, teamb);
percent[teama_position][teamb_position] = win;
percent[teamb_position][teama_position] = lose;
}
int main(int argc, char* argv[])
{
double percent[4][4] = { 0, };
char team_names [4][11] = { {0,} };
for (int i = 0; i < 4; i++) {
scanf("%s", team_names[i]);
getchar();
}
for (int i = 0; i < 6; i++) {
input(percent, team_names);
}
for (int i = 0; i < 4; i++) {
double p = 0;
int choice[6] = { 0, };
test(percent, choice, 0, &p, i);
printf("%.10f\n", p);
}
}
이 문제만큼 코딩에 대한 자신감을 끌어올리는 문제는 없었다. 하지만, 더 최적의 방법으로 문제들을 해결할 수 있도록 앞으로 알고리즘 공부.. 열심히 해야겠다!
'백준' 카테고리의 다른 글
| [C언어] 14888번 연산자 끼워넣기 (삼성 SW 역량 테스트 기출 문제) (0) | 2022.03.14 |
|---|---|
| [문제해결] 1436번 : 영화감독 숌 해결과정 (0) | 2022.02.16 |
