5주차 컴퓨터개론 과제 - yunseoooooo/-1- GitHub Wiki

1-2.

순서만 있으면 좋은 알고리즘일까?

좋은 알고리즘은 단순히 순서만 있는 것이 아니라 명확성, 유한성, 정확성, 일반성, 효율성의 다섯 가지 조건을 만족해야 한다. 각 단계가 명확하고 올바르게 실행되어야 하며, 다양한 입력에 적용할 수 있고 적절한 시간 안에 종료되어야 한다.

알고리즘의 다섯 가지 조건

명확성: 모든 단계가 명확하고 모호함이 없어야 한다.
유한성: 유한한 단계 후에 반드시 종료해야 한다.
정확성: 각 단계가 정확하게 수행되어 올바른 결과를 만들어야 한다.
일반성: 다양한 입력에 대해 적용할 수 있어야 한다.
효율성: 시간과 자원을 효과적으로 사용해야 한다.

질문: 학교 가는 절차를 다섯 조건으로 평가해 보세요.

| 조건 | 평가 |

| 명확성 | 일어나기, 씻기, 옷 입기, 가방 챙기기, 학교 가기 순서가 명확해야 한다. |

| 유한성 | 정해진 단계를 거쳐 학교에 도착하면 종료한다. |

| 정확성 | 준비물을 챙기고 올바른 경로로 이동하여 학교에 도착해야 한다. |

| 일반성 | 도보, 버스, 지하철 등 다양한 이동 방법에 적용할 수 있다. |

| 효율성 | 이동 시간과 교통수단을 고려하여 효율적으로 이동한다. |

정리: 좋은 알고리즘은 단순히 순서가 있는 것이 아니라 다섯 가지 조건을 만족해야 한다.

1-3.

복잡한 문제를 어떻게 구조화할까?

복잡한 문제를 입력, 처리, 출력, 예외로 나누어 구조화하면 해결 과정을 쉽게 이해할 수 있다. 입력은 필요한 데이터를 받고, 처리는 데이터를 계산하거나 비교하며, 출력은 결과를 보여준다. 예외는 잘못된 입력이나 예상하지 못한 상황을 처리하는 것이다.

입력-처리-출력(IPO)

입력: 데이터, 형식, 범위
처리: 계산, 비교, 조건, 반복
출력: 결과값, 표시 형식, 오류 메시지
예외: 잘못된 입력이나 예상하지 못한 상황을 처리하는 방법

질문: 택시 요금 계산기의 입력, 처리, 출력, 예외는?

| 구분 | 내용 |

| 입력 | 이동 거리, 기본요금, 추가 거리당 요금 |

| 처리 | 기본요금에 기본 거리 초과분의 추가 요금을 더한다. |

| 출력 | 최종 택시 요금을 원 단위로 표시한다. |

| 예외 | 거리가 음수이거나 숫자가 아닌 값이면 오류 메시지를 표시한다. |

정리: 문제를 입력, 처리, 출력, 예외로 나누면 해결 과정을 쉽게 이해할 수 있다.

1-4.

절차와 조건을 한눈에 보려면?

절차와 조건을 한눈에 보려면 순서도를 사용한다. 타원은 시작과 종료, 사각형은 처리, 평행사변형은 입출력, 마름모는 조건 판단을 나타내며, 화살표는 실행 방향을 표시한다. 순서도를 작성할 때는 모든 경로가 연결되어 있고 참과 거짓이 표시되어 있으며 종료 지점이 있는지 확인해야 한다.

순서도의 기본 기호

타원: 시작, 종료
사각형: 처리
평행사변형: 입출력
마름모: 판단
화살표: 실행 방향과 연결

순서도 점검 기준

모든 경로가 연결되어 있어야 한다.
조건 판단에는 참과 거짓이 표시되어야 한다.
종료 지점이 있어야 한다.

질문: 20세 이상 판정 순서도를 그려 보세요.


       (시작)

          |

    / 나이 입력 /

          |

    ◇ 나이 >= 20? ◇

       /       \

     참         거짓

     |            |

 / 성인 출력 / / 미성년자 출력 /

     |            |

     └─────┬──────┘

           |

         (종료)

