1. 알고리즘

알고리즘 개요

: 경우에 따라 시간과 공간에 얼마나 효율적인지 파악하여 적절한 알고리즘을 생각해 구현하자!!

---

0.Computational Thinking이란?

Computational Thinking은 4가지로 되어 있습니다.

• 분해: 복잡한 문제를 작은 문제로 나눕니다.
• 패턴 인식: 문제 안에서 유사성을 발견합니다.
• 추상화: 문제의 핵심에만 집중하고, 부차적인 것은 제외합니다.
• 알고리즘: 이렇게 정의한 문제를 해결하는 절차입니다(일반화와 모델링은 여기에 포함됩니다). 복잡한 문제를 해결하는 것은 어렵지만, 작은 문제를 해결하는 것은 비교적 쉽습니다. 작은 문제를 해결하다 보면 복잡한 문제를 해결하게 됩니다. 컴퓨터 공학에서 배우는 알고리즘은 대부분 정형화된 문제에 대해 검증된 해법을 제시하는 과목입니다.

현실에서 컴퓨터로 해결하려는 문제는 정형화된 문제가 아니라 비정형화된 문제가 더 많습니다. 그래서 비정형화된 문제를 컴퓨터로 해결하는 과정, 즉, 문제를 이해하고 분해, 패턴 인식, 추상화, 알고리즘 작성까지를 Computational Thinking이라고 합니다.

---

1.알고리즘이란?

Why We Study Algorithm?

어떤 방법이 효율적이고, 어느 경우가 효율적인지를 고려하여 적은 공간을 이용하여 빠른 시간 안에 빠른 속도로 수행되는 프로그램을 구현하기 위해

• 정의 : 문제가 있을 때, 문제 해결을 위한 동작의 방법들의 모임

---

2.성능 평가

: 우리는 최악의 상황을 고려하기 위하여 Big-O 표기법을 사용

(파이썬 기준으로 2000만번 연산할 때 1초라고 가정하고 생각하기)

---

2-1.시간 복잡도 (Time Complexity)

: 입력 값과 문제를 해결하는데 걸리는 시간의 상관 관계 (입력 값에 비례하여 연산 시간이 얼마나 변화하는지 파악)

---

2-2.공간복잡도 (Space Complexity)

: 입력값과 문제를 해결하는데 필요한 공간과의 상관관계 (저장하는 데이터가 1개의 공간을 차지한다고 생각)

---

2-3.점근 표기법

: 알고리즘의 성능을 수학적으로 표기하여 효율성을 평가하는 지표 (입력 값의 분포에 따라 소요된 연산량, 소요시간, 저장공간이 변할 수 있다)

• 빅오(Big-O) 표기법 : 최악의 성능일 때를 고려하여 표기 ex) O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)
• 빅오메가(Big-Ω) 표기법 : 최상의 성능일 때를 고려하여 표기 ex) Ω(1)

---

3. 알고리즘 설계 기법

1. 탐욕적 알고리즘 (Greedy Algorithm) : 분기마다 가장 최적의 해를 선택하여 결과를 도출 (항상 종합적인 최적의 해를 보장하지는 못 함)
2. 분할정복법 (Divide and Conquer) ex)퀵정렬 : 크고 방대한 문제를 효율적으로 풀 수 있는 단위로 작게 나눠 계산한 뒤 다시 합치는 방식(Top-down)
3. 재귀적 알고리즘 (Recusion Algorithm) ex)DFS : 풀이 도중 같은 풀이를 다시 불러오는 과정의 반복
4. 퇴각 검색법 (Backtracking) ex) DFS : 분기구조(tree) 탐색에서 탐색이 실패한 경우, 새로운 탐색이 가능한 가능한 분기까지 탐색 과정을 되돌려 진행하는 방식 (Depth First Searchj)
5. 동적계획법 (Dynamic Programming) : 어떤 문제를 해결하기 위해 그 문제를 작은 문제의 연장선으로 생각혀, 최선의 해를 활용
6. 근사 알고리즘 (Approximation Algorithm) : 최적 해를 구할 수는 없지만 비교적 빠른 시간합치는 방식(Top-Down)

