Ch01_컴퓨팅사고의시작(3)_알고리즘

03.알고리즘

•알고리즘의 정의를 설명할 수 있다.
•알고리즘의 조건(입력, 출력, 명확성, 유한성, 유효성)을 설명할 수 있다.
•의사코드와 순서도로 알고리즘을 표현할 수 있다.

우리는 문제 해결을 위한 컴퓨팅 사고력의 개념, 즉 문제를 분해하고 문제의 유형과 그 데이터를 통해 패턴을 인식하며, 상태를 대표값으로 표현하는 추상화 과정에 관하여 예를 들어 학습해 보았다. 오늘은 이러한 문제 분해, 패턴 인식, 추상화를 어떻게 컴퓨터 시스템으로 구현하는지 그 단계에 관하여 알아보고자 한다. 즉, 컴퓨팅 사고를 구현하는 과정인 알고리즘에 관하여 살펴보고, 이를 프로그래밍 언어인 파이썬으로 실행하기 위해 직접 환경을 설정해 보도록 하겠다.

---

알고리즘이 역할 – 컴퓨팅 사고력의 구현

알고리즘이란 주어진 문제를 해결하기 위한 명확한 단계적 절차이다. 문제를 해결하기 위해 단계별로 나아가는 논리적인 방법이라고 볼 수 있다. 알고리즘을 설계하는 과정은 다음과 같은 단계로 구성된다.

1. 문제 정의 및 분석: 해결하고자 하는 문제를 명확하게 정의하고, 그 문제의 입력과 출력을 구체적으로 분석한다.
2. 문제 분해: 문제를 더 작은 하위 문제로 나누는 과정이다. 이는 복잡한 문제를 더 쉽게 이해하고 해결할 수 있도록 도와준다.
3. 패턴 인식: 문제에서 반복적으로 나타나는 패턴을 찾아내는 것이다. 패턴을 인식하면 유사한 문제를 동일한 방법으로 해결할 수 있게 된다.
4. 추상화: 문제를 단순화하는 과정이다. 중요한 정보만 남기고, 불필요한 세부 사항은 제거하여 핵심을 파악하는 것이 목적이다.
5. 알고리즘 설계: 문제를 해결하는 구체적인 절차를 설계한다. 이때 알고리즘은 명확하고 효율적으로 설계되어야 한다.

---

알고리즘이 역할 – 컴퓨팅 사고력의 구현

컴퓨터는 문제를 명확하게 이해하기 위해 먼저 문제 분석과 데이터 수집을 거친다. 그 후, 문제 해결을 위해 문제 분해, 패턴 인식, 그리고 추상화의 단계를 거친다. 

이 과정에서 문제를 더 간단하게 만들기 위해 불필요한 부분은 제거하고, 핵심 요소와 개념 또는 기능만 간추려 일반화된 모델을 만든다. 이 추상화 과정은 복잡한 문제를 단순화시키는 데 중요한 역할을 하며, 이를 통해 문제를 해결할 수 있는 구조적인 방법을 도출하게 된다. 추상화를 자동화하기 위해 우리는 컴퓨터를 활용한다. 컴퓨터는 주어진 문제를 분석하고, 적절한 방식으로 추상화된 모델을 처리하여 해결책을 찾는다. 이러한 과정을 컴퓨터로 구현할 수 있게 해주는 사고의 체계가 바로 알고리즘이다.

즉, 알고리즘은 문제를 해결하기 위한 단계적인 절차이며, 이러한 절차를 바탕으로 컴퓨터는 문제를 자동으로 처리할 수 있게 된다.

---

우리가 라면을 끓인다고 생각 해 볼까요.?

1. 물 550ml를 끓인다.
2. 스프와 면을 넣고 4분 더 끓인다.
3. 맛있게 먹는다.

이러한 알고리즘을 바탕으로 개인의 기호에 맞춰 다양한 변형이 가능하다는 점도 언급되어 있습니다. 알고리즘의 핵심은 문제 해결을 위한 구체적이고 단계적인 절차를 제공하는 것이며, 이를 통해 문제를 효율적으로 해결할 수 있습니다.

---

알고리즘 - 문제 해결을 위한 단계적인 절차

다시 한번 문제 해결을 위한 단계적인 절차, 알고리즘을 정리하면 다음과 같이 정의할 수 있다.

• 문제를 해결하는 방법을 각 단계별로 정리해 놓은 것이다.
• 어떤 일을 수행할 수 있는 일련의 명령어 또는 규칙의 집합이다.
• 선택된 목적지에 도달할 수 있는 일련의 명령어들이다.
• 인간을 위한 체계적이고 효율적인 방법이자 강력한 도구이다.

