[컴퓨팅 사고] 알고리즘

컴퓨터는 어떻게 가공하여 출력하는 것일까? 일상 생활에서 다양한 문제를 처리하는 방식과 같이 컴퓨터 또한 순서대로 필요한 동작을 하며 문제를 처리하는 것을 알고리즘이라고 한다.

 

💡 핵심 단어 : 알고리즘, 의사코드

 

input -> [       ] -> output

알고리즘이란?

문제를 해결하는 단계적인 방법

 

예시) 전화번호부

• 1. M.S 라는 사람을 찾기 위해 한장씩 넘기면서 찾는다 -> 비효율적 최악의 경우 1,000단계를 거쳐야함. (X)
• 2. 2장씩 넘긴다 -> 2배 빠른 대신 지나칠 수 있다. (X)
• 3. M 목차로 가서 뒤에 이름이 S인 목차로 간다. -> 훨씬 줄어들었다. (O)
  • 1,024 -> 512 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1
  • 10단계

즉, 이미 생각하고 있는 직관이나 생각을 코드로 해석한다고 생각하면 된다. 

 

시간복잡도

• 빨간색 - 전화번호부 예시 1.
• 노란색 - 전화번호부 예시 2.
• 초록색 - 전화번호부 예시 3.
  • 문제를 절반으로 나누고 나누고 나누고
  • 만약 페이지가 배로 늘었다고 해도 한 단계만 더 추가하면 된다. 
  • 효율성 측면에서 아주 큰 차이를 보인다

Sudo Code

• functions (동사) - 노란색 글씨
• conditions - if 뒤의 구문 -> 선택해서 답을 냄
• Boolean expressions -> 예 or 아니요, 0 or 1
• loops -> 반복, 순환
• variables
• threads
• events
• ...

 

출처 - 부스트코스 CS50 강의