컴퓨터개론 5주차 - yulha1128000-cyber/qqwi GitHub Wiki

1-1. 알고리즘이란 무엇인가

알고리즘

정의: 문제 해결을 위한 유한하고 명확한 절차
흐름: 입력(정보, 데이터)-> 처리(입력 기반 해결)-> 출력(결과)

알고리즘 vs 프로그램

알고리즘: 절차적 흐름에 따라 처리
프로그램: 설계된 명령에 따라 구현

`Q. 자판기 구매를 입력, 처리, 출력으로 나누면?

A: 입력: 돈 넣고 음료수 고르기, 처리: 넣은 금액을 확인하고 음료수 재고 확인, 출력: 음료수`

1-2. 좋은 알고리즘의 조건

좋은 알고리즘의 다섯 조건

명확성: 모든 단계의 지시가 모호하지 않고 명확해야 함
유한성: 유한한 수의 단계 후에 반드시 작업이 종료되어야 함
정확성: 단계가 수행되어 올바를 결과를 도출해야 함
일반성: 다양한 입력에 적용 가능해야 함
효율성: 시간과 자연을 효율적으로 사용해야 함

모호한 지시 vs 명확한 지시

모호한 지시: 적당한 이라는 표현을 사람마다 기준이 다르고 모호함
명확한 지시: 정확한 지시는 지시가 명확해 올바르게 수행 가능

즉, 컴퓨터가 오해하지 않게 명확하게 하는 것이 중요 3. 종료 확인

유한 단계: 단계를 거치며 올바른 알고리즘
무한 반복: 명확한 종료 조건이 없어 무한 반복

유한성을 확보하는 것이 중요 4. 좋은 알고리즘?

적절한 시간에 완료됌
자원을 효율적으로 사용함
예외 상황에서도 올바르게 처리함

`Q. 학교 가는 절차를 다섯 조건으로 평가해 보세요

A. 명확성: 학교 가는 단계가 구체적으로 정해져 있어야 함, 유한성: 학교 도착 후 종료, 정확성: 정해진 절차에 따라 학교 도착, 일반성: 출발 장소나 교통 수다닝 달라져도 적용 가능, 효율성: 시간, 비용에 맞게 선택`

1-3. 입력, 처리, 출력으로 문제 보기

입력

모든 문제 해결의 출발점
데이터 종류: 숫자, 문자, 논리값 등
데이터 형식: 정수, 실수 등
데이터 범위: 최솟값, 제약 조건 등

처리

문제를 해결하기 위한 논리적 과정
과정: 계산-> 비교-> 조건-> 반복

출력

사용자에게 최종 결과물 저장
결과 값: 최종 값
표시 형식: 표, 목록, 그래프
오류 메시지: 잘못된 입력, 경고

사례

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

A. 입력: 탑승 거리, 탑승 시간, 추가 요금 등 / 처리: 기본, 거리, 시간 요금 계산 / 출력: 총 요금, 상세 내역 / 예외: 비정상적인 값, 시스템 오류`

1-4. 순서도(프로 차트)로 알고리즘 표현하기

기본 도형

타원: 시작, 종료
사각형: 데이터 변경, 처리, 연산 동작
평행사변형: 입출력
마름모: 조건을 비교해 참과 거짓 판단

화살표

이전 단계----> 다음 단계 (실행 방향)

로그인 순서도

한 눈에 시스템 파악 가능
점검 기준: 모든 경로 연결 여부, 참과 거짓 표시 여부, 종료 존재 여부

`Q. 20세 이상 순서도를 그려보세요

1-5. 의사코드로 알고리즘 표현하기

의사 코드

알고리즘을 표현하기 위해 만들어짐
프로그램의 논리적 구조를 직관적으로 텍스트로 설계
일상어: 자연어 + 프로그래밍 구조
논리와 절차를 정확하게 표현

작성 원칙

한 줄에 한 동작: 가독성 향상
들여쓰기: 가독성 향상
의미 있는 변수: 이름 설정
일관된 표현
구체적 절차가 중요

큰 수 찾기

`Q. 짝수, 홀수 판정 의사코드를 작성해 보세요

2-1. 순차 구조

순차 구조: 한 단계 씩 실행
의존 관계

입력-> 계산-> 출력
단계별로 순서대로 진행하는 것이 중요

넓이 계산

가로 입력-> 세로 입력-> 넓이(가로x세로) 계산-> 출력
계산: 가로와 세로 값이 입력되지 않은 상태에서 계산 수행은 불가능

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

A. 입력(가로, 세로 값)-> 넓이 계산(가로X세로)-> 값 출력`

2-2. 선택 구조

참과 거짓: 조건식이 주어질 때 참 또는 거짓으로 평가
3가지 선택

단일 선택: 참-특정 명령 수행, 거짓-아무것도 하지 않고 지나감
양자택일: 참과 거짓 중 하나 선택
다중 선택: 조건이 여러 개 일 때 하나만 선택

경계값

논리 오류: 부등호(<,> 등) 잘못 작성 시 값ㅇ이 어느 공간에도 포함되지 않거나 두 공간에 같이 곂쳐버리는 곂침 발생
기호를 명확하게 해주는 것이 중요

`Q. 점수별 A, B, C 조건을 작성해 보세요.

A. 등급A: >=90(90이상), 등급B: 80=< and <90(80이상 90미만), 등급C: <80(80미만)`

