Algorithm. concept

[Visual Studio과 C#으로 구현]
Algorithm concept // Week01

20210908_20615034

Algorithm; 해법, 문제를 해결하는 단계적 절차(방법)

자료구조 + 알고리즘 = 프로그램

< 알고리즘의 특성 >

• - 정확성 : 주어진 입력에 대해 올바를 해를 주어야한다.
• - 수행성 : 각 단계는 컴퓨터에서 수행가능 해야한다.
• - 유한성 : 일정한 시간 내에 종료되어야한다. 
• - 효율성 : 효율적일 수록 가치가 높아진다.

< 알고리즘의 예 >

• 01. 가장큰 수 찾기  //정렬 알고리즘
• 02. 원하는 값 찾기  //탐색 알고리즘(순차/이진)
• 03. 동전 거스름돈   //탐욕 알고리즘
• 04. 한 붓 그리기     //오일러 써킷
• 05. 미로 찾기         //오른손 법칙
• 06. 가짜동전 찾기   //분할 정복 알고리즘
• 07. 독이 든 술단지  //2진수 활용

.

.

.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

• 01. 가장큰 수 찾기  //정렬 알고리즘

=> 정렬 알고리즘 사용 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

• 02. 원하는 값 찾기  //탐색 알고리즘(순차/이진)

ㅡㅡㅡ

02-1 정렬이 되어있지 않은 경우

=> 선형탐색 알고리즘 택

'O(N)' 에 해당하는 시간복잡도를 갖음.

평균비교 횟수 : n/2

최악비교 횟수 : n

 

-> 탐색 순서

① 처음부터 끝까지 순서대로 탐색

 

ㅡㅡㅡ

02-2 정렬이 되어있는 경우

=> 이진탐색 알고리즘 택

'O(logN)' 에 해당하는 시간복잡도를 갖음.

평균비교 횟수 : 

최악비교 횟수 : 10개 경우, 3

 

-> 탐색 순서

① 중간값 선별 

② 원하는 값과 비교 

 

③ 일치하지 않으면, (그 이상/이하 값 측정 후 해당하지 않는 부분 값 버림.)

    ①번으로 돌아감.

ㅡㅡㅡ

02-1, 02-2 비교

02-1 정렬이 되어있지 않은 경우의 'O(N)'와 02-2 정렬이 되어있는 경우의 'O(logN)' 비교 시,

'O(N)'이 커질 수록 'O(logN)'이 작아지는 것을 확인 가능하다.

따라서, 값(data)이 많아질 수록, 선형탐색을 사용하는 02-1 정렬이 되어있지 않은 경우의 'O(N)'이 더 느려진다.

그림을 보면, 값이 증가함에 따라 'O(N)'이 'O(logN)'보다 느려지는 것을 확인할 수 있다.

더 빠른 것은 이진탐색이다.

ㅡㅡㅡ
if) 정렬이 되어있지 않은 경우 이진탐색을 사용해도 빠를까?

    NO.

왜냐하면, 정렬을해야지 진행할 수 있는 알고리즘으로. 정렬이 되어있지 않을 경우, 정렬을 먼저 진행 후 이진탐색을 진행할 수 있다.

이 경우, 정렬알고리즘을 먼저 사용 후 사용해야한다. (01. 가장큰 수 찾기 참고)

정렬알고리즘은 'O(NlogN)'인데, 이는 선형탐색'O(N)'과 이진탐색'O(logN)'보다도 느릴 뿐더러 정렬이 되어있지 않은 이진탐색이었으므로, 정렬 후에 이진탐색을 다시 또 해줘야하는 상황이 발생한다. 

2번의 알고리즘으로 디버깅 속도도 느려졌을 뿐더러 정렬알고리즘 자체 특성상 느려서 느리고 느려 더 느려진다 고로 NO다.

ㅡㅡㅡ
if) 그럼 정렬알고리즘은 느리니까 무조건 안 쓰는 것이 좋은가?

    NO.

알고리즘이란 효율성이 가장 민감하다.

효율적으로 생각했을 때. 정렬 후, 여러번 사용할 것이라면 정렬을 한 번 해주고 이진탐색을 사용하는 것이 더 좋다. 고로 NO다.

ㅡㅡㅡ

if)  항상 효율적으로 써야겠다. 

    NO.

값의 갯수가 적으면 처리 속도는 거의 다 비슷하다. 

항상 효율적인 알고리즘이 좋은 것은 아니다. 때에 맞게 쓰는 것이 더 중요한 것.

• 03. 동전 거스름돈   //탐욕 알고리즘

=> 탐욕 알고리즘 사용 

실제화폐발행에 사용

가장 큰 것부터 채워나감

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

• 04. 한 붓 그리기     //오일러 써킷

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

• 05. 미로 찾기         //오른손 법칙

=> 오른손 법칙 사용

오른손으로 벽쓸고 다니면 미로탈출이 가능하다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

• 06. 가짜동전 찾기   //분할 정복 알고리즘

=> 분할정복 사용 (DIVIDE & CONQUER)

분할해서 정복한다.

ㅡㅡㅡ

06-1 1번방법

-> 1개를 기준으로 모든 동전을 다 비교해본다.

1024-1=1023 

1023

ㅡㅡㅡ

06-2 2번방법

-> 둘 씩 비교해본다.

1024/2=512

512

ㅡㅡㅡ

06-3 3번방법 (가장 좋은방법)

-> 반씩 나누어 비교(이진탐색 같은데 맞는지 모르겠음)

1024/2, 512/2,  ...  =10번

10


ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

• 07. 독이 든 술단지  //2진수 활용

=> 2진수를 활용한다.

1024개의 독이 든 술단지 경우, 먹어야 알 수 있음. 사상자를 최대한 줄여야함.

-> 방법예시

술병이 4개일 경우,

00 01 10 11 와 같은 코드 생성

A에겐 코드의 첫 번째 자리 1이오면 술 먹게 함.

B에겐 코드의 두 번째 자리 1이오면 술 먹게 함.

if) 10의 코드를 가진 세 번째 술통에 독이 들었다면,

첫 번째 자리에만 코드 1이 있으므로

첫 번째 자리에 코드 1이 있는 술을 먹게한 A만 죽는다. 

고로 10 코드에 술이 있음을 알 수 있다.

2^n=1024 이므로 

n=10 이다.

고로 1024일 경우, 10자리 코드를 생성해야한다.

최악의 경우 희생자 수는 log(밑2)n 명이므로,

log(밑2)n  = log(밑2)1024 = log(밑2)2^10 = 10

10

0000000000의 코드가 있기 때문에 최선의 희생자 수는 0명이다.

0~10명의 희생자가 배출된다.