5주차 - park-gyubi/Computer GitHub Wiki

알고리즘

• 정의: 문제를 해결하기 위해 정해진 순서대로 수행하는 명확한 절차
• 입력된 데이터를 처리하여 원하는 결과인 출력으로 변환하는 과정
• 컴퓨터 프로그램뿐만 아니라 일상생활에서도 알고리즘을 찾을 수 있음.

기본 흐름

• 입력 -> 처리 단계 -> 출력
• 입력: 문제 해결에 필요한 데이터
• 처리: 정해진 순서에 따라 수행하는 작업
• 출력: 처리 결과

알고리즘의 조건

• 각 단계가 명확해야 함.
• 실행 순서가 분명해야 함.
• 일정한 과정을 거쳐 결과를 얻을 수 있어야 함.

사례: 라면 끓이기

• 물 준비 -> 물 끓이기 -> 재료 넣기 -> 기다리기 -> 완성
• 요리 과정처럼 일상생활에서 순서대로 수행하는 절차도 알고리즘으로 볼 수 있음.

길 찾기 사례

• 출발지에서 목적지까지 이동할 때 여러 경로 중 적절한 경로를 선택
• 내비게이션은 거리, 시간 등의 정보를 이용하여 이동 경로를 계산함.
• 같은 문제라도 해결하는 방법과 알고리즘은 여러 가지가 존재할 수 있음.

주의

• 절차와 코드 프로그램은 같은 개념이 아님.
• 알고리즘은 문제를 해결하는 절차이고, 프로그램은 알고리즘을 컴퓨터가 실행할 수 있도록 구현한 것임.

---

좋은 알고리즘

• 단순히 답을 얻는 것뿐만 아니라 정확하고 효율적으로 문제를 해결할 수 있어야 함.

정확성

• 주어진 문제에 대해 올바른 결과를 만들어야 함.

명확성

• 각 단계와 명령의 의미가 분명해야 함.

유한성

• 일정한 단계를 수행한 후 반드시 종료되어야 함.

효율성

• 가능한 적은 시간과 자원을 사용하여 문제를 해결해야 함.

일반성

• 하나의 특정 상황에만 적용되는 것이 아니라 비슷한 유형의 여러 문제에도 적용할 수 있어야 함.

오해 바로잡기

• 절차가 있다고 해서 모두 좋은 알고리즘은 아님.
• 답이 맞더라도 지나치게 많은 시간이나 자원을 사용한다면 좋은 알고리즘이라고 보기 어려움.
• 복잡한 알고리즘이 항상 좋은 알고리즘인 것은 아님.

사례

• 같은 목적지까지 갈 수 있는 여러 길이 있다면 더 짧거나 빠른 경로를 선택하는 것이 효율적인 해결 방법이 될 수 있음.

---

문제를 해결하기 위해서는 문제를 입력, 처리, 출력의 구조로 나누어 생각할 수 있음.

입력

• 문제를 해결하기 위해 주어지는 데이터
• 예시: 숫자, 문자, 사용자 입력, 센서 값 등

처리

• 입력 데이터를 이용하여 결과를 만들어내는 과정
• 계산, 비교, 조건 판단, 반복 등의 작업이 포함됨.

출력

• 처리한 결과를 사용자에게 보여주는 단계
• 예시: 숫자, 표, 메시지, 경고 등

학생 계산기 사례

• 입력: 학생의 점수
• 처리: 합계, 평균 계산 및 조건에 따른 결과 판단
• 출력: 계산된 합계와 평균, 결과 표시

문제 해결 흐름

• 입력 -> 처리 -> 출력
• 복잡한 문제도 필요한 입력과 원하는 출력을 먼저 파악하면 처리 과정을 설계하기 쉬워짐.

---

순서도(Flowchart)

• 알고리즘의 처리 과정과 실행 순서를 정해진 기호를 이용하여 그림으로 표현한 것
• 복잡한 처리 과정을 한눈에 확인하는 데 유용함.

기본 도형

• 타원: 시작과 종료
• 사각형: 처리
• 마름모: 조건 판단
• 평행사변형: 입력과 출력
• 화살표: 처리 순서와 진행 방향