2-3. 반복 구조

횟수 반복

반복 횟수가 명확하게 정해진 경우 사용
횟수 카운트 후 목표에 도달했을 때 종료

조건 반복

맞을 때까지 반복
시도 횟수 제한 가능

반복문이 오류 없이 진행되도록 하기 위한 4가지 필수 요소

초기값: 반복 시작 전 초기화
반복 조건: 반복 유지 여부
실행 내용: 반복할 때 필요한 명령문
상태 변화: 조건이 언젠가 거짓이 되도록 변화시킴

반복문 오류 주의

무한 반복: 조건이 항상 참이면 멈추지 않아 시스템 과부하
한 번 더 또는 덜 실행: 데이터 결과가 좋지 않음

`Q. 1부터 10까지 합의 반복 요소를 설정해 보세요.

2-4. 변수와 상태 변화

변수: 데이터를 저장하기 위해 이름을 붙여둔 메모리 속의 저장 공간
대입

새로운 값으로 갱신
시간이 흐르고 명령이 실행됨에 따라 상태값이 변화

주의 사항

초기화: 초기화 하지 않으면 메모리 안에 남아있던 이전의 변수 값이 포함되어 계산이 부정확해질 위험
변수 이름=값(x): 이름과 내용물 혼동x

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

A. 초기= 0원-> 상품 1개= 3000원-> 상품 2개-> 6000원`

2-5. 알고리즘 실행 추적

추적표

단계, 명령, 조건, 변수 값, 출력을 표로 검증하는 방법

1부터 3까지의 합

변수 값의 변화를 표로 기록해 검증

시험 입력

정상값: 일반적인 값을 입력하고 올바를 결과가 도출되는지 확인
경계값: 경계값이 문제가 있는지 확인
예외값: 잘못된 입력 확인

다양한 입력을 통해 오류 발생 확인 4. 하나의 입력 성공=x

다양한 입력을 넣고 테스트 해야 함
여러 번 검증 필요

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

3-1. 문제 분해와 패턴 찾기

문제 분해

복잡한 문제를 해결 가능한 작은 문제(하위 문제)로 나누어서 처리
하위 문제들을 개별적으로 해결하고 합침
이때 하위문제들은 독립적으로 기능을 개발하고 전체 시스템 구축 발달에 이바지 가능

패턴 찾기

입력-> 처리-> 출력
다른 문제 해결 때 재사용 가능-> 개발 생산성 향상

문제 분해 최대한 작게x

무조건 작게 하면 에너지 사용량 증가 위험
독립적으로 해결 가능한 적절한 단위로 나누어야 함

`Q. 학교 축제를 네 하위 문제로 나누어 보세요.

A. 장소 준비, 프로그램 기획, 홍보와 참가신청, 예산과 물품관리 `

3-2. 추상화와 모델링

추상화

목적에 필요한 핵심 특징만 선택
불필요한 세부 사항은 숨김
복잡성은 줄이고 본질을 남김

모델링 순서: 목적 설정-> 변수 선택(문제해결에 필요한 핵심 데이터)-> 관계(선택한 변수들 간에 상호작용과 연관 관계)-> 가정(시스템 작동에 필요한 기본 조건과 제약 상황)-> 검증(만들어진 모델이 올바르게 해결하는지)
지하철 노선도

세부 정보는 과감히 삭제하여 핵심 특징만 남김(추상화)`` 4. 추상화는 대충 생략?x

목적에 따라서 필요한 정보만 선택하는 고도의 논리적인 행위

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

A. 건물들의 위치와 명칭, 길 안내 동선, 정문 입구 등`

3-3. 탐색 알고리즘

순차 탐색

정렬되지 않은 목록에서도 동작
앞에서 부터 순서대로 동작
원하는 값이 가장 앞에 있는 경우 빠르게 찾기 가능\

이진 탐색

정렬된 목록에서만 동작
정렬된 범위의 가운데를 비교하여 범위가 절반

선택 기준

정렬 여부: 정렬x(이진 탐색), 정렬o(순차 탐색)
목록 크기: 목록이 큼(이진 탐색 효과 큼)
정렬 준비 비용: 정렬 준비 시 시간이 듦

3-4. 정렬 알고리즘과 비교

정렬 기준

선택 정렬: 값들 중 최소 값을 가장 앞으로 보내고 나머지 값들 중 가장 최소 값을 앞으로 보내는 과정 반복
버블 정렬: 이웃 값을 비교해서 정렬 완료될 때까지 계속 반복
주의 사항

동점 처리 여부
비교 규칙 설정
정렬 기준 명확히 기록

`Q. 5,2,4,1을 선택 정렬로 단계별 정리해 보세여.

A. 초기- 5 2 4 1 1단계- 1 2 4 5 2단계- 1 2 4 5 3단계- 1 2 4 5`

3-5. 알고리즘의 효율과 검증

평가 기준: 정확성, 실행 시간(시간 단축), 메모리(사용량이 적은지), 이해와 유지 보수(복잡한지), 예외 처리(안전하게 처리 하는지)
입력 크기

큰 데이터: 순차탐색- 100만번 연산, 이진탐색- 순차탐색보다 적은 계산

검증 과정: 테스트 입력-> 기대 결과-> 실제 결과-> 원인 수정-> 재시험

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

A. `