---

---

프로그래밍 언어

---

개념

1. 자연어 : 사람들이 일상적으로 사용하는 언어, 앞뒤 문맥 상황, 경험을 토대로 의미 이해, 모호성 부정확성으로 컴퓨터에 전달이 어려움
2. 기계어 : 컴퓨터가 별다른 해석과정을 거치지 않고 읽을 수 있는 언어, 명확한 의미와 정확한 문법, 0과 1만 사용하여 구성
3. 하드웨어 : 컴퓨터를 구성하는 물리적인 기계 장치
4. 소프트웨어 : 하드웨어를 효율적으로 운영하기 위해 개발되는 프로그램의 총칭 (하드웨어를 제어하기 위해 규칙을 정하고 지시를 내림)
5. 프로그래밍 : 코딩을 통해 소프트웨어(프로그램)을 제작하는 절차
6. 저급언어(Low Level Language) : 컴퓨터가 이해하기 쉽게 작성된 프로그래밍 언어, 배우기 어렵고 속도 매우 빠름, 거의 기계어
7. 고급언어(High Level Language) : 사람이 이해하기 쉽게 작성된 프로그래밍 언어, 배우기 쉽고 호환성이 높지만 기계어로 번역 필요(compile과정 필요) ex)우리가 공부하는 언어(python, java, C)
8. 원시 프로그램 : 사용자가 작성한 프로그램(고급언어로 작성된 프로그램 파일)
9. 목적 프로그램 : 원시 프로그램이 기계어로 번역된 프로그램 (컴파일 과정을 거쳐 원시 프로그램이 목적 프로그램이 되었다) 컴파일 언어는 번역과정은 시간이 걸리지만 컴파일 후 기계어로 구성된 목적 프로그램의 실행 속도는 빠르다 인터프리터 언어는 전체를 번역하지 않고 한 번에 한 줄씩 번역하여 실행하기 때문에 번역 속도는 빠르지만, 실행 속도는 컴파일 언어에 비해 비교적 느리다

---

프로그래밍 개념

---

개념

1. 상수 : 항상 변하지 않는 값 (항상 고정된 하나의 값)
2. 변수 : 수시로 변할 수 있는 값 ( 특정 값을 기억장치에 저장하기 위해 사용하는 공간)
3. 식별자 : 변수, 함수 등 데이터와 기능을 고유하기 구분하기 위해 명명된 이름
4. 예약어 : 프로그래밍 언어가 미리 기능을 수행하도록 정해 놓은 식별자
5. 소프트웨어 개발 절차 문제분석 -> 기능 결정 -> 설계 -> 구현 -> 테스트/디버그 -> 유지 관리

• 문제분석 : 해결해야할 문제를 정확히 인지, 해결을 위한 기초 데이터 및 공식 확인하는 단계
• 기능결정 : 문제 해결을 위해 수행해야하는 기능, 작업을 결정하는 단계
• 설계 : 프로그램의 전체 구조를 설계, 기능을 수행하기 위한 알고리즘을 순서도, 의사코드 등으로 설계
• 구현 : 설계한 프로그램과 알고리즘을 프로그래밍 언어로 구현
• 테스트/디버그 : 프로그램의 오류가 있는 경우 수정(debug), 모든 경우에 대한 테스트
• 유지 관리 : 사용자 피드백을 통한 프로그래램 업그레이드

1. 순서도(Flow chart) : 약속된 도형과 기호를 이용하여 알고리즘을 표현한 양식
2. 의사코드(Psedo Code) : 특정 언어로 프로그래밍 하기 전에 알고리즘의 모델을 대략적으로 모델링 하는 경우

---

코드의 품질 향상