흐름

• 이전 단계 -> 현재 단계 -> 다음 단계
• 화살표를 이용하여 프로그램이 실행되는 순서를 표현함.

로그인 순서도 사례

• 로그인 정보 입력
• 아이디와 비밀번호가 맞는지 판단
• 조건이 참이면 로그인 성공
• 조건이 거짓이면 오류 또는 재입력
• 종료

점검 기준

• 모든 경로가 연결되어 있는가?
• 시작과 종료가 존재하는가?
• 조건에 따른 경로가 올바르게 나뉘어 있는가?

---

의사코드(Pseudocode)

• 프로그래밍 언어의 정확한 문법보다 알고리즘의 논리와 실행 순서를 중심으로 작성하는 표현 방법
• 자연어와 프로그래밍 언어의 중간 형태
• 실제 코드를 작성하기 전에 알고리즘의 흐름을 설계할 때 사용할 수 있음.

작성 규칙

• 한 줄에 하나의 동작을 작성
• 들여쓰기를 사용하여 구조를 구분
• 의미가 명확한 표현 사용
• 일정한 표현 방식을 사용

큰 수 찾기 사례

• 두 수 입력
• A와 B 비교
• 만약 A > B라면 A 출력
• 그렇지 않으면 B 출력

장점

• 특정 프로그래밍 언어의 문법을 몰라도 알고리즘을 표현할 수 있음.
• 코드 작성 전에 논리적인 오류를 확인하기 쉬움.
• 프로그램의 전체적인 처리 흐름을 파악하기 쉬움.

오해 바로잡기

• 의사코드는 실제 프로그램이 아니므로 컴퓨터가 직접 실행할 수 없음.
• 문법보다는 논리가 중요함.

---

순차 구조

• 명령을 위에서 아래로 정해진 순서에 따라 하나씩 실행하는 구조
• 가장 기본적인 알고리즘의 실행 구조

실행 과정

• 첫 번째 명령 -> 두 번째 명령 -> 세 번째 명령 -> ... -> 마지막 명령

의존 관계

• 앞 단계의 결과가 다음 단계의 입력으로 사용될 수 있음.
• 실행 순서를 변경하면 결과가 달라질 수 있으므로 순서가 중요함.

커피 주문 사례

• 메뉴 선택 -> 주문 -> 결제 -> 음료 준비 -> 음료 수령
• 각 단계가 순서대로 진행됨.

넓이 계산 사례

• 가로 입력
• 세로 입력
• 넓이 = 가로 × 세로
• 결과 출력

주의

• 순차 구조에서는 명령의 실행 순서를 정확하게 설계해야 함.

---

선택 구조

• 주어진 조건의 결과에 따라 서로 다른 명령을 실행하는 구조
• 조건이 참인지 거짓인지 판단하여 실행 경로를 선택함.

기본 흐름

• 조건 확인 -> 참/거짓 판단 -> 해당 경로 실행

세 가지 선택

• 단일 선택: 특정 조건을 만족할 때만 명령 실행
• 두 가지 선택: 조건의 참과 거짓에 따라 두 경로 중 하나 선택
• 여러 가지 선택: 여러 조건에 따라 여러 경로 중 하나 선택

회원 할인 사례

• 회원 여부 확인
• 회원이면 할인 가격 적용
• 회원이 아니면 일반 가격 적용

경계값 주의

• 조건을 작성할 때 <, >, <=, >= 등의 범위를 정확하게 설정해야 함.
• 예를 들어 20세 이상이라는 조건에서 20세가 포함되는지 확인해야 함.

주의

• 조건의 범위가 겹치거나 빠지는 값이 없도록 설계해야 함.

---

반복 구조

• 같은 작업을 여러 번 수행해야 할 때 일정한 조건에 따라 명령을 반복해서 실행하는 구조
• 동일한 명령을 계속 작성하지 않고 반복 구조를 사용하여 효율적으로 표현할 수 있음.

횟수 반복

• 반복 횟수가 미리 정해져 있는 경우
• 예시: 1부터 10까지 반복

