컴퓨팅 사고 - 알고리즘 & Pseudo code

📝boostcourse 의 '모두를 위한 컴퓨터 과학 (CS50 2019)' 을 듣고 정리한 내용입니다.

 

알고리즘

• 입력(input)에서 받은 자료를 출력(output) 형태로 만드는 처리과정을 의미함

• 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한
  규칙들의 순서적 나열
• 이러한 순서적 규칙들을 어떻게 나열하는지에 따라 알고리즘의 종류가 달라진다.
• 같은 Output이 나오더라도 출력까지 걸리는 시간에 따라서 효율성이 달라질 수 있다.

 

 

정확한 알고리즘

여기 전화번호부가 하나 있다.

전화번호부?
: 핸드폰이 보편화 되기 전에 쓰이던 방법으로 책 안에 여러 사람들의 이름과 전화번호가 적혀있는 책

여기서 Mike Smith를 찾아야 하는 상황이라고 가정해보자.

• 1번 방법
  • 첫 페이지를 펴고 Mike Smith를 찾는다
  • 없다면 한 장을 넘기고 Mike Smith를 찾는다
  • 찾을 때 까지 반복한다.
  • 결과 
    • 정확성 ↑
    • 효율성 매우↓ : 시간이 너무 많이 소요된다.
• 2번 방법
  • 첫 페이지를 펴고 Mike Smith를 찾는다.
  • 2장을 넘기고 Mike Smith를 다시 찾는다.
  • 찾을 때까지 반복한다.
  • 결과
    • 정확성 ↓ : 페이지를 지나치게 된다면 Mike Smith를 못 찾을 수도 있음
    • 효율성 ↑
• 두 방법 모두 좋은 알고리즘이라고는 할 수 없음
• 알고리즘을 평가할 때는 정확성도 중요하지만, 효율성도 중요하다.

 

 

정확하고 효율적인 알고리즘?

   → 1, 2번보다 더 직관적이고 효율적인 알고리즘을 적용해보자😄

• 3번 방법
  1. 전화번호부의 가운데를 편다.
     • 만약 여기에 Mike Smith가 있다면 알고리즘 종료
  2. 없다면 ABC순서이므로 Mike Smith가 앞, 뒤 어느 쪽에 있는지 판단하여 없는 쪽을 버린다.
  3. 남은 책의 가운데 페이지를 편다.
     • Mike Smith가 있다면 종료
     • 없다면 2번으로 돌아가서 Mike Smith를 찾을 때 까지 반복한다.

 전화번호부의 페이지가 200장이 더 추가되었다고 가정해보자

1번 방법	3번 방법
한 장을 넘기고 또 한 장을 넘기는 규칙들의 순서적 나열	반을 줄이고, 또 반을 줄이는 규칙들의 순서적 나열
→ 페이지를 100번 더 넘겨야 한다.     = 절차가 100번 추가	→ 절반씩 줄어드는 알고리즘이므로 1번만 더 수행한다.     = 절차 1번만 더 추가됨

                                                   
⇒ 즉, 3번 방법이 1번 보다 알고리즘적으로 효율적이다.

 

Pseudo code(의사 코드)

• 위와 같은 알고리즘은 아래와 같은 Pseudo 코드(의사 코드)라는 방식으로 보다 명료하게 정리할 수 있다.

• 들여 쓰기 된 부분 = 종속관계를 나타냄

1.	전화번호부를 집어 든다
2.	전화번호부의 중간을 편다
3.	페이지를 본다
4.	만약 Mike Smith가 페이지에 있으면
5.		Mike Smith에게 전화한다.
6.	그렇지 않고 만약 Mike Smith가 앞 페이지에 있으면
7.		앞 페이지의 절반을 편다
8.		3번째 줄부터 다시 실행한다
9.	그렇지 않고 만약 Mike Smith가 뒷 페이지에 있으면
10.		뒷 페이지의 절반을 편다
11.		3번째 줄부터 다시 실행한다
12.	그러지 않으면
13.		그만둔다

• Pseudo 코드를 보면 C언어나 파이썬과 같은 언어에서도 볼 수 있는 공통점이 있다.

 

1. 강조된 부분 ⇒ 함수(function)를 의미

• 함수란 컴퓨터에게 무엇을 할지 알려주는 동사와 같다.

 

2. 강조된 부분 ⇒ 조건을 의미

• 조건이란 여러 선택지 중에서 하나를 고르는 것

 

3. 강조된 부분 ⇒ 불리언(Boolean)

• 답이 예 / 아니오 또는 참(True) / 거짓(False) 또는 2진법의 0 / 1로 나오는 질문을 뜻함

 

4. 강조된 부분 ⇒ 루프(Loop)

• 무엇인가를 계속해서 반복하는 순환을 의미