1. 코드 최적화 기법 : 코드의 구조를 개선하여 성능을 개선 (나쁜 코드를 없애고 클린 코드 작성)
2. 나쁜 코드 : 로직을 이해하기 어려운 스파게티 코드 (중복되거나 유지보수 비용이 높은 코드)
3. 클린 코드 : 중복 최소, 가독성 향상, 유지보수 비용 감소 3-1. 클린코드 작성 원칙

• 가독성 : 이해하기 쉬운 식별자, 명령어, 구조
• 단순성 : 하나의 기능만 수행하도록 기능을 분리하여 함수를 만든다
• 의존성 : 결합도 최소화
• 고유성 : 중복성 제거
• 추상화 : 각 기능들의 공통된 부분을 재사용 모듈로 구성 (추상화하는 이유는 구체화 하기 위해서이다. 일관성있게 구체화 하기 위해서) 3-2. 표준화된 코딩 형식
• 하나의 라인에는 하나의 명령만 실행하도록 하기
• 사용하기 전에 먼저 정의
• 가독성 좋은 식별자와 코드
• 적절한 주석문 사용

1. 코드의 품질 향상 4-1. 코드의 품질 향상 기법

• 테스트(TEST) : 가장 일반적인 코드 검증 방법
• 코드인스펙션 (Code inspection) : 코드에 존재하는 결함을 확인
• 정적분석(Static Analysis) : 프로그램을 실행하지 않고 코드 구조를 분석
• 동적분석(Dynamic Analysis) : 프로그램을 실행하여 결과를 분석
• 증명 (Proof) : 소프트웨어 품질이 아주 중요한 경우에 활용되는 가장 이상적인 방법 4-2. 리팩토링 : 코드의 기능이 아닌 구조를 개선(안정성 향상), 소프트웨어 디자인 개선(가독성 향상) 4-3. 정적분석도구
• pmd : java 및 다른 언어의 버그와 데드 코드 분석
• cppcheck : C/C++에 대한 결함 및 오류를 분석
• SonarQube : 소스코드의 품질을 체크하는 통합 플랫폼 도구
• checkstyle : java코드의 표준 준수 여부를 분석 4-4. 동적분석도구
• valanche : 프로그램의 결함 및 취약점을 분석
• valgrind : 메모리 누수, 쓰레드 결함 등을 분석

---

객체지향 기술

1. 특징 : 현실 세계 개체를 속성과 메서드를 이용하여 디지털 객체화 한다, 객체간 통신을 통해 프로그램 구현

• 객체 : 속성과 메소드로 구성된 클래스의 인스턴스
• 속성 : 객체를 나타내는 자료구조, 상태 값 등
• 메소드 : 속성에 대한 연산기능, 객체가 수행하는 행위

1. 장단점 : 객체를 재사용하여 확정성이 좋고 유지보수에 용이하며, 쉽고 빠르게 현실 세계와 유사한 형태로 개발 : 객체 자체 설계가 어렵고 속도가 비교적 느리다
2. 구성요소

• 클래스(class) : 객체의 타입을 정의하고 객체를 구현하여 생성하는 틀 : 객체들의 공통된 특성을 표현한 데이터 추상화 단위
• 객체(object) 모든 대상 지칭 : 클래스에 의해 구현된 대상들의 총칭, 현실 세계의 개체 : 객체마다 고유한 속성을 가지며 클래스에 정의된 메소드 수행이 가능
• 인스턴스(instance) 구현된 객체 제한적으로 지칭 : 특정 클래스에서 구현된 객체로, 좁은 범위의 객체
• 메시지(message) : 객체들 사이를 상호작용하기위한 인터페이스(메소드)

1. 기술