정리: 순서도는 실행 과정과 조건에 따른 분기를 그림으로 표현하여 프로그램의 흐름을 쉽게 파악하게 한다.

1-5.

언어를 몰라도 정확히 적을 수 있을까?

프로그래밍 언어를 몰라도 의사코드를 사용하면 알고리즘을 정확하고 이해하기 쉽게 작성할 수 있다. 한 줄에 한 동작씩 작성하고, 들여쓰기를 활용하며, 의미 있는 변수 이름과 일관된 표현을 사용하면 된다.

의사코드 작성 규칙

한 줄 한 동작: 한 줄에는 하나의 작업만 작성한다.
들여쓰기: 조건에 따라 실행되는 부분을 구분한다.
의미 있는 변수: 변수 이름만 보고도 어떤 값인지 알 수 있게 작성한다.
일관된 표현: 같은 의미는 같은 표현으로 작성한다.

질문: 짝수, 홀수 판정 의사코드를 작성해 보세요.


시작

    정수 number 입력

    만약 number를 2로 나눈 나머지가 0이라면

        "짝수입니다" 출력

    아니면

        "홀수입니다" 출력

    끝만약

끝

정리: 의사코드는 특정 프로그래밍 언어의 문법을 몰라도 알고리즘의 실행 과정을 이해하기 쉽게 표현하는 방법이다.

2-1.

명령은 기본적으로 어떤 순서로 실행될까?

명령을 정해진 순서대로 하나씩 실행하는 구조이다.

커피 주문 사례: 메뉴 선택 → 수량 선택 → 금액 확인 → 결제 → 영수증 받기
넓이 계산: 가로 입력 → 세로 입력 → 넓이 계산 → 결과 출력

질문: 직사각형의 넓이 절차를 배열해 보세요.

가로 길이를 입력한다.
세로 길이를 입력한다.
가로와 세로를 곱하여 넓이를 계산한다.
계산한 넓이를 출력한다.

정리: 순차 구조는 명령을 정해진 순서대로 실행하는 기본적인 알고리즘 구조이다.

2-2.

조건에 따라 다른 행동을 하려면?

조건에 따라 다른 행동을 하려면 조건문을 사용하면 된다. 조건이 참인지 거짓인지 판단한 뒤, 결과에 따라 서로 다른 명령을 실행한다.

조건 구조의 종류

단일 선택: 조건이 참일 때만 특정 명령을 실행한다.
양자 택일: 두 가지 경로 중 하나를 선택한다.
다중 선택: 여러 조건에 따라 여러 경로 중 하나를 선택한다.

질문: 점수별 ABC 조건을 작성해 보세요.


점수 입력

만약 점수가 90점 이상이면

    "A" 출력

아니고 점수가 80점 이상이면

    "B" 출력

아니고 점수가 70점 이상이면

    "C" 출력

아니면

    "F" 출력

끝

정리: 조건 구조는 주어진 조건에 따라 서로 다른 명령을 실행할 수 있도록 한다.

2-3.

같은 일을 자동으로 여러 번 하려면?

같은 일을 자동으로 여러 번 하려면 반복문을 사용하면 된다. 반복문은 정해진 횟수만큼 실행하거나 특정 조건이 만족될 때까지 같은 명령을 반복한다. 예를 들어 1부터 10까지의 숫자를 차례대로 출력할 때 반복문을 사용할 수 있다.

반복 구조의 종류

횟수 반복: 정해진 횟수만큼 반복한다.
조건 반복: 조건이 참인 동안 반복한다.

반복의 네 가지 요소

초기값: 반복을 시작하기 전에 처음 값을 설정한다.
반복조건: 반복을 계속할지 결정하는 조건이다.
실행내용: 반복할 때마다 수행하는 작업이다.
상태변화: 반복이 끝날 수 있도록 값을 변화시킨다.

주의할 점

조건이 항상 참이면 반복이 끝나지 않을 수 있다.
조건이나 상태변화가 잘못되면 반복 횟수가 한 번 많거나 적어질 수 있다.