조건 반복

• 특정 조건을 만족하는 동안 또는 특정 조건을 만족할 때까지 반복
• 반복 횟수가 미리 정해지지 않을 수도 있음.

반복 구조의 네 요소

• 초기값: 반복을 시작할 때의 값
• 반복 조건: 반복을 계속할지 결정하는 조건
• 실행 내용: 반복해서 수행할 명령
• 상태 변화: 반복할 때마다 값을 변화시키는 과정

주의

• 반복 조건이 항상 참이 되도록 작성하면 반복이 끝나지 않는 무한 반복이 발생할 수 있음.
• 반복 횟수와 종료 조건을 정확하게 설정해야 함.

---

변수

• 프로그램에서 값을 저장할 수 있는 공간
• 처리 과정에서 필요한 데이터를 저장하거나 변경하는 데 사용함.

대입

• 변수에 새로운 값을 저장하는 작업
• 기존 값이 존재한다면 새로운 값으로 변경됨.

예시

• 합계 = 합계 + 가격
• 기존 합계에 새로운 가격을 더한 결과를 다시 합계에 저장
• 따라서 같은 변수라도 프로그램이 실행되는 과정에서 값이 계속 달라질 수 있음.

장바구니 사례

• 초기 합계 = 0
• 상품 추가 -> 상품 가격을 합계에 더함.
• 다른 상품 추가 -> 변경된 합계에 다시 가격을 더함.
• 상품이 추가될 때마다 합계의 상태가 변화함.

주의사항

• 초기값을 정확하게 설정해야 함.
• 변수에 어떤 값이 저장되어 있는지 실행 과정에서 추적해야 함.

---

실행 추적

• 알고리즘을 실제로 실행하기 전에 각 단계가 어떻게 실행되고 변수의 값이 어떻게 변하는지 순서대로 확인하는 과정
• 논리적 오류를 발견하는 데 사용할 수 있음.

추적표

• 단계
• 입력
• 조건 결과
• 변수 값
• 출력

등을 기록하여 알고리즘의 실행 과정을 확인함.

시험 입력

• 정상적인 값
• 경계에 해당하는 값
• 예외적인 값

등을 넣어 결과를 확인함.

오류 바로잡기

• 예상한 결과와 실제 실행 결과를 비교
• 결과가 다르면 조건, 계산, 변수 변화 등의 과정을 다시 확인
• 문제의 원인을 찾은 후 알고리즘을 수정

주의

• 알고리즘이 한 가지 입력에서 정상적으로 동작한다고 해서 모든 입력에서 정상적으로 동작하는 것은 아님.
• 다양한 입력을 사용하여 검증해야 함.

---

문제 분해

• 복잡한 문제를 해결하기 쉬운 작은 문제들로 나누는 과정
• 큰 문제를 한 번에 해결하는 것보다 작은 단위로 나누면 해결 방법을 찾기 쉬움.

문제 해결 과정

• 문제 파악 -> 작은 문제로 분해 -> 각각 해결 -> 결과 결합

온라인 주문 사례

• 상품 찾기
• 상품 선택
• 결제
• 배송
• 각각의 작은 과정으로 나누어 전체 주문 문제를 해결할 수 있음.

패턴 찾기

• 여러 문제나 데이터에서 반복적으로 나타나는 공통된 특징이나 규칙을 찾는 과정
• 발견한 패턴을 이용하면 비슷한 문제를 더 쉽게 해결할 수 있음.

주의사항

• 문제를 지나치게 세부적으로 나누면 오히려 복잡해질 수 있음.
• 문제 해결에 적절한 크기로 분해해야 함.

---

추상화

• 문제를 해결하는 데 필요한 핵심 정보만 남기고 중요하지 않은 세부 사항을 제거하는 과정
• 복잡한 문제를 단순하게 표현하여 핵심에 집중할 수 있도록 함.

추상화 과정

• 목표 확인 -> 핵심 선택 -> 불필요한 정보 제거 -> 단순하게 표현

지하철 노선도 사례