• 캡슐화 : 문제 해결에 관여하는 속성과 메소드를 하나로 묶는 것 : 정보은닉 (클래스의 내부속성과 메소드를 외부의 고려되지 않는 영향으로 부터 보호) : 재사용 용이, 중복성 최소화, 인터페이스가 단순, 가독성 향상, 내부데이터의 일관성 유지
• 추상화 : 클래스의 공통된 요소를 추출하여 부모 클래스로 구현하고 이후 자식 클래스에서 구체적으로 구현 기능 추상화(IPO), 자료 추상화(데이터와 관련 기능 묶는), 제어 추상화(외부 이벤트에 대한 반응 묶는)
• 상속 : 상위 클래스의 속성과 메소드를 하위 클래스에서 사용, 재사용 또는 확장할 수 있고, 상위 클래스의 추상적인 요소를 하위클래스가 구체화 한다
• 다형성 (객체지향 기술들의 최종 목표) : 상속된 여러 하위 객체들이 서로 다른 형태를 가질 수 있는 성질 : overloading, overriding 동일한 메소드명으로 서로 다른 작업이 가능

1. 개발절차

5-1. 객체지향 분석 (객->동->기)

• 객체모델링 : 업무에서 요구되는 객체, 속성(자료구조), 메소드 식별
• 동적모델링 : 객체들의 기능과 상태 파악, 상태, 활동 다이어그램으로 기능의 흐름 표시
• 기능모델링 : 각 기능 상세분석(제한사항, 성능 등), 제어 흐름, 기능의 상호작용 표현 5-2. 객체지향 분석 방법론
• 럼바우(Rumbaugh) : 가장 대표적이고 객체->동적->기능 모형으로 분리하여 접근하는 방법
• Booch : Micro개발 프로세스로 접근, 클래스 계층 정의 및 클러스터링 작업 수행
• Coad&Yourdon : E-R 다이어그램을 사용하여 객체의 행위를 모델링, (객체식별, 구조식별, 주체정의, 속성 및 관계 정의, 서비스 정의의 과정으로 구성)
• Jacobson : 사용자와 시스템의 상호작용과정을 서술한 시나리오로 접근하는 방법
• Wirfs-Brocks : 설계 프로세스 간에 뚜렷한 구분이 없음, 고객 명세의 평가

1. 객체지향 설계 (설계대로 객체지향 프로그래밍을 진행하면 된다)

6-1. 개념 : 분석이 완료된 모델을 구체적인 절차로 표현 : 사용자 중심, 대화식 프로그램 개발에 적합 : 클래스를 객체로, 속성을 자료구조로, 기능을 알고리즘으로 표현하는 것에 중점

6-2. 설계 원칙 (5가지)

• 단일 책임 : 단일 클래스가 제공하는 모든 기능은 하나의 책임을 수행 (낮은 결합도, 높은 응집도 유지 가능)
• 개방 폐쇄 : 소프트웨어 구성요소는 확장에는 열리고, 변경에는 닫혀 있어야한다.(캡슐화를 통해서 가능)
• 리스코프 치환 : 하위클래스는 언제나 상위 클래스로 교체할 수 있어야한다.(호환되어야한다) (상위 클래스에서 구현한 제약사항을 준수하여 하위클래스 구현하면 할 수 있다)
• 인터페이스 분리 : 사용하지 않는 인터페이스에 시스템이 영향을 받아선 안된다.
• 의존성 뒤집기 : 하위 클래스의 변경 사항이 상위 클래스에 영향을 미치지 않도록 해야한다

6-3. 설계 순서 (객체->기능->동적)

1. 객체지향 테스트

7-1. 단위테스트 : 객체의 가장 작은 단위로 캡슐화된 클래스나 객체를 검사

7-2. 통합테스트

• 쓰레드 기반 : 시스템에 대한 하나의 입력이나 이벤트에 응답하는데 요구되는 클래스를 검증
• 사용 기반 : 상위 클래스 영향이 미치지 않는 수준의 하위 클래스들을 독립적으로 검사한 후 상위 클래스 검증)
• 검증과 시스템 : 사용자의 요구가 객체에 정확히 반영되었는지 성능이나 인터페이스상 오류는 없는지 검증