컴퓨터개론 5주차 과제 - ehdaud/ec GitHub Wiki

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

컴퓨팅 사고력의 시작
컴퓨터 과학은 코딩에서 출발하는 것이 아니라, 일상의 문제를 논리적 절차로 나누어 보는 컴퓨팅 사고력에서 출발한다.
자판기 처리 과정 예시: 잔액 검증, 재고 확인, 거스름돈 계산 처리를 거쳐 선택한 음료수, 거스름돈, 영수증을 출력한다.

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

좋은 알고리즘의 5가지 핵심 요건

명확성: 모든 단계의 지시가 모호하지 않고 명확해야 한다. (예: '적당히 가열'은 모호하나 '중불에서 3분간 가열'은 명확함)
유한성: 유한한 단계를 거친 후 반드시 작업이 종료되어야 한다. 명확한 종료 조건 설정이 필수적이다.
정확성: 각 단계가 정확하게 수행되어 올바른 결과를 만들어내야 한다.
일반성: 특정 하나의 값뿐만 아니라 동일한 형태의 다양한 입력에 대해서도 폭넓게 적용 가능해야 한다.
효율성: 계산에 걸리는 시간(시간 효율성)과 사용되는 메모리 자원(공간 효율성)을 최대한 아껴 사용해야 한다.

오해 바로잡기
단순히 결과만 올바르게 나온다고 해서 좋은 알고리즘인 것은 아니다.
계산 시간이 너무 오래 걸리거나 자원을 불필요하게 많이 사용하는 경우, 예외 상황에서 튕기는 경우에는 좋은 알고리즘이라 볼 수 없으므로 효율성, 정확성, 일반성을 종합적으로 평가해야 한다.

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

입력, 처리, 출력 구조
입력(Input): 데이터의 종류(숫자, 문자, 논리 값 등), 데이터 형식(정수, 실수, 문자열, 날짜 등), 데이터 범위 및 제약 조건(최솟값, 최댓값 등)을 명확히 정의해야 한다.
처리(Processing): 연산, 비교, 조건 분기, 반복 등 문제를 해결하기 위한 논리적 과정이다.
출력(Output): 최종 데이터 값, 시각적 표시 형식(표, 목록 등), 오류 메시지 및 경고를 사용자에게 전달한다.
학점 계산기 적용 예시
입력: 과목명, 점수(0-100), 학점 수(1-3)
처리: 과목별 점수와 학점을 곱한 뒤 총합을 구하고, 총 학점의 합으로 나누어 가중평균(평점) 계산
출력: 산출된 평점 및 평가 기준표에 따른 최종 성적 등급 표시
예외 처리
비정상적인 입력 값(예: 음수 거리 입력 등)이나 데이터 누락 시 시스템이 멈추거나 튕기지 않도록 걸러내고 안내 메시지를 띄우는 예외 처리 로직이 반드시 포함되어야 한다.

1-4. 순서도로 알고리즘 표현하기

순서도의 기본 도형 4가지

타원: 알고리즘의 시작과 종료.
사각형: 값 계산, 데이터 변경 등 처리(연산 동작)
평행사변형: 키보드 입력, 화면 출력 등 입출력
마름모: 조건 비교 및 판단(참/거짓 조건 분기)

순서도 작성 및 점검 기준 3가지

모든 경로가 화살표로 연결되어 끊어진 부분이 없어야 한다.
마름모(판단)에서 갈라지는 화살표에 참과 거짓이 명확히 표시되어야 한다.
종료 원칙에 따라 반드시 종료 타원에 도달해야 한다.

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

의사 코드의 개념 및 목적
사람이 쓰는 일상 언어(자연어)에 프로그래밍의 핵심 구조(조건문, 반복문 등)를 섞어서 표현하는 양식이다.
특정 프로그래밍 언어의 문법에 종속되지 않고, 개발자 간 논리와 절차를 명확하게 소통하기 위한 설계도 역할을 한다.
의사 코드 작성 4대 원칙

한 줄에 한 동작만 작성한다.
들여쓰기를 통해 조건문/반복문 내부 블록의 논리적 포함 관계와 가동성을 높인다.
변수 이름을 보고 역할을 한눈에 파악할 수 있도록 작성한다.
핵심 제어 키워드 표현을 문서 전체에서 일관되게 사용한다.

주의 사항
단순한 감상문이나 모호한 메모가 아니며, 다른 개발자가 읽고 프로그래밍 언어로 1대 1 변환이 가능할 정도로 구체적이고 단계적인 절차가 담겨야 한다.

2-1. 순차 구조