---

알고리즘의 기본 조건

알고리즘의 기본 조건에 대해 설명하면 다음과 같다:

1. 입력 (Input):
   알고리즘이 작동하기 위해서는 외부로부터 제공되는 데이터가 필요하다. 이는 0개 이상의 입력 데이터일 수 있으며, 문제를 해결하는 데 필요한 정보로 사용된다.
2. 출력 (Output):
   알고리즘은 반드시 하나 이상의 결과를 생성해야 한다. 이 결과는 문제의 해답이나 처리된 데이터를 의미하며, 컴퓨터가 문제를 해결하기 위해 수행하는 작업의 최종 산출물이다.
3. 명확성 (Definiteness):
   알고리즘의 각 단계는 명확하고 모호하지 않아야 한다. 즉, 알고리즘의 모든 단계가 구체적으로 정의되어야 하며, 그 내용에 모순이나 불확실성이 없어야 한다. 이를 통해 알고리즘이 일관되게 작동할 수 있다.
4. 유한성 (Finiteness):
   알고리즘은 유한한 수의 단계를 거친 후 반드시 종료되어야 한다. 무한 루프에 빠지지 않고, 일정한 시간이 지나면 결과를 내어야 한다. 그렇지 않으면 알고리즘은 답을 제시하지 못하고 계속해서 실행될 것이다.
5. 유효성 (Effectiveness):
   알고리즘의 각 단계는 실행 가능해야 하며, 실제로 수행될 수 있는 명령이어야 한다. 또한, 그 단계는 너무 복잡하지 않고 충분히 단순해야 하며, 필요한 연산이나 명령이 실질적으로 유효하게 작동할 수 있어야 한다.

이러한 기본 조건을 만족하는 알고리즘이야말로 신뢰할 수 있고 효율적인 문제 해결 방법을 제공할 수 있다.

---

알고리즘의 기본 조건 - 예제

아침 수업을 듣기 위한 과정을 알고리즘으로 표현하면 다음과 같다.

1. 알람 소리 듣고 기상
2. 등교 준비
3. 교통 환경에 따른 이동 수단 선택
4. 학교 도착 후 강의실 출입

알고리즘의 조건

• 입력성: 외부에서 제공하는 0개 이상의 입력이 존재해야 한다.
• 출력성: 1개 이상의 출력이 존재해야 한다.
• 명백성: 각 명령어의 의미가 모호하지 않고 명확해야 한다.
• 유한성: 한정된 명령어가 실행된 후에는 반드시 종료되어야 한다.
• 유효성: 각 명령어들은 실행 가능한 연산이어야 한다.

아침 수업 듣기 위한 과정을 알고리즘으로 표현한다면, 각 단계가 명확해야 하며, 그 결과로서 학생이 수업에 참여할 수 있어야 합니다. 아래는 이 과정을 알고리즘으로 간략하게 표현한 예입니다.

아침 수업을 듣기 위한 과정:

• 알람 소리 듣고 기상
• 등교 준비
• 교통 환경에 따른 이동 수단 선택
• 학교 도착 후 강의실 출입

입력 (Input)

• 학생
• 수업 시작 시간
• 알람 시간

출력 (Output)

• 학생이 수업에 시간에 맞춰 도착

단계 (Procedure)

1. 알람이 울리면 깨어난다.
2. 이불을 걷고 일어난다.
3. 개인 위생을 청한다 (예: 양치질, 세수하기 등).
4. 옷을 입는다.
5. 아침을 먹는다.
6. 학교에 가기 위한 교통수단을 선택한다 (예: 버스, 지하철, 자전거 등).
7. 학교에 도착하여 수업에 참여한다.

유한성 (Finiteness)

• 모든 단계가 완료되면, 학생은 수업에 참여할 것입니다. 이 과정은 수업이 끝날 때까지 유한합니다.

명확성 (Definiteness) & 유효성 (Effectiveness)

• 각 단계는 명확하고 실행 가능해야 하며, 모든 단계를 거쳐 학생은 수업에 참여할 수 있어야 합니다.

이처럼 아침 수업에 참여하기 위한 일련의 과정을 알고리즘으로 표현하면, 각 단계가 명확해야 하며 그 결과로 학생이 수업에 참여할 수 있어야 한다. 위 과정은 알고리즘의 조건을 간단히 설명하기 위한 예시이다.

---

자연어

자연어란 사람들이 일상생활에서 사용하는 언어를 의미한다.  자연어는 컴퓨터가 사용하는 프로그래밍 언어와는 구별되며, 사람이 사용하는 언어는 매우 유연하고 모호성이 있을 수 있지만, 프로그래밍 언어는 명확하고 구조화되어 있어야 한다.