질문: 1부터 10까지 합의 반복 요소를 정해 보세요.

초기값: 숫자 = 1, 합계 = 0
반복조건: 숫자가 10 이하인 동안
실행내용: 합계에 숫자를 더한다.
상태변화: 숫자를 1 증가시킨다.


숫자 = 1

합계 = 0

숫자가 10 이하인 동안 반복

    합계 = 합계 + 숫자

    숫자 = 숫자 + 1

끝반복

합계 출력

결과: 55

정리: 반복 구조를 사용할 때는 초기값, 반복조건, 실행내용, 상태변화를 정확하게 설정해야 한다.

2-4.

계산 중간값은 어디에 기억할까?

계산 중간값은 변수에 저장한다. 변수는 데이터를 임시로 기억하는 공간으로, 계산 결과를 저장했다가 다음 계산에 다시 사용할 수 있다.

변수와 대입

변수: 이름을 붙인 저장 공간으로, 데이터를 저장한다.
대입: 변수에 값을 저장하거나 새로운 값으로 변경하는 것이다.

예를 들어 합계 = 합계 + 가격은 기존 합계에 가격을 더한 뒤 새로운 합계로 저장한다.

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

| 단계 | 명령 | 합계 |

| 1 | 합계 = 0 | 0원 |

| 2 | 합계 = 합계 + 3000 | 3,000원 |

| 3 | 합계 = 합계 + 3000 | 6,000원 |

최종 합계: 6,000원

정리: 변수는 계산 중간값을 저장하며, 대입을 통해 값을 계속 변경할 수 있다.

2-5.

실행 전에 논리 오류를 어떻게 찾을까?

실행 전에 논리 오류를 찾으려면 손으로 직접 실행 과정을 따라가며 확인하면 된다. 입력값을 넣고 각 명령이 순서대로 실행될 때 변수의 값이 어떻게 바뀌는지 확인한다. 이를 추적표로 정리하면 계산 과정이나 조건 판단에서 잘못된 부분을 찾을 수 있다.

추적표

추적표는 알고리즘을 단계별로 실행한다고 가정하고 변수의 변화와 출력 결과를 기록하는 표이다.

단계: 실행 순서
명령: 해당 단계에서 수행하는 작업
조건: 반복이나 선택에서 확인하는 조건
변수값: 실행 후 변수에 저장된 값
출력: 화면에 표시되는 결과

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

1부터 3까지 숫자를 더하는 알고리즘을 예시로 작성한다.


숫자 = 1

합계 = 0

숫자가 3 이하인 동안 반복

    합계 = 합계 + 숫자

    숫자 = 숫자 + 1

끝반복

합계 출력

| 단계 | 명령 | 조건 | 숫자 | 합계 | 출력 |

| 1 | 초기값 설정 | - | 1 | 0 | - |

| 2 | 합계에 숫자 더하기 | 참 (1 ≤ 3) | 1 | 1 | - |

| 3 | 숫자 1 증가 | - | 2 | 1 | - |

| 4 | 합계에 숫자 더하기 | 참 (2 ≤ 3) | 2 | 3 | - |

| 5 | 숫자 1 증가 | - | 3 | 3 | - |

| 6 | 합계에 숫자 더하기 | 참 (3 ≤ 3) | 3 | 6 | - |

| 7 | 숫자 1 증가 | - | 4 | 6 | - |

| 8 | 반복 종료 | 거짓 (4 ≤ 3) | 4 | 6 | - |

| 9 | 합계 출력 | - | 4 | 6 | 6 |

정리: 추적표를 사용하면 실행 전에 변수의 변화와 출력 결과를 확인하여 논리 오류를 찾을 수 있다.

3-1.

큰 문제를 어떻게 작게 나눌까?

큰 문제를 작게 나누려면 분해(문제 분해) 를 활용하면 된다. 복잡한 문제를 여러 개의 작은 문제로 나누고, 각 문제를 해결한 뒤 결과를 합쳐 전체 문제를 해결한다.

문제 분해

문제 분해는 큰 목표를 해결하기 쉬운 여러 하위 문제로 나누는 것이다.