순차 구조
명령어들이 위에서 아래로 작성된 순서대로 단 한 번씩 실행되는 가장 기본적이고 직관적인 구조다.
의존 관계
뒤 단계가 실행되기 위해 앞 단계의 데이터가 먼저 준비되어야 하는 관계를 의미한다. (예: 입력이 되지 않으면 계산할 수 없고, 계산 결과가 없으면 출력할 수 없음)
의존성이 있는 명령어의 순서가 바뀌면 치명적인 버그나 엉뚱한 결과가 발생하므로 순서적 사고가 중요하다. (단, 가로와 세로 길이를 각각 입력받는 순서처럼 의존 관계가 없는 단계끼리는 순서 변경이 가능함)

2-2. 선택 구조

선택 구조의 3가지 유형

단일 선택: 조건이 참일 때만 특정 명령을 수행하고 거짓이면 아무것도 하지 않고 통과함. (if)
양자택일: 참일 때와 거짓일 때 실행할 명령을 두 갈래 중 하나로 선택함. (if-else)
다중 선택: 여러 조건 중 하나를 선택함. (if-else if-else, switch-case)

경계값 설계 및 오류 방지
선택 구조에서 가장 많은 논리 오류(버그)가 발생하는 지점은 경계값 처리다.
조건 기호(이상, 이하, 초과, 미만)를 명확히 작성하여 구간의 '겹침'이나 '누락'이 발생하지 않도록 설계해야 한다. (예: 90점 이상, 80점 이상~90점 미만, 80점 미만으로 명확히 분리)

2-3. 반복 구조

반복 구조의 2가지 종류

횟수 반복: 30명의 출석부 출력처럼 반복 횟수가 명확히 정해져 있는 경우에 사용하며 주로 for문을 사용함.
조건 반복: 비밀번호 재시도처럼 특정 조건이 만족되는 동안 계속해서 반복하는 경우에 사용하며 주로 while문을 사용함.

반복문의 4대 필수 요소

초기값: 반복을 시작하기 전에 카운트 변수 등을 초기화 (예: i = 1)
반복 조건: 반복을 계속 유지할지 결정하는 조건 (예: i <= 10)
실행 내용: 반복할 때마다 실제 수행할 명령어
상태 변화: 반복이 진행됨에 따라 언젠가 조건이 거짓이 되어 탈출할 수 있도록 값을 변화 (예: i = i + 1)

주의해야 할 실수
상태 변화 작성을 누락하면 조건이 계속 참이 되어 무한 반복에 빠진다.
초기화 오류나 미만/이하 기호 오용 시 정해진 횟수보다 한 번 더 또는 한 번 덜 실행될 수 있다.

2-4. 변수와 상태 변화

변수와 대입 연산자
변수: 데이터를 저장하기 위해 이름을 붙여둔 메모리상의 저장 공간이다.
대입 연산자 (=): 수학의 '같다'라는 의미가 아니라, 오른쪽 연산 결과를 왼쪽 변수에 저장하여 값을 '갱신(업데이트)'하라는 명령이다. (예: 합계 = 합계 + 가격).
변수 사용 시 2가지 주의 사항

변수 초기화: 연산을 시작하기 전에 기본값(예: 0)을 반드시 설정해야 한다. 초기화를 하지 않으면 메모리에 남아 있던 이전 값이나 쓰레기 값이 연산에 포함되어 오류가 발생한다.
이름과 값의 구분: 데이터를 담는 상자(변수 이름)와 상자 안의 내용물(실제 데이터 값)을 혼동해서는 안 된다.

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

추적표
알고리즘 실행 전 논리적 오류를 손으로 검증하기 위해, 각 단계별 명령, 조건(참/거짓), 변수 값의 변화, 출력을 표로 기록하여 추적하는 기법이다.
3가지 시험 입력 구성

정상값: 무난하고 일반적인 입력 데이터
경계값: 루프가 한 번도 실행되지 않거나 경계에 위치한 데이터(오류가 가장 많이 발생하는 지점)
예외값: 마이너스 값이나 비정상적으로 큰 값 등 잘못된 데이터

주의 사항
단 하나의 입력값에 대해서만 정답이 나온다고 방심해서는 안 되며, 다양한 입력과 경계값, 예외 케이스를 폭넓게 검증해야 한다.

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

