๋ถ์คํธ์ฝ์ค CS50 ์ฝ์นญ์คํฐ๋ 4์ฃผ์ฐจ ์ฃผ์ ๋ '์๊ณ ๋ฆฌ์ฆ' !!
ํ๋ก๊ทธ๋๋จธ์ค์์ ์ฝ๋ฉํ
์คํธ ์ณ๋ณด๋ ค๊ณ ๊ณต๋ถํ๋ ์๊ณ ๋ฆฌ์ฆ ...
์ด๋ก ๋ ๋ชจ๋ฅด๋ฉด์ ๋ฌธ์ ๋ถํฐ ํ๊ณ ๋ชจ๋ฅด๋๊ฑด ํ์ด ์ฐพ์๋ณด๋ฉด์ ์กฐ๊ธ์ฉ ์ตํ๋ ๊ฒ ๊ฐ๋ค
๋ฌผ๋ก ๊ธฐ์ต์ ์ ๋จ๋๋ค๋ ์ฅ์ ์ด ์์์ง๋ง ๋์ด๋๊ฐ ์ฌ๋ผ๊ฐ์๋ก ๊ธฐ๋ณธ์ด ์๋ค๋๊ฒ ํฐ๋ ์๋ฐ์ ์์๋ค
์ง๊ธ์ด๋ผ๋ ๊ธฐ์ด๋ฅผ ์์๋ณด์ ๐ฅ
4์ฃผ์ฐจ์์๋ ๋ค์ํ ์๊ณ ๋ฆฌ์ฆ๊ณผ ํ๊ธฐ๋ฒ์ ๋ํด ๋ฐฐ์ ๋ค
Big-O ํ๊ธฐ๋ฒ : ์๊ณ ๋ฆฌ์ฆ์ ์ํํ๋๋ฐ ํ์ํ ์๊ฐ์ ์ํ์
ฮฉ(Omega, ์ค๋ฉ๊ฐ) ํ๊ธฐ๋ฒ : ์๊ณ ๋ฆฌ์ฆ์ ์ํํ๋๋ฐ ํ์ํ ์๊ฐ์ ํํ์
ฮ(Theta, ์ํ) ํ๊ธฐ๋ฒ : ์๊ณ ๋ฆฌ์ฆ์ ์ํ์ ๊ณผ ํํ์ ์ด ๊ฐ์ ๋
์ ํ ๊ฒ์(linear search) : ์ฒ์๋ถํฐ ๋๊น์ง ํ๋์ฉ ์์๋๋ก ๋น๊ตํ์ฌ ์ํ๋ ๊ฐ์ ์ฐพ์๋ด๋ ์๊ณ ๋ฆฌ์ฆ
์ด์ง ๊ฒ์(binary search) : ์ค๊ฐ ๊ฐ๋ถํฐ ํ์ํ๋ ์๊ณ ๋ฆฌ์ฆ
๋ฒ๋ธ ์ ๋ ฌ(bubble sort) : ๋ ๊ฐ์ ์ธ์ ํ ์๋ฃ๊ฐ์ ๋น๊ตํ๋ฉด์ ์์น๋ฅผ ๊ตํํ๋ ๋ฐฉ์
์ ํ ์ ๋ ฌ(selection sort) : ๋ฐฐ์ด ์์ ๊ฐ์ฅ ์์(ํน์ ํฐ) ์๋ฅผ ์ฐพ์ ์ฒซ ๋ฒ์งธ(ํน์ ๋ง์ง๋ง) ์์น์ ์์ ๊ตํํ๋ ๋ฐฉ์
์ฌ๊ท(recursion) : ์๊ธฐ ์์ ์ ์ฌ์ฐธ์กฐํ๋ ๋ฐฉ์
๋ณํฉ ์ ๋ ฌ(merge sort) : ํ๋์ ๋ฐฐ์ด์ ๋ ๊ฐ์ ๊ท ๋ฑํ ํฌ๊ธฐ๋ก ๋ถํ ํ, ๋ถํ ๋ ๋ถ๋ถ์ ์๋ฃ๊ฐ์ ์ ๋ ฌํ ๋ค์, ๋ ๊ฐ์ ์ ๋ ฌ๋ ๋ถ๋ถ ๋ฐฐ์ด์ ํฉํ์ฌ ์ ์ฒด๊ฐ ์ ๋ ฌ๋ ๋ฐฐ์ด์ด ๋๊ฒ ํ๋ ๋ฐฉ์
์ ๋ ฌ์ด ๋์ด๊ฐ๋ ๊ณผ์ ์ ๋ณด์ฌ์ค์ ๊ฒ์์ด๋ ์ ๋ ฌ์ ๊ด๋ จํด์๋ ์ด๋ ์ ๋ ์๋ฟ์์ง๋ง
์ด ์๊ณ ๋ฆฌ์ฆ์ ๋น
์ค๋? ํ๋ฉด ๐ ๊ธ์ ๊ธ์
์ด์ ์ ์ฌ๋ ์๋ฐ์คํฌ๋ฆฝํธ๋ก ํ๋ ์๋ฃ ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ ์ฑ
์์๋ ์ฝ๊ธด ํ์ง๋ง ๐๐
๋ฐ๋ณตํด์ ์ฌ๋ฌ ๋ฒ ์ฝ์ด์ผ ๊ฒ ๋ค ..ใ
ใ
..
๊ฐ์ ๋ค์ผ๋ฉด ํด์ฆ๋ ์ด๋ ต์ง ์๊ฒ ํ ์ ์์๋น ๐
(ํญ์ ์ฌ๊ธฐ๊น์ง ๊ธฐ๋ถ์ด ์ข๋ค..)
๋ค๋ฅธ ๋ฌธ์ ๋ ๋์ด๋๊ฐ ๋์์ ๊ฐ์ฅ ์ฌ์๋ณด์ด๋ ๋ฌธ์ ๋ฅผ ํํ๋ค
(์ด๊ฑฐ๋ผ๋ ์ ํ๋ฉด ๋คํ์ด๋ค ์ถ์ ์ฌ์ ์ด์๋ค ๐ญ)
#include <stdio.h>
#include <cs50.h>
int isAnagram(const int *n1, const int *n2);
int main(void)
{
isAnagram(12345, 54321);
isAnagram(14258, 25431);
isAnagram(11132, 21131);
}
//์ถ๋ ฅ์ ์ํ ํจ์
void check(const int *n1, const int *n2)
{
printf("์
๋ ฅ๊ฐ: %i, %i โ ", n1, n2);
if(isAnagram(n1, n2)) //isAnagram์ด ์ฐธ์ด๋ฉด
{
printf("์ถ๋ ฅ๊ฐ: True\n");
}
else //isAnagram์ด ๊ฑฐ์ง์ด๋ฉด
{
printf("์ถ๋ ฅ๊ฐ: False]\n");
}
}
//์ ๋๊ทธ๋จ์ธ์ง ์๋์ง ํ๋ณํ๊ธฐ ์ํ ํจ์
int isAnagram(const int *n1, const int *n2)
{
int i ,j;
for(i = 0; n1[i]; i++) //n1[i] ๋ฌธ์๊ฐ ์ฐธ์ด๋ฉด ๋ฐ๋ณต
{
for(j = 0; n2[j]; j++) //n2[j] ๋ฌธ์๊ฐ ์ฐธ์ด๋ฉด ๋ฐ๋ณต
{
if(n1[i] == n2[j]) //n1[i]์ n2[j]๊ฐ ๊ฐ์ผ๋ฉด
{
break;//n2[j] ๋ฐ๋ณต๋ฌธ ํ์ถ(n2[j]์ ์ฐธ์ธ ์ํ)
}
}
if(n2[j]==0) //n1[i]์ n2[j]๊ฐ ๋ค๋ฅด๋ฉด
{
return 0; //isAnagram์ ๊ฑฐ์ง
}
}
return 1; //isAnagram์ ์ฐธ
}
์ฒ์์ ์ด๋ ๊ฒ ํด์ ์ถ๋ ฅ! ํ๋๋ ์ซ์๊ฐ ๋ฐฐ์ด์ด ์๋๋ผ์ for๋ฌธ์์ ์ค๋ฅ๊ฐ ๋ฌ๋ค
(์์ธ..ใ
..)
#include <stdio.h>
#include <cs50.h>
const int FIRST_NUMBER_01[5] = {1, 2, 3, 4, 5};
const int FIRST_NUMBER_02[5] = {5, 4, 3, 2, 1};
int isAnagram(const int n1[5], const int n2[5]);
int main()
{
isAnagram(&FIRST_NUMBER_01[5], &FIRST_NUMBER_02[5]);
}
//์ถ๋ ฅ์ ์ํ ํจ์
void check(const int n1[5], const int n2[5])
{
for(int k = 0; k < 5; k++)
{
printf("์
๋ ฅ๊ฐ: %d, %d โ ", n1[k], n2[k]);
}
if(isAnagram(n1, n2)) //isAnagram์ด ์ฐธ์ด๋ฉด
{
printf("์ถ๋ ฅ๊ฐ: True\n");
}
else //isAnagram์ด ๊ฑฐ์ง์ด๋ฉด
{
printf("์ถ๋ ฅ๊ฐ: False]\n");
}
}
//์ ๋๊ทธ๋จ์ธ์ง ์๋์ง ํ๋ณํ๊ธฐ ์ํ ํจ์
int isAnagram(const int n1[5], const int n2[5])
{
int i ,j;
for(i = 0; i < 5; i++)
{
for(j = 0; j < 5; j++)
{
if(n1[i] == n2[j]) //n1[i]์ n2[j]๊ฐ ๊ฐ์ผ๋ฉด
{
break; //n2[j] ๋ฐ๋ณต๋ฌธ ํ์ถ(n2[j]์ ์ฐธ์ธ ์ํ)
}
}
if(n2[j] == 0) //n2[j]๊ฐ ๊ฑฐ์ง์ด๋ฉด
{
return 0; //isAnagram์ ๊ฑฐ์ง
}
}
return 1; //isAnagram์ ์ฐธ
}
์ด๊ฑด ์ปดํ์ผ๊น์ง ๋๋๋ฐ.. ์ถ๋ ฅํ๋ฉด ์๋ฌด๊ฒ๋ ์๋์จ๋น ๐
ํ์๋ถ๋คํํ
์ฌ์ญค๋ดค๋๋ฐ ์๋ฌด๋ ์๋ ค์ฃผ์๋ ๋ถ์ด ์์ด์
๋ผ์ด๋ธ ๊ฐ์ ๋๋๊ณ ๋ค๋ฅธ ํ๋ค์ด ํผ ํ์ด๋ฅผ ๋ด์ผ๊ฒ ๋ค ๐ฆ
๊ธ์์ผ ์ ๋
์ ์ผ์ด ์๊ฒจ ์ด๋ฒ์๋ ํ ์์ผ 3~10์์ ์ฌ๋ผ์ค๋ ๋ผ์ด๋ธ ๊ฐ์ ๋
นํ๋ณธ์ ๋ณด์๋ค
์ด๋ฒ ์ฃผ๋ถํฐ๋ ์๋ก์ด ์งํ์๋ถ๊ณผ ์๋ก์ด ์ ์๋์ผ๋ก ์งํ๋์๋ค
์ค๊ฐ์ ์ฌ์ค ์ค๋ฌด์์๋ ์๊ณ ๋ฆฌ์ฆ์ ์ง๊ฑฐ๋ ํ ์ผ์ด ์์ง๋ง
์ฝ๋๋ฅผ ์งค ๋ ์ ํ๋ฒ์๊ฐ ๋์ด์ง๋ค๊ณ ๋ง์ํด์ฃผ์
จ๋น
ํ์ฌ์์ ์ค๋ฌด๋ก ์๊ณ ๋ฆฌ์ฆ ์ง๋ผ๊ณ ์ํค๋ฉด ๊ทธ ํ์ฌ ๋์ค๋ผ๊ณ ํ์ จ ... ๐
ํ์๋ค๊ณผ ์ด๋์ ๋ ์๋
ผํ๋ฉด์ ์ฝ๋๋ฅผ ์ง๋ณด๊ณ ์ถ์๋๋ฐ
๋ค๋ค ๋ฐ์์ ์ง ์ํต์ด ์ ์๋ผ์ ์์ฝ๋ค ๐ญ๐ญ
์งํ๋ ์์ ๋ก์ด ํธ์ด๋ค ๋ณด๋ ์ฌ๋ ์ฌ๋ ์ง๋๋ง ๋ฐ๋ผ๊ฐ๋ค ๋ณด๋ฉด ์ด๋์ ์๋ฃ์ฆ ๋ฐ๊ณ ์์ ๊ฒ ๊ฐ๊ธฐ๋...
์ค์ค๋ก ๋ ์ฐพ์๋ณด๊ณ ๊ณต๋ถํด์ผ ํ๋๋ฐ ๋ง์ฒ๋ผ ์ ์ ์๋๋ ๐ต
์ค๋๋ ๋ฐ์ฑ์ผ๋ก ๋๋๋ ๋ถ์คํธ์ฝ์ค ํ๊ณ ๋ก,,,,,