• 실제 지형과 거리, 건물 등을 모두 표현하지 않음.
• 역과 노선, 환승 관계처럼 이동에 필요한 핵심 정보만 표현
• 실제 공간보다 단순하지만 목적에 필요한 정보는 유지함.

모델링

• 추상화한 정보를 이용하여 실제 문제나 시스템을 이해하기 쉬운 형태로 표현하는 과정

오해 바로잡기

• 추상화는 무조건 정보를 많이 제거하는 것이 아님.
• 문제 해결 목적에 필요한 핵심 정보를 선택하는 것이 중요함.

---

탐색 알고리즘

• 여러 데이터 중에서 원하는 데이터를 찾아내는 방법

순차 탐색

• 데이터의 처음부터 하나씩 차례대로 비교하여 원하는 값을 찾음.
• 구조가 단순하고 데이터가 정렬되어 있지 않아도 사용할 수 있음.
• 데이터가 많아지면 확인해야 하는 값도 많아질 수 있음.

이진 탐색

• 정렬된 데이터의 가운데 값을 확인하고 탐색 범위를 절반씩 줄여가며 원하는 값을 찾음.
• 많은 데이터에서 효율적으로 값을 찾을 수 있음.
• 데이터가 정렬되어 있어야 사용할 수 있음.

비교

• 순차 탐색: 처음부터 하나씩 확인
• 이진 탐색: 탐색 범위를 절반씩 감소
• 데이터의 상태와 크기에 따라 적절한 탐색 방법을 선택해야 함.

사례

• 1~1000 사이의 숫자를 찾을 때 중간값을 기준으로 범위를 절반씩 줄이면 빠르게 답을 찾을 수 있음.

---

정렬

• 데이터를 일정한 기준에 따라 순서대로 배치하는 작업
• 숫자 크기, 이름, 날짜 등 다양한 기준으로 정렬할 수 있음.

정렬 기준 사례

• 숫자: 작은 값 -> 큰 값
• 날짜: 과거 -> 최근
• 문자: 이름 순서

선택 정렬

• 정렬되지 않은 데이터에서 가장 작은 값 또는 가장 큰 값을 선택
• 선택한 값을 정해진 위치로 이동
• 남은 데이터에서 같은 과정을 반복

버블 정렬

• 서로 인접한 두 값을 비교
• 순서가 잘못되어 있으면 두 값의 위치를 교환
• 이 과정을 반복하여 데이터를 정렬

정렬 알고리즘 비교

• 같은 데이터를 정렬하더라도 알고리즘에 따라 비교 횟수와 교환 횟수가 달라질 수 있음.
• 데이터의 크기와 상태에 따라 알고리즘의 효율도 달라짐.

오해 바로잡기

• 모든 정렬 알고리즘의 성능이 같은 것은 아님.
• 결과가 같더라도 결과를 얻기 위해 필요한 과정과 비용은 다를 수 있음.

---

알고리즘의 효율

• 같은 문제를 해결하는 알고리즘이라도 필요한 시간과 자원의 양이 다를 수 있음.
• 데이터의 양이 증가할수록 알고리즘 사이의 성능 차이가 커질 수 있음.

평가 기준

• 정확성: 올바른 결과를 만드는가?
• 시간: 문제를 해결하는 데 얼마나 많은 시간이 필요한가?
• 메모리: 얼마나 많은 저장 공간을 사용하는가?
• 이해 가능성: 알고리즘을 이해하고 구현하기 쉬운가?
• 유지보수: 수정하거나 관리하기 쉬운가?

입력 크기

• 처리해야 하는 데이터가 증가하면 필요한 연산의 수도 증가할 수 있음.
• 작은 입력에서는 비슷해 보이는 두 알고리즘도 입력이 커지면 실행 시간에 큰 차이가 생길 수 있음.

검증 과정

• 여러 시험 데이터를 준비
• 알고리즘 실행
• 예상 결과와 실제 결과 비교
• 오류 확인 및 수정

최종 확인

• 결과가 정확한가?
• 다양한 입력에서도 정상적으로 동작하는가?
• 불필요한 작업이 지나치게 많지는 않은가?
• 문제의 목적에 적합한 알고리즘인가?