온라인 주문 사례: 상품 찾기 → 장바구니 → 결제 → 배송 확인
패턴 찾기: 반복되는 입력, 처리, 출력을 찾아 재사용한다.

주의 사항

무조건 작게 나누는 것이 아니라 해결에 적절한 크기로 나눈다.
각 하위 문제의 역할과 연결 관계를 명확하게 정한다.

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

축제 기획: 축제 주제와 일정, 예산을 정한다.
부스 준비: 부스 종류를 정하고 필요한 물품을 준비한다.
행사 운영: 공연과 체험 활동을 진행하고 안전을 관리한다.
마무리: 쓰레기를 정리하고 물품을 반납하며 만족도를 조사한다.

정리: 큰 문제를 하위 문제로 나누면 각 단계의 역할이 명확해지고 효율적으로 해결할 수 있다.

3-2.

무엇을 남기고 무엇을 생략할까?

문제를 쉽게 이해하고 해결하려면 추상화를 활용하면 된다. 문제 해결에 필요한 핵심 정보는 남기고, 중요하지 않은 세부 정보는 생략한다.

추상화

추상화는 문제의 목적에 중요한 특징을 선택하고 불필요한 세부 정보를 생략하는 것이다.

모델링 순서

목적: 무엇을 해결할지 정한다.
변수 선택: 필요한 정보를 선택한다.
관계: 정보 사이의 관계를 정한다.
가정: 문제 해결에 필요한 조건을 정한다.
검증: 모델이 목적에 맞는지 확인한다.

주의: 추상화는 정보를 무조건 생략하는 것이 아니라 목적에 따라 필요한 정보를 선택하는 것이다.

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

남길 정보: 건물 이름, 강의실 위치, 도서관, 학생식당, 화장실, 정문과 출입구, 이동 경로
생략할 정보: 건물 내부의 모든 책상 위치, 장식물, 수업과 관계없는 세부 시설 정보

정리: 학교를 처음 방문한 학생이 목적지를 쉽게 찾는 데 필요한 정보를 중심으로 지도를 구성한다.

3-3.

원하는 항목을 더 빠르게 찾으려면?

원하는 항목을 더 빠르게 찾으려면 탐색 알고리즘을 활용하면 된다. 항목을 하나씩 확인하는 순차 탐색이나, 정렬된 자료를 반씩 나누어 찾는 이진 탐색을 사용할 수 있다. 자료가 정렬되어 있다면 이진 탐색이 더 빠르게 찾을 수 있다.

탐색 방법

순차 탐색: 목록의 처음부터 하나씩 비교한다. 정렬되지 않은 목록에서도 사용할 수 있다.
이진 탐색: 정렬된 목록의 가운데 값을 비교하고 탐색 범위를 절반씩 줄인다. 반드시 정렬된 목록에서 사용해야 한다.

탐색 사례

책상 위에 섞여 있는 서류 찾기: 순차 탐색
이름순으로 정렬된 전화번호부에서 이름 찾기: 이진 탐색

탐색 방법 선택 기준

목록이 정렬되어 있는지 확인한다.
목록의 크기를 고려한다.
정렬하는 데 드는 준비 비용을 고려한다.

질문: 1~100에서 73을 찾는 범위 변화를 말해 보세요.

이진 탐색을 사용하면 다음과 같이 범위가 줄어든다.

1-100에서 가운데 값 50을 확인한다. 73은 더 크므로 51-100을 탐색한다.
51-100에서 가운데 값 75를 확인한다. 73은 더 작으므로 51-74를 탐색한다.
51-74에서 가운데 값 62를 확인한다. 73은 더 크므로 63-74를 탐색한다.
63-74에서 가운데 값 68을 확인한다. 73은 더 크므로 69-74를 탐색한다.
69-74에서 가운데 값 71을 확인한다. 73은 더 크므로 72-74를 탐색한다.
72-74에서 가운데 값 73을 확인한다. 찾았다!

정리: 이진 탐색은 정렬된 목록에서 탐색 범위를 절반씩 줄여 빠르게 값을 찾을 수 있다.

3-4.

순서를 바꾸면 왜 찾기 쉬울까?

