알고리즘에 관한 3주차 과제 3가지입니다!
Sort, Plurality, Runoff 로 구성되어 있고, 각각의 문제 해결 방법과 코드, 중요한 부분들을 정리해보겠습니다.
사실 쉬운 버전과 어려운 버전 중에 1주차에는 호기롭게 어려운 Credit을 골랐다가 된통 혼났더랬죠...
쉬운 버전이 쉬운 버전이 아님.. Credit에도 한 여섯 시간 이상은 투자하고 머리 싸맸던 것 같아요
그래서 자존심이고 공부 가치관이고 뭐고 12월 말 안에 일단 쉬운 버전으로 과제는 다 제출해놓자고 마음을 먹고.. 이후에 코딩이라는 것에 좀 익숙해졌을 때쯤 어려운 버전들을 차근차근 해 나가 보겠다는 마인드.. ㅎㅎㅎ
아무튼 시작!
1. Sort
: Analyze three sorting programs(merge sort/ selection sort/ bubble sort) to determine which algorithms they use.
→ cs50에서 미리 작성되어 제공된 distribution code files를 다운받아 reversed/ random/ sorted list (5000/10000/50000) 각각을 sort하는 데에 걸리는 시간을 측정, 비교하여 어떤 sort type인지 맞히는 과제
우선 시간을 측정할 때에는 (terminal window):
time ./sort1 reversed5000.txt
위의 형식으로 명령어를 입력하면, 시간을 측정해 준다.
단순히 프로그램이 list를 sort해주고, 시간도 측정해 주기 때문에 데이터를 분석하는 일이 내 몫인데, 아래 표를 참고하면 도움이 된다.
| the worst case (O) | the best case (Ω) | |
| merge sort | O(n log(n)) | Ω(n log(n)) |
| selection sort | O(n^2) | Ω(n^2) |
| bubble sort | O(n^2) | Ω(n) |
- sort 1 : 다른 방법들보다 대체적으로 시간이 오래 걸리며, 50000개의 경우 reversed와 sorted list의 시간이 차이가 많이 난다
→ O와 Ω의 차이가 큰 BUBBLE SORT - sort 2 : 가장 적은 시간이 걸리며, O와 Ω의 차이가 거의 없다
→ MERGE SORT - sort 3 : 중간 정도의 시간이 걸리며, O와 Ω의 차이가 거의 없다
→ SELECTION SORT
2. Plurality
: In the plurality vote, every voter gets to vote for one candidate. At the end of the election, whichever candidate has the greatest number of votes is declared the winner of the election.
Implement a program that runs a plurality election.
2번째 과제도 이미 cs50에 의해 일부 작성되어 있는 distribution code를 다운받아 빈칸을 채우는 형태였습니다!
오리지널 코드는 다음과 같습니다 :
★ #define MAX 9
: candidate candidates[MAX] 에서 사용함으로써, 변수 candidates의 최대 숫자를 9로 제한한다는 뜻
★ if (argc < 2)
: command-line argument에 input이 적어도 하나 있어야 한다는 뜻
★ candidate_count = argc - 1
: 하나를 차지하는 './plurality' 를 빼고 센 숫자가 candidate_count에 들어간다는 뜻
★ for loop 안의 candidates[i].name = argv[i + 1];
: i가 0에서 후보자 수만큼 증가하는 루프 안에서, './plurality'를 뺀 첫 번째 후보자의 이름부터 candidates[i].name에 들어간다는 뜻
TODO #1
voter들이 투표할 때마다 각각의 후보자의 total vote 수를 업데이트 시켜야 함.
for (int i = 0; i < candidate_count; i++)
{
if (strcmp(name, candidates[i].name) == 0)
{
candidates[i].vote ++;
return true;
}
}
return false;
★ String끼리 비교할 때는 함수 strcmp( , ) == 0 사용
TODO #2
가장 많은 표를 받은 사람을 찾아 print 하기 (sorting 사용할 필요 x)
void print_winner(void)
{
int highest_vote = 0;
for (int i = 0; i < candidate_count; i++)
{
if (candidates[i].votes > highest_vote)
{
highest_vote = candidate[i].votes;
}
}
for(int i = 0; i < candidate_count; i++)
{
if(candidates[i].votes == highest_vote)
{
printf("%s\n", candidate[i].name);
}
}
}
// Find the maximum number of votes
→ candidates[i].votes를 iterate 하기 위한 for loop를 만들고, 그 속에 highest_vote와 각 후보자의 투표 수를 비교해서 큰 수를 highest_vote에 넣어 업데이트 시킨다.
// Print the candidate with maximum votes
→ candidates[i].votes를 iterate 하기 위한 for loop를 만들고, 그 속에 각 후보자의 투표 수가 highest_vote와 동일하다면 해당 후보자의 이름인 candidates[i].name을 프린트하는 함수를 사용하여 문제를 해결한다.
3. Runoff
: In an instant runoff election, voters can rank as many candidates as they wish. If any candidate has a majority (more than 50%) of the first preference votes, that candidate is declared the winner of the election. The candidate who received the fewest number of votes is eliminated from the election, and anyone who originally chose that candidate as their first preference now has their second preference considered, and so on.
간략히 말해서 2번째 과제와 비슷한 선거 시스템을 만드는데, 앞의 plurality와 달리 투표 순서에 따라 선호도가 만들어져 반영됩니다. 50% 이상의 지지율을 받은 후보는 바로 그 선거의 우승자가 되지만, 그렇지 않을 경우 가장 적은 표를 받은 선거는 투표에서 제거되고, 두 번째로 선호도가 높은 후보가 선거 결과에 반영됩니다. 이 방식의 장점은 투표자들의 선호를 더 잘 반영한다는 장점을 가지고 있습니다.
이번에도 사전에 cs50에 의해 작성되어 다운받은 distribution code는 다음과 같습니다 :
참 긴데요.. 하나하나 뜯어보면서 같이 과제를 해결해보아요 ^~^
2번째 과제와 다른 부분이라고 한다면 minimum votes수를 가진 후보를 제거한다는 점에서
candidate struct 안에 bool eliminated; 가 추가되었습니다!
투표자들이 투표함에 따라서 각각에 따른 Rank를 매기고, vote 형식에 맞지 않을 경우 'Invalid vote.'를 프린트하는 부분입니다.
ⓐ outer loop (int i)
: 각각의 투표자들을 iterate 하는 loop
ⓑ inner loop (int j)
: 각각의 투표자들의 각각의 rank를 iterate 하는 loop
ⓒ prompt name
string name = get_string("Rank %i:", j + 1);: j + 1 인 이유는 rank가 0이 아니라 1에서부터 시작하기 때문
ⓓ record vote
if (!vote(i, j, name)): vote라는 함수를 불러 invalid 할 경우 해당 문구를 프린트
그리고 여기서부터 작성해야 하는 과제 코드 시짝!!
1) Vote function
bool vote(int voter, int rank, string name)
{
//TODO
}: VOTE function 에서는 투표를 통해 받은 이름과 후보자의 이름이 동일할 경우, preferences array를 투표자와 rank를 반영하도록 update 해야합니다.
이 부분이 제일 어려웠음 무슨 말인지...???
for (int i = 0; i < candidate_count; i ++)
{
if (strcmp (name, candidates[i].name) == 0)
{
preferences[voter][rank] = i;
return true;
}
}
return false;
① 모든 후보자를 포괄하도록 후보자 수만큼 loop를 돌려주고,
② 투표를 통해 받은 이름(name)과 후보자 이름(candidates[i].name)이 동일할 경우를 strcmp 함수로 조건문을 적어주기
③ 같을 경우, preferences[voter][rank] 배열에 랭크 i를 배치해주기
→ 이로써, 각 투표자들의 각 이름별로 rank가 형성된 preferences[] 가 생겨나게 됨!
2) Tabulate function
void tabulate(void)
{
//TODO
}: Tabulate function에서는 제거되지 않은 후보자들에 대하여 각 후보자들이 받은 투표 수 만큼 votes 수를 업데이트 해야합니다.
for (int i = 0; i < voter_count; i++)
{
for (int j = 0; j < candidate_count; j++)
{
if (!candidate[preferences[i][j]].eliminated)
{
candidate[preferences[i][j]].votes ++;
break;
}
}
}
① if 조건문
if (!candidate[preferences[i][j]].eliminated) : candidate[i].eliminated 대신에 이렇게 쓰인 것은 각 rank로 업데이트 된 선호도에 따라서 candidate를 더 세분화해서 봐야 하기 때문입니다.
3) Print_winner function
bool print_winner(void)
{
//TODO
}: Print_winner function에서는 만약 한 후보자의 득표수가 과반수를 넘긴 경우 이름을 프린트하고, 아무도 이긴 사람이 없다면 false로 마무리 해야합니다.
for (int i = 0; i < candidate_count; i++)
{
if (candidate[i].votes > (voter_count / 2))
{
printf("%s\n", candidates[i].name);
return true;
}
}
return false;
① if 조건문
candidate[i].votes 즉 후보자가 얻은 득표수가 (voter_count / 2) 즉 전체 투표자수 / 2 = 과반수를 넘길 때를 말하는 조건문
4) Find_min function
int find_min(void)
{
//TODO
}: find_min function에서는 여전히 선거에 참여하는 후보자들 중 가장 적은 득표수의 후보를 찾습니다.
int min = candidates[0].votes;
for (int i = 0; i < candidate_count; i++)
{
if(!candidates[i].eliminated && candidates[i].votes < min)
{
min = candidates[i].votes;
}
}
return min;
① int min = candidates[0].votes;
: min에 첫 번째 후보자의 투표 수 값을 배정
② if 조건문
: 각 후보자가 제거되지 않았을 경우(!candidates[i].eliminated), 그 후보자의 득표수가 min보다 작을 때
③ min에 새로운 값 배정
: min = candidates[i].votes
5) is_tie function
bool is_tie(int min)
{
//TODO
}: is_tie function에서는 선거에 남아있는 후보자들의 득표수가 min으로 모두 같을 때 true를 return함
for (int i = 0; i < candidate_count; i++)
{
if(!candidates[i].eliminated && candidates[i].votes != min)
{
return false;
}
}
return true;
여기서도 true일 경우의 조건문을 찾느라 고생고생하다가, 관점을 바꾸어 false일 경우를 정의하고, 그것이 아닐 때 return true;를 하게 되니 더 쉬웠습니다. (cs50 duck 덕분에 ㅎ..)
★ 후보자가 제거되지 않고(1), 득표 수가 하나라도 min과 동일하지 않을 때(2) → return false;
(1) !candidates[i].eliminated
(2) candidates[i].votes != min
6) Eliminate function
void eliminate(int min)
{
//TODO
}: Eliminate function에서는 min 득표수를 가지고 있는 후보자를 제거합니다.
for (int i = 0; i < candidate_count; i++)
{
if (candidates[i].votes == min)
{
candidates[i].eliminated = true;
}
}
return;
이건 비교적 간단한 코드입니다!
주의할점은 candidates[i].eliminated = true; 에서 등호를 두 개가 아닌 하나 적는 것!
* = : 값을 할당한다
* == : 두 값이 같다
휴~ 여기까지 무사히 Week0부터 Week3까지 한 달치를 끝냈네요!
갈수록 Pset이 어려워지고 더 길어져서 무섭습니다만 차근차근 파고들어가보면 그렇게 못 할 것도 아닌 것 같기도 하고.. 모르겠어요
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
지레 겁먹기보다는 할 수 있다고 생각하고 덤비는 게 코딩을 대하는 좋은 자세 같아요.
컴퓨터 짜식이.... 나는 인간인데.....
그래도 1/3을 마무리하는 이 시점이 아주 뿌듯 ! 행복 ! 합니다 ㅎㅎ
시작할 때부터 원했던 정말 끈기를 길러주는 코딩 녀석.. 한 번 시작하니 오기가 생겨 정말 올해 안에 끝내고 싶네요 ^~^
다음 주도 화이팅! ♥
'CS50' 카테고리의 다른 글
| [CS50] Week 4 Section (1) | 2024.10.10 |
|---|---|
| [CS50] Week 4 Review (4) | 2024.10.09 |
| [CS50] Week 3 Section (2) | 2024.10.03 |
| [CS50] Week 3 Review (1) | 2024.10.01 |
| [CS50] Pset 2 : Scrabble, Readability, Caesar (1) | 2024.09.29 |