자연어로 알고리즘을 표현하는 것은 매우 직관적일 수 있지만, 때로는 복잡하고 모호할 수 있다. 이는 자연어가 규칙적이지 않고 다양한 방식으로 해석될 수 있기 때문이다. 반면, 프로그래밍 언어는 명확한 규칙과 문법을 따르기 때문에 컴퓨터가 쉽게 이해할 수 있다. 따라서 자연어로 표현된 알고리즘을 컴퓨터가 이해할 수 있는 프로그래밍 언어로 변환하는 과정은 필수적이며, 이는 컴퓨터 과학의 중요한 과제 중 하나이다.

---

의사코드(Pseudo Code)

의사코드(Pseudo Code)는 알고리즘을 표현하는 방법 중 하나로, 실제 프로그래밍 언어는 아니지만 인간이 이해하기 쉬운 형식으로 알고리즘의 동작을 서술하는 방식이다.

• 의사: 실제 프로그래밍 언어와 비슷하지만 실제 코드가 아닌, 논리적 흐름을 표현하는 방식이다.
• 알고리즘 표현: 프로그래밍 언어를 사용하지 않고도 알고리즘의 동작을 설명할 수 있도록 유사한 문법을 사용해 알고리즘을 설명한다.  대신 유사한 문법을 가진 언어로 표현

---

순서도 (Flow Chart)

앞서 문제 해결을 위한 절차가 알고리즘이라고 이야기 한 것처럼 우리는 일상에서 일어나고 있는 것을 좀 더 명확하게 단계료 표현 할 수 있어야 합니다. 

순서도 (Flow Chart)는 문제 해결 과정이나 알고리즘의 전체 구조와 흐름을 명확하게 시각적으로 표현하는 도구이다.

이는 복잡한 논리적 절차와 흐름을 간단하고 명확하게 나타내며, 다음과 같은 특징을 가진다.

1. 전체 구조 파악:
   자연어로 설명하기 어려운 복잡한 절차나 흐름을 쉽게 이해할 수 있도록 도와준다. 각 단계를 도식화하여 문제 해결의 전반적인 흐름을 한눈에 파악할 수 있다.
2. 논리적 절차와 흐름:
   순서도는 각 단계가 어떻게 연결되어 있는지를 보여준다. 논리적 절차가 시각적으로 표현되기 때문에, 각 과정이 어떤 순서로 실행되는지 명확하게 알 수 있다.
3. 기호와 도형:
   순서도는 약속된 기호와 기하학적 도형을 사용하여 표현된다. 예를 들어, 타원은 시작과 끝을 나타내고, 사각형은 작업 단계를, 마름모는 조건문 또는 결정 지점을 의미한다. 화살표는 단계 간의 흐름을 나타낸다.
4. 문제 해결 과정 표현:
   순서도는 문제 해결의 각 단계를 시각적으로 나타내며, 프로그램이 어떤 절차로 문제를 해결할지 보여준다. 이 과정에서 각 처리 방법이 어떤 순서로 수행되는지 쉽게 파악할 수 있다.

순서도는 특히 복잡한 알고리즘이나 절차를 설명할 때 매우 유용하며, 문제를 단계별로 나눠서 이해할 수 있게 도와준다.

순서도의 대표적인 기호를 테이블로 정리하면 다음과 같다:

기호	설명	용도
라운드 사각형	시작 / 끝	알고리즘의 시작과 끝을 나타낸다.
사각형	처리 과정	입력된 값을 연산 처리 작업이나 실행할 명령을 나타낸다.
마름모	조건 / 결정	조건문이나 분기를 나타내며, 참/거짓의 결과에 따라 다른 경로로 흐른다.
화살표	흐름선	단계 간의 흐름을 나타낸다.
평행사변형	입력 / 출력	데이터를 입력하거나 출력을 나타낸다.
원통형	데이터 저장	데이터베이스나 저장소를 나타낸다.
원형	연결자 (온페이지/오프페이지 연결)	페이지 안팎의 흐름 연결을 나타낸다.

장점:

1. 시각적 이해 용이성:
   • 복잡한 알고리즘이나 절차를 시각적으로 표현하기 때문에, 전체 흐름을 한눈에 파악할 수 있다. 이는 이해하기 쉽고, 논리적인 절차를 간단하게 설명할 수 있도록 돕는다.
2. 문서화 및 커뮤니케이션 도구:
   • 순서도는 다양한 팀원들 간에 복잡한 절차를 설명하거나 문제 해결 과정을 공유하는 데 매우 유용한 도구이다. 특히 비전문가나 개발자 모두에게 전달하기 좋다.