자료를 일정한 기준에 따라 정렬하면 원하는 항목을 더 쉽게 찾을 수 있다. 특히 숫자를 작은 순서나 큰 순서로 정렬하면 탐색 범위를 빠르게 줄일 수 있어 검색 시간을 줄일 수 있다.

정렬 기준

숫자: 점수, 가격 등
문자: 이름, 제목 등
날짜: 오래된 순서 또는 최신 순서
오름차순: 작은 값에서 큰 값으로 정렬
내림차순: 큰 값에서 작은 값으로 정렬

정렬 알고리즘

선택 정렬: 남은 값 중 최솟값을 선택하여 앞쪽으로 이동한다.
버블 정렬: 이웃한 두 값을 비교하고 순서가 잘못되었으면 교환한다.

주의 사항

값이 같은 경우의 처리 기준을 정한다.
한글과 영어 대소문자 등 문자 정렬 규칙을 명확하게 정한다.
어떤 기준으로 정렬하는지 미리 정한다.

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

처음 배열: [5, 2, 4, 1]

1단계: 남은 값 중 최솟값 1을 선택하여 맨 앞으로 이동한다.

[1, 2, 4, 5]
2단계: 남은 값 [2, 4, 5] 중 최솟값 2를 선택한다. 이미 올바른 위치에 있으므로 그대로 둔다.

[1, 2, 4, 5]
3단계: 남은 값 [4, 5] 중 최솟값 4를 선택한다. 이미 올바른 위치에 있으므로 그대로 둔다.

[1, 2, 4, 5]

최종 결과: [1, 2, 4, 5]

정리: 선택 정렬은 정렬되지 않은 부분에서 최솟값을 찾아 앞에서부터 차례대로 배치하는 방법이다.

3-5.

두 방법 중 어느 것이 더 좋을까?

순차 탐색은 자료를 처음부터 하나씩 확인하는 방법으로, 정렬되지 않은 자료에서도 사용할 수 있다. 이진 탐색은 정렬된 자료를 반씩 나누어 찾는 방법으로, 더 빠르게 검색할 수 있다. 따라서 정렬되지 않은 자료는 순차 탐색, 정렬된 자료에서 빠르게 찾으려면 이진 탐색이 더 좋다.

알고리즘 평가 기준

정확성: 올바른 결과를 만드는가?
실행 시간: 결과를 얻는 데 얼마나 걸리는가?
메모리: 얼마나 많은 저장 공간을 사용하는가?
이해 및 유지보수: 알고리즘을 이해하고 수정하기 쉬운가?
예외 처리: 잘못된 입력이나 예외 상황을 처리할 수 있는가?

탐색 방법 비교

순차 탐색: 처음부터 하나씩 비교하며, 최악의 경우 N번 비교한다.
이진 탐색: 정렬된 목록에서 범위를 절반씩 줄이며, 최악의 경우 약 log₂N번 비교한다.

질문: 제출자 검색의 두 방법을 시간과 준비 비용으로 비교해 보세요.

학생들의 제출자 명단에서 특정 학생을 찾는다고 가정한다.

| 평가 기준 | 순차 탐색 | 이진 탐색 |

|---|---|---|

| 시간복잡도 | O(N) | O(log N) |

| 준비 비용 | 정렬할 필요가 없어 낮다. | 이름순 등으로 정렬해야 하므로 추가 비용이 든다. |

| 전체 비용 | 검색할 때마다 목록을 처음부터 확인할 수 있다. | 정렬 비용이 들지만 반복 검색할수록 유리하다. |

검증 과정

테스트 입력을 준비한다.
예상 결과를 정한다.
실제 실행 결과를 확인한다.
예상과 다르면 원인을 찾아 수정한다.
다시 테스트하여 문제가 해결되었는지 확인한다.

정리: 검색을 한 번만 하고 목록이 정렬되어 있지 않다면 순차 탐색이 간단하다. 반면 정렬된 명단에서 여러 번 검색한다면 이진 탐색이 시간 면에서 유리하다.

문장 다듬기, 이미지제작에 CHAT GPT를 사용하였습니다.