문제 분해와 분할 정복
복잡한 문제나 거대한 목표를 해결 가능한 작은 크기의 하위 문제들로 나누어 정의하는 과정이다.
하위 문제들을 독립적으로 해결한 뒤 합치는 '분할 정복' 방식을 취한다. (예: 쇼핑몰 시스템을 상품 찾기, 장바구니, 결제, 배송 확인 모듈로 분해)
단, 무조건 작게만 나누면 관리 비용이 커지므로 독립적으로 해결 가능한 적절한 단위로 나누어야 한다.
패턴 찾기
분해된 하위 문제들 간에 공통적으로 반복되는 구조나 공통 패턴(예: 동일한 데이터 조회 패턴)을 발견하는 과정이다.
공통 패턴을 만들어 두면 로직을 새로 만들 필요 없이 그대로 재사용할 수 있어 개발 생산성이 향상된다.

3-2. 추상화와 모델링

추상화
해결하려는 목적에 꼭 필요한 핵심 특징만 선택하고, 불필요한 세부 사항은 숨기거나 생략하는 과정이다. (예: 지하철 노선도는 실제 지형/건물을 생략하고 역 이름과 환승 연결 관계라는 핵심 정보만 남김)
모델링 5단계 순서

목적 설정: 무엇을 위한 모델인지 분명히 함.
변수 선택: 목적에 필요한 핵심 데이터/변수를 골라냄.
관계 정의: 선택한 변수들 간의 상호작용 및 연관 관계를 정의함.
가정 설정: 작동에 필요한 기본 조건과 제약 사항을 설정함.
검증: 만들어진 모델이 현실 문제를 올바르게 해결하는지 테스트함.

3-3. 탐색 알고리즘

순차 탐색과 이진 탐색의 비교
순차 탐색
데이터를 처음부터 하나씩 순서대로 비교하며 찾는 방식이다.
정렬되지 않은 데이터에 적합하며, 최악의 경우 데이터 개수($n$번)만큼 비교해야 한다.
이진 탐색
반드시 정렬된 데이터에서 중앙값을 기준으로 탐색 범위를 절반씩 줄여가며 찾는 방식이다.
최악의 경우에도 ($\log_2 n$번)만 비교하므로 데이터가 수만~수억 개로 커질 때 매우 고속으로 동작한다.

탐색 알고리즘 선택 기준
정렬 여부, 데이터 크기, 정렬에 드는 비용을 종합적으로 고려해야 한다.
데이터가 정렬되어 있지 않고 단 한 번만 찾거나 데이터 크기가 작다면 순차 탐색이 유리하다.
데이터가 이미 정렬되어 있거나 반복해서 계속 찾아야 하는 상황이라면 이진 탐색이 유리하다.

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

정렬의 기본 요소
정렬을 위해 키(숫자 크기, 알파벳, 가나다순, 날짜 등)와 정렬 방향(오름차순, 내림차순)을 명확히 지정해야 한다.
2가지 대표 정렬 알고리즘

선택 정렬: 데이터 중 가장 최솟값(오름차순 기준)을 찾아 맨 앞으로 보내고, 남은 값들 중 최솟값을 찾아 그다음으로 보내는 과정을 반복한다.

버블 정렬: 이웃한 두 개의 값을 비교하여 순서가 맞지 않으면 교환하는 과정을 반복하며, 한 회차가 끝날 때마다 가장 큰 값이 제일 뒤로 이동한다.

정렬 시 주의사항
동점(동일한 값) 처리 규칙, 대소문자/한글 유니코드 우선순위 규칙, 정렬 키와 방향을 명확하게 지정해야 한다.

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

알고리즘 우수성의 5가지 평가 기준

정확성: 올바른 입력에 대해 항상 정확한 결과를 출력함.
실행 시간: 계산 단계와 소요 시간이 적게 걸림.
메모리 자원: 램 자원을 알뜰하게 적게 사용함.
가독성(유용성): 코드가 직관적이어서 타인이 읽고 이해/수정하기 쉬움.
예외 처리: 비정상적인 입력에도 시스템이 다운되지 않고 안전하게 견딤.

시간 복잡도와 데이터 크기
데이터 양이 적을 때는 알고리즘 간 차이가 미미하지만, 데이터가 100만 개 이상으로 커지면 시간 복잡도 차이에 의해 성능 격차가 기하급수적으로 벌어진다. (예: 100만 개 데이터에서 순차 탐색은 100만 번, 이진 탐색은 약 20번 연산)
알고리즘 검증 5단계 프로세스

데이터 입력: 시험 데이터(정상값, 경계값, 예외값) 준비
기대 결과 정의: 이론상 나와야 하는 정답값을 미리 설정
실제 결과 확인: 알고리즘 실행 후 출력값 확인
원인 분석 및 코드 수정: 기대 결과와 다를 경우 버그 수정
재시험: 테스트 입력을 다시 넣어 문제가 완벽히 해결되었는지 검증