핵심

• 좋은 알고리즘은 단순히 정답을 출력하는 것에서 끝나지 않음.
• 정확한 결과를 만들면서 시간과 자원을 적절하게 사용하고, 다양한 입력에서도 올바르게 동작하는지 검증해야 함.

---

1. 자판기 구매를 입력, 처리, 출력으로 나누기

• 원하는 제품 버튼 누르기(입력) -> 자판기가 돈을 받는다.(처리) -> 제품이 나온다(출력)출력

2. 학교 가는 절차를 다섯 조건으로 평가하기

• 명확성 - 어떤 버스/ 지하철을 타고 얼마나 가는지 등 명확성이 떨어짐
• 유한성 - 유한한 단계 후 종류되므로 유한성이 있음
• 정확성 - 버스나 지하철의 노선, 하차 위치 등이 구체적으로 정해져 있지 않아 이 절차만으로 항상 학교에 정확히 도착한다고 보장하기 어렵다.
• 일반성 - 일반적으로 많은 학생들이 집에서 나와 대중교통을 타고 학교에 도착 할 수 있으므로 일반성은 높다
• 효율성 - 대중교통을 이용하는 것이 상황에 따라 가장 빠르거나 효율적인 방법이라고 할 수 없으며, 이동 경로나 소요 시간도 제시되지 않아 효율성이 높다고 판단하기 어렵다.

3. 택시 요금 계산기의 입력, 처리, 출력, 예외는?

• 입력 - 이동 거리, 할증 여부, 탑승 시간 등
• 처리 - 기본 요금, 거리 요금, 할증 적용 등 계산
• 출력 - 총 요금, 결제 안내, 성세 내역
• 예외 - 데이터 누락, 비정상적인 값, 시스템 오류

4. 20세 이상 판정 순서도를 그려보세요

5. 짝수 홀수 판정 의사코드 작성

• 숫자 입력 받기 -> 숫자를 2로 나누었을때 나누어떨어지는가? 예(짝수) 아니오(홀수) -> 판정 결과 출력

6. 직사각형 넓이 절차를 배열해보세요

• 입력 - 직사각형 가로, 세로 길이
• 처리(계산) - 직사각형 넓이 = 가로 * 세로
• 출력 -직사각형 넓이

7. 점수별 A,B,C 조건을 작성하기

• A: 80-100
• B: 60-79
• C: 40-59

8. 1부터 10까지 합의 반복 요소를 정하기

• 초기값: i=1
• 반복 조건: i<=10
• 실행 내용: 더하기
• 상태 변화: i+=1

9. 3000원 상품 두 개에서 합계 변화를 적어 보세요.

• 합계 0원 -> 합게 3000원 -> 합계 6000원

10. 반복 알고리즘의 변수 변화를 표로 적어 보세요.

11. 학교 축제를 네 하위 문제로 나누어보기

• 홍보 문제
• 축제 운행 시 안전 사고 문제
• 축제 장소
• 운영 비용

12. 처음 방문한 학생용 학교 지도에 남길 정보는?

• 정문
• 강의동
• 도서관
• 학생회관
• 각 위치를 어떻게 가는지 대략적 위치 정보

13. 1-100에서 73을 찾는 범위 변화를 말해 보세요.

• 1-100 가운데 50<73 -> 51-100 가운데 75 >73 -> 51-74 가운데 68<73 -> 69-74 가운데 71<73 -> 72-74 가운데 73 == 73

14. 5,2,4,1을 선택 정렬로 단계 별 정리해 보세요

• 초기 - 5 2 4 1 -> 최소 1
• 1단계 - 1 2 4 5 -> 최소 2
• 2단계 - 1 2 4 5 - > 최소 4
• 3단계 - 1 2 4 5 -> 최소 5

15. 제출자 검색의 두 방법을 시간, 준비, 비용으로 비교해 보세요

순차 탐색

• 최대 n번
• 거의 없다(정렬X)
• 한 번 검색할 때 적음

이진트리

• 최대 log2 n번
• 정렬 비용 발생
• 한 번 검색할 때는 큰지만, 반복 할수록 적어짐