3. 논리적 오류 확인 용이:
   • 순서도를 통해 알고리즘의 흐름을 시각화하면 논리적 오류나 잘못된 분기 등을 쉽게 파악할 수 있다.
4. 표준화된 기호 사용:
   • 순서도는 국제적으로 표준화된 기호를 사용하므로, 다른 사람들이 봐도 공통적으로 이해할 수 있다. 이를 통해 협업이 원활하게 이루어진다.

단점:

1. 복잡한 시스템에서는 어려움:
   • 복잡한 시스템이나 대규모 알고리즘을 순서도로 표현하려고 하면 너무 복잡해질 수 있다. 이 경우 도형과 흐름이 많아지면서 오히려 이해가 어려워질 수 있다.
2. 수정이 어려움:
   • 순서도를 수정하려면 도형과 연결선을 다시 그려야 하기 때문에, 자주 변경이 필요한 경우에는 비효율적일 수 있다. 이는 특히 복잡한 순서도일수록 더 큰 문제다.
3. 세부 사항 표현 제한:
   • 순서도는 전체 흐름을 시각적으로 표현하는 데는 탁월하지만, 세부적인 알고리즘 로직이나 코드 수준의 상세한 처리를 표현하는 데는 한계가 있다.
4. 자동화 도구 부족:
   • 1. 순서도 자체는 시각적인 도구일 뿐, 실제로 이를 바탕으로 코드를 자동으로 생성하거나 동작시킬 수 있는 기능은 부족하다. 이를 프로그래밍 언어로 변환하는 추가적인 작업이 필요하다

---

순서도 구조

순서도에서는 기본적으로 세 가지 주요 구조가 사용되는데, 이들은 순차 구조, 선택 구조, 그리고 반복 구조입니다. 이 구조들을 이해하고 적절히 활용함으로써, 어떠한 알고리즘도 표현할 수 있습니다.

1. 순차 구조 (Sequence Structure):

• 설명: 순차 구조는 모든 명령이 정해진 순서대로 차례차례 실행되는 구조이다. 한 단계가 끝나면 다음 단계로 넘어간다.
• 예시:
  1. 변수 초기화
  2. 값 계산
  3. 결과 출력
• 사용: 명령들이 순서대로 실행되어야 할 때 사용된다. 특별한 조건이나 반복 없이, 주어진 절차가 순차적으로 이루어질 때 적합하다.

2. 선택 구조 (Selection Structure):

• 설명: 선택 구조는 조건에 따라 다른 명령을 실행하는 구조로, "if-then-else"와 같은 구조로 많이 사용된다. 조건을 만족하면 특정 작업을 수행하고, 그렇지 않으면 다른 작업을 수행하는 방식이다.
• 예시:
  • 조건: 만약 학생의 성적이 90점 이상이면, 'A' 등급을 부여한다.
  • 조건 실패: 그렇지 않으면 'B' 등급을 부여한다.
• 사용: 조건에 따라 서로 다른 결과를 도출해야 할 때 사용된다. 예를 들어, 조건문을 통해 특정 상황에서만 실행되는 명령을 처리하고자 할 때 유용하다.

3. 반복 구조 (Iteration Structure):

• 설명: 반복 구조는 특정 조건이 만족되는 동안 같은 작업을 반복하는 구조이다. "while" 또는 "for" 루프가 이러한 구조를 나타낸다.
• 예시:
  • 배열의 모든 원소를 순차적으로 더해 합계를 계산한다.
• 사용: 동일한 명령을 여러 번 반복해서 실행해야 하는 경우, 예를 들어 데이터 집합을 순회하거나 특정 조건이 충족될 때까지 실행하는 작업에 적합하다.

각 구조의 기호:

1. 사각형 (Rectangle): 일반적인 처리 단계를 나타내며, 주로 순차 구조에서 사용된다.
2. 다이아몬드 (Diamond): 조건을 나타내며, 주로 선택 구조에서 사용된다. 조건이 참일 때와 거짓일 때 서로 다른 흐름을 나타낸다.
3. 화살표 (Arrow): 흐름의 방향을 나타내며, 모든 구조에서 사용된다. 각 단계 간의 흐름을 연결하여 알고리즘이 어떤 순서로 실행되는지 시각적으로 표현한다.

구조들의 조합과 중첩:

이들 세 가지 구조는 단독으로 사용되기도 하지만, 복잡한 알고리즘에서는 이들을 조합하고 중첩하여 사용한다. 예를 들어, 선택 구조 내에서 반복 구조가 사용되거나, 반복 구조 내에서 선택 구조가 나타날 수 있다. 이러한 방식으로 복잡한 알고리즘도 명확하게 표현할 수 있다.

---