hyoriyam

Simple Sort Algorithm

데이터를 오름차순 또는 내림차순으로 정렬하는 기본적인 알고리즘

종류 : 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort) 등

1. 버블 정렬 (Bubble Sort)

버블 정렬은 서로 인접한 두 요소를 비교하여 잘못된 순서라면 위치를 바꾸는 방식으로 동작합니다. 이 과정을 반복하여 가장 큰 값이 리스트의 끝으로 "버블"처럼 이동합니다. 

동작 방식:

• 리스트의 처음부터 시작하여 인접한 두 개의 값을 비교합니다.
• 잘못된 순서라면 두 값을 교환합니다.
• 이 과정을 리스트 끝까지 반복한 후, 가장 큰 값이 맨 끝에 위치하게 됩니다.
• 나머지 요소들에 대해 같은 과정을 반복합니다.

예시:

정렬 전: [5, 2, 9, 1, 5, 6]
첫 번째 단계 후: [2, 5, 1, 5, 6, 9]
최종 정렬 후: [1, 2, 5, 5, 6, 9]

2. 삽입 정렬 (Insertion Sort)

삽입 정렬은 리스트를 순차적으로 탐색하며, 각 요소를 이미 정렬된 부분과 비교하여 적절한 위치에 삽입하는 방식입니다.

동작 방식:

• 두 번째 요소부터 시작하여 그 요소를 앞의 정렬된 리스트와 비교합니다.
• 적절한 위치에 삽입하여 정렬된 부분을 확장해 나갑니다.
• 리스트 끝까지 이 과정을 반복합니다.

예시:

정렬 전: [5, 2, 9, 1, 5, 6]
첫 번째 단계 후: [2, 5, 9, 1, 5, 6]
최종 정렬 후: [1, 2, 5, 5, 6, 9]

3. 선택 정렬 (Selection Sort)

선택 정렬은 매번 남아 있는 리스트 중에서 가장 작은(또는 큰) 값을 선택하여 앞쪽부터 차례대로 위치를 정렬해 나가는 방식입니다.

동작 방식:

• 리스트에서 가장 작은 값을 찾아 첫 번째 요소와 교환합니다.
• 다음으로 두 번째 작은 값을 찾아 두 번째 위치와 교환합니다.
• 이 과정을 리스트의 끝까지 반복합니다.

예시:

정렬 전: [5, 2, 9, 1, 5, 6]
첫 번째 단계 후: [1, 2, 9, 5, 5, 6]
최종 정렬 후: [1, 2, 5, 5, 6, 9]

요약:

• 버블 정렬: 인접한 요소끼리 비교하며 정렬.
• 삽입 정렬: 이미 정렬된 부분에 새로운 요소를 삽입하며 정렬.
• 선택 정렬: 남은 요소 중 가장 작은 것을 찾아 차례대로 정렬.

이 알고리즘들은 구조가 단순하고 구현이 쉬워서 학습용으로 적합하지만, 시간 복잡도가 O(n2)O(n^2)O(n2)이기 때문에 큰 데이터 세트에는 비효율적일 수 있습니다.

< 학습목표 >

• 개념: 불안정한 짝(unstable pair)와 안정적인 매칭(stable matching)의 개념을 이해하고,
• 구현: Gale-Shapley 알고리즘이 어떻게 불안정한 짝을 피하고 안정성을 보장하는지 알고,
• 응용: 실제 문제나 응용 사례에서 이 알고리즘을 적용할 수 있어야 합니다.

Stable matching

Def. A stable matching is a perfect matching with no unstable pairs.

Stable Matching 문제의 핵심은 이미 형성된 매칭이 있고, 그 매칭이 불안정한지 또는 안정적인지를 판단하는 것이에요.

Perfect matching

Def. A matching M is a set of ordered pairs h-s with h ∈ H and s ∈ S s.t.

- Each hoshpital h ∈ H appears in at most one pair of M.

Unstable pair

Def. Given a perfect matching M, hospital h and student s form an unstable pair if both.

Key point. An unstable pair h-s could each improve by joint action.

Gale-Shapley deferred acceptance algorithm for Stable Matching Marriage

The Gale-Shapley algorithm, solves the stable matching problem, where you have an equal number of men and women, and each person ranks the people of the opposite gender by their preferences.

The goal if to find a stable matching - a situation where no pair of individuals would both prefer to be with each other over their current partners.

예제 )

Males: 

Adam, Ben, Cian, David, Ethan

Females:

Tina, Wendy, Xena, Yasmine, Zara

선호도 조사가 다음과 같다고 하자. (선호하는 순서대로 적음)

(A, T), (B, W), (C,X), (D,Z), (E, Y)

Meaning of Algorithms

- a set of instructions for solving a problem

Why we use algorithms?

• Algorithms are especially important to computers because computers are general purpose machines for solving problems.
• In order for a computer to be useful, we must give it a problem to solve and a technique for solving the problem.
• Through the use of algorithms, we can make computers intelligent by programming them with various algorithms to solve problems.

Algorithms' Characteristics

• Name
• Description
• Input (입력) : Algorithm receives input
  외부에서 제공되는 자료가 0개 이상 있어야 한다. (입력할 수 없는 경우도 있음.)
• Output (출력) : Produces output
  적어도 1개 이상의 결과를 만들어야 한다.
• Generality(일반성) : The algorithm applies to set of inputs
  같은 유형의 문제에 대해 항상 적용될 수 있어야 합니다.
  
• Order of Operations (명령어의 순서) : Exact order of steps to perform
  설명: 알고리즘은 단계별로 순서가 정확하게 정의되어 있어야 합니다. 이 순서가 바뀌면 원하는 결과를 얻지 못할 수 있기 때문에 명령어의 순서는 매우 중요합니다.
  예시: 버블 정렬에서 인접한 두 수를 비교하고, 그 결과에 따라 위치를 바꾸는 과정이 순차적으로 이루어져야 합니다. 만약 순서가 잘못되면 정렬이 되지 않습니다.
  
• Precision(정확성) : The steps are precisely stated
  설명: 알고리즘의 단계는 명확하고 구체적이어야 하며, 애매하거나 불확실한 명령은 없어야 합니다. 알고리즘을 수행하는 사람이든 컴퓨터든, 각 단계를 정확하게 수행할 수 있어야 합니다.
  예시: "숫자를 비교한다"는 구체적인 단계입니다. 반면 "필요한 작업을 수행한다"는 모호한 지시입니다. 정확한 단계가 없으면 알고리즘이 제대로 실행될 수 없습니다.
  
• Finiteness (유한성) : The algorith terminates
  알고리즘은 유한한 단계를 거쳐 실행이 종료되어야 한다. 모든 명령문은 유한한 시간 내에 실행되어야 하고, 무한 루프같은 무한한 반복을 피해야 한다. 알고리즘은 모든 입력에 대해 종료되어야 하므로 무한히 실행되거나 중단되어서는 안된다.
• Correctness(정확성) : The output produced by algorithm is correct
  입력을 이용한 문제 해결 과정과 출력은 논리적이고 정확해야 합니다. 오류가 없어야 함.
  

※ 알고리즘과 자료구조와의 관계 
알고리즘의 성능은 자료구조에 의해 결정된다.

성능이란, '얼만큼 빨리 수행되느냐.'이다.

같은 자료라고 해도 어떻게 표현되고 저장되느냐에 따라 사용가능한 알고리즘이 달라지기 때문이다.

자료구조의 기본적인 연산을 구현하기 위해서 알고리즘을 사용한다.

※ 알고리즘 분석 기준

복잡도란,

1. 알고리즘의 성능, 효율성을 나타내는 척도. 즉. 어떤 알고리즘이 효율적인지 판단하는 척도.
2. 크게 Time Complextity와 Space Complexity로 나눌 수 있음.
3. 각 알고리즘이 주어진 특정 크기의 입력(n)을 기준으로 수행시간(연산) 혹은 사용 공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시함.
4. 복잡도를 나타내는 방법 : 점근 표기법으로 O(빅오), Ω(오메가), Θ(세타) 등이 있고, 주로 빅오와 세타 표기법이 많이 사용됨.

알고리즘을 평가할 때는 주로 수행 시간과 메모리 사용량을 기준으로 둔다.

1) 시간 복잡도 (Time Complexity)
- 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수를 나타낸다.
- 실행 시간이 아닌, 연산 횟수를 센다. 

- 알고리즘의 성능 평가 Case 분류

• 최선의 경우 (Best Case)
  최적의 입력을 한 상태에서, 작업을 완료하는 데 가장 연산 횟수가 적은 경우
• 최악의 경우 (Worst Case)
  최악의 입력을 한 상태에서, 작업을 완료하는 데 가장 연산 횟수가 많은 경우
• 평균의 경우 (Average Case)
  여러 경우의 수를 고려하여, 총 연산 횟수를 계산하고 시행 횟수로 나눈 경우

알고리즘 분석 시 평균의 경우와 최악의 경우가 가장 많이 활용되며, 알고리즘이 복잡해질수록 Average를 구하기 어려워 Worst Case로 Algorithm Perfomance를 파악한다.

2) 공간 복잡도 (Space Complexity)
- 메모리(저장공간)가 적게 드는 것을 의미한다.

- 프로그램 실행과 완료에 얼마나 많은 공간이 필요한지를 나타낸다.

- 알고리즘을 실행시키기 위해 필요한 공간(space)은 두 가지로 분류한다.

• 고정 공간(Fixed Space), 알고리즘과 무관한 공간
  - 코드가 저장되는 공간
  - 알고리즘 실행을 위해 시스템이 필요로 하는 공간 
• 가변 공간(Variable Space), 알고리즘과 밀접한 공간
  - 문제를 해결하기 위해 알고리즘이 필요로 하는 공간
  - 변수를 저장하는 공간. 순환 프로그램의 경우 순환 스택(recursion stack) 등

3) 시간 복잡도 VS 공간 복잡도

- 시간 복잡도는 얼마나 빠르게 실행되는지, 공간 복잡도는 얼마나 많은 자원(메모리 공간)이 필요한지를 판단한다.
- 시간 복잡도와 공간 복잡도는 반비례하는 경향이 있어, 보통 알고리즘의 성능을 파악할 때는 시간 복잡도를 위주로 파악한다.

01 자료구조 (Data Structure) 

가) 정의

• 자료구조(Data Structure)란 자료를 컴퓨터의 기억장치 내에 저장하는 방법으로 다양한 자료를 효율적으로 표현하고 활용할 수 있도록 자료의 특성과 사용 용도를 고려하여 조직적, 체계적으로 정의한 것.
• 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현방법들
• 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨.
• 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음
• 여러 자료구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 해 자료구조에 대한 이해가 중요

나) 분류

자료구조의 분류 : 선형구조와 비선형 구조

정적 자료구조(Static) : 프로그램 실행 중에 크기가 고정되어 있는 자료구조
- 배열은 정적 자료구조의 대표적인 예로 선언시 배열의 크기가 정해지고 이후에 변경 불가
- 미리 할당된 메모리 공간에 데이터를 저장하기 때문에 데이터 추가, 삭제, 크기 변경 등이 제한적
  
동적 자료구조(Dynamic) : 프로그램 실행 중 크기가 동적으로 조정될 수 있는 자료구조
- 필요에 따라 메모리에서 유연하게 공간을 할당하고 해제헤 데이터를 저장할 수 있어
- 데이터 추가, 삭제, 크기 변경 등이 가능함
- 대표적인 예: ArrayList, LinkedList, Queue, Stack 등이 있음

순차자료구조와 연결자료구조의 비교

**노드(Node)란**

• 자료구조에서 하나의 단위를 의미한다. 노드를 어떤 데이터를 담고 있는 상자라고 이해할 수 있다.
• 노드에는 데이터(data)와 포인터(pointer)가 있다. 포인터는 주로 연결 자료 구조에서 사용되고, 순차 자료 구조에서는 필요하지 않다.

**순차 자료 구조(Sequential Data Structure)란**

• 순차 자료 구조는 배열을 생각하면 된다. 배열, 데이터를 메모리에 차례대로 저장하는 방식. 
• 배열의 가장 큰 특징은 연속적인 공간을 사용한다는 점. 즉, 메모리에서 데이터가 연속적으로 나열되어 있다.
• 배열에서 데이터를 찾을 때는 인덱스로 접근 할 수 있어서 빠르게 찾을 수 있지만, 배열의 중간에 데이터를 삽입하거나 삭제하려면 나머지 데이터를 이동시켜야 하는 번거로움이 있다.
• 선형 리스트(Linear List)와 같은 개념

** 연결 자료 구조(Linked Data Structure)란**

• 연결 자료 구조는 배열과 달리 연속된 공간에 저장하지 않고, 각각의 노드가 서로를 가리키며 연결이 되어있다. 이때, 데이터를 담고 있는 노드가 다음 노드를 가리키는 포인터를 갖고 있다.
• 연결 자료 구조는 중간에 데이터를 쉽게 삽입하거나 삭제할 수 있지만, 특정 위치의 데이터를 찾으려면 처음부터 차례대로 노드를 따라가야 하므로 속도가 느릴 수 있다.
• 연결 리스트(Linked List)는 연결 자료 구조의 대표적인 예시

**간단한 예시:

• 배열(순차 자료 구조):
  [10, 20, 30] (연속된 메모리 공간에 데이터가 순차적으로 저장됨)
• 연결 리스트(연결 자료 구조):
  [10] → [20] → [30] (각 노드가 데이터를 가지고, 다음 노드를 가리키는 방식)

다) 스택과 큐

1) 스택(Stack)

**스택이란**

- 스택은 선형리스트(순차 자료 구조)의 하나로 데이터가 입력된 순서로 기억공간에 저장되어 후입선출하는 자료구조.

- 스택에 저장된 원소는 top으로 정한 곳에서만 접근이 가능하여 top 위치에서만 원소를 삽입하고 마지막에 삽입한 원소는 맨 위에 쌓여 있다가 가장 먼저 출력되게 됨.

- LIFO(Last In First Out) : 후입선출 구조

** 스택의 연산의 종류 **

※ 스택이 비었다는 것은?

스택이 비었다는 것은, 더 이상 스택 안에 쌓여 있는 데이터(원소)가 없다는 것을 의미합니다. 마치 그릇 안에 아무것도 들어 있지 않은 상태를 생각해보면 이해하기 쉽습니다.

stack = []
//스택에 아무것도 넣지 않은 상태

예시를 보자.

stack = [1, 2, 3]  # 스택에 원소가 있음

if not stack:  # 스택이 비었는지 확인
    print("스택이 비었습니다.")  # 이 메시지는 출력되지 않음
else:
    print("스택에 원소가 있습니다.")  # 스택에 원소가 있으니 이 메시지가 출력됨

2) 큐(Queue)

** 큐(Queue)란 **

- 스택과 유사하게 삽입과 삭제의 위치가 제한되어 있지만 스택과는 달리 데이터가 삽입되는 곳과 삭제되는 곳이 다른 자료구조.

- 큐는 뒤에서만 삽입되고 앞에서는 삭제만 할 수 있는 구조로 삽입된 순서대로 원소가 나열되어 가장 먼저 삽입한 원소는 맨 앞에 있다가 가장 먼저 삭제된다. 

- FIFO (First In First Out) 선입선출 구조

** 큐의 연산 종류 **

3) 스택과 큐 연산 비교

라) 트리와 그래프 

1. 트리 (Tree)

- 원소들 간에 계층관계를 가지는 계층형 자료구조로 상위 원소에서 하위 원소로 내려가면서 확장되는 나무 모양의 구조를 가지고 있으며 원소들 간에 1:다 관계를 가진다.

- 트리의 시작노드를 루트노드(root node)라고 하고 노드를 연결하는 선을 간선(edge)이라고 한다. 같은 부모 노드를 가진 자식 노드들을 형제노드(sibling node)라고 하고 부모노드와 연결된 간선을 끊었을 때 생성되는 트리를 서브트리(subtree)라고 한다.

2. 그래프 (Graph)

연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조로 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합이다. 그래프 자료구조는 전기회로분석, 인공지능 등과 같이 여러가지 복잡한 문제들을 그래프로 나타내어 그래프이론을 기반으로 문제를 해결하는 경우가 많다.

마) 자료구조의 선택 기준

• 자료의 처리 시간
• 자료의 크기
• 자료의 활용 빈도
• 자료의 갱신 정도
• 프로그램의 용이성

바) 자료구조의 활용

02 알고리즘(Algorithm)

가) 알고리즘 개요

1) 알고리즘의 정의

- 주어진 문제를 해결하기 위한 일련의 처리 절차를 단계적으로 기술한 것. 문제 해결 방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서이다.

- 알고리즘의 목표 : 단순히 원하는 결과를 얻을 수 있는 알고리즘이 아닌, 처리시간이나 기억장소 사용 측면에서 효율적인 알고리즘을 개발하는 것이다.

2) 알고리즘의 조건

입력, 출력, 명확성, 유한성, 효과성

나) 알고리즘 분석 기준

정확성, 작업량, 기억 장소 사용량, 최적성, 단순성

다) 알고리즘 표현 방법

라) 알고리즘 성능 분석

1) 공간 복잡도

• 고정 공간량 : 프로그램, 변수 및 상수들과 같이 프로그램의 크기나 입출력 횟수에 상관없이 고정적으로 필요한 저장 공간
• 가변 공간량 : 프로그램의 수행과정에서 사용하는 자료와 변수들을 저장하는 공간과 함수 실행에 관련된 정보를 저장하는 공간

2) 시간 복잡도

• 컴파일 시간 : 프로그램 특성과 관련이 적은 고정적인 시간으로 일단 컴파일이 되면 프로그램의 수정이 일어나지 않는 한 일정하게 유지
• 실행 시간 : 프로그램의 실행시간으로 컴퓨터의 성능 등에 의존하므로 실제 정확한 실행 시간을 측정하기 보다는 명령문의 실행 빈도수를 구하여 계산

알고리즘 간의 비교 시에는 주로 실행 시간을 사용하여 시간 복잡도를 나타낼 빅-오(Big Oh) 표기법을 사용하여 O(n)로 표기한다. 알고리즘에 따라 logn, n, nlogn, n^2, n^3, 2^n 등의 실행 시간 함수가 있다. 

가장 작은 값의 시간 복잡도를 가지는 알고리즘을 선택하는 것이 좋다.

마) 정렬 알고리즘

1) 정렬의 분류

• 정렬 장소에 따라 내부정렬(Internal Sort)과 외부정렬(External Sort)로 분류할 수 있다.
• 정렬 방법은 사용하는 시스템의 특성, 데이터의 양과 상태, 정렬에 필요한 기억 공간 및 실행 시간 등의 조건을 고려하여 선택한다.

2) 내부 정렬 알고리즘의 분류

01 소프트웨어 재사용

가) 소프트웨어 재사용(Reuse) 개요

• 소프트웨어 재사용은 기존의 소프트웨어 또는 소프트웨어 지식을 활용해, new 소프트웨어를 구축하는 일이다.
• 재사용가능한 소프트웨어나 소프트웨어 지식은 재사용가능한 자신이다.
• 자신 - 설계, 요구명세, 검사, 아키텍처 등 포함

1. 소프트웨어 재사용 배경

2. 소프트웨어 재사용 정의

• 소프트웨어 재사용이란 사용 소프트웨어 개발 관련 지식(기능, 모듈, 구성 등)을 표준화하여 개발 생산성을 높이기 위하여 반복적으로 사용하기에 적합하도록 구성하는 방법
• 기존 개발 기능, 성능 및 품질을 인정받았던 소프트웨어의 전체 또는 일부분을 다시 사용하여 신규 개발되는 소프트웨어의 품질과 생산성 및 신뢰성을 높이고 개발 일정 및 비용을 감소시켜 주는 대응방안
• 기존 개발 모듈이나 프로그램, 산출물 등을 동일한 응용 분야, 서로 다른 응용업무, 혹은 서로 다른 기업 간에 다시 사용하거나 일부 수정 후 재사용할 수 있는 개념

3. 소프트웨어 재사용의 목적

신뢰성, 확장성, 생산성

신뢰성 - 기능, 안정, 속도 등의 사전 성능 검증됨.

확장성 - 검증된 기능 기반으로 upgrade 용어

생산성 - 비용, 시간 위험 등 전체적 개발 프로세스 향상

나) 소프트웨어 재사용의 대상

다) 소프트웨어 재사용의 원칙

• 범용성 (Generality)
  - 특정 응용 분야만이 아닌 일반적으로 활용될 수 있는 정도여야 한다.
• 모듈성 (Modularity)
  - 정보은닉과 추상화의 원칙으로 최소한의 결합도 및 최대한의 응집력을 갖도록 하는 특성
• 하드웨어 독립성
  - 가능한 실행 하드웨어 기종과 무관해야 한다.
• 소프트웨어 독립성
  - OS 또는 DBMS와는 무관하게 운영해야 한다.
• 자기문서화 (Self Documentation)
  - 모듈의 정확한 기능, 용법, 인터페이스를 기술한다.
• 일반성 (Commonality)
  - 많은 개발자들에게 공통적으로 필요하고 사용 가능해야 한다.
• 신뢰성 (Reliability)
  - 품질을 믿고 사용할 수 있어야 한다.

라) 실무에서 재사용 구현의 문제점

마) 소프트웨어 재사용의 장애요인 및 대책

바) 재사용 적용 시 고려사항

사) 소프트웨어 재사용의 효과

02 역공학

가) 역공학의 정의

• 역공학이란 소프트웨어 공학의 한 분야로 이미 만들어진 시스템을 역으로 추적하여 처음의 문서나 설계기법 등의 자료를 얻어 내는 일을 말한다.
• 유지보수 단계에 수행하는 활동
• 순공학에 상대되는 개념
• input과 output의 흐름을 통해 이해할 수 있다.

나) 역공학이 필요한 경우

• 기 가동중인 시스템의 유지보수가 어려운 경우
• 변경이 빈번하여 시스템 효율이 저하된 경우
• 파일 시스템으로 개발된 업무를 광계형 데이터베이스로 재구축 하려는 경우
• 기본 메인 프레임을 다운사이징하는 경우 

다) 역공학의 장점

상용화되거나 기 개발된 소프트웨어의 분석을 도와줌.

기존 시스템의 자료와 정보를 설계 수준에서 분석할 수 있어 유지 보수성을 향상

기존 시스템 정보를 Repository에 보관하여 CASE의 사용을 용이하게 함

라) 역공학의 종류

논리역공학 (Logical Reverse Engineering)

• 목적: 소프트웨어나 시스템의 논리적 구조와 동작 방식을 분석하는 데 초점을 맞춥니다. 즉, 소프트웨어의 작동 원리, 알고리즘, 논리적 흐름을 이해하는 것이 목적입니다.
• 적용 분야: 주로 시스템의 기능을 분석하여 소스 코드를 재구성하거나, 시스템의 동작 원리를 복원하는 데 사용됩니다. 예를 들어, 프로그래밍 언어로 작성된 코드가 기계어로 컴파일된 후, 이 기계어를 역으로 분석하여 원래의 고수준 소스 코드를 추론하는 것이 논리역공학입니다.
• 활용: 소프트웨어 개선, 오류 수정, 보안 취약점 분석 등에서 많이 사용됩니다. 또한, 기존 시스템을 분석하여 새로운 시스템을 설계하는 데에도 쓰입니다.

자료역공학 (Data Reverse Engineering)

• 목적: 데이터 구조와 형식을 분석하는 데 초점을 둡니다. 특정 파일 형식이나 데이터베이스의 저장 방식을 분석하여 데이터의 구조를 복원하거나, 데이터가 어떻게 처리되고 저장되는지 파악하는 것이 목적입니다.
• 적용 분야: 데이터 파일을 분석하여 데이터베이스나 파일 형식의 구조를 파악하거나, 암호화된 데이터를 해석하는 데 사용됩니다. 예를 들어, 데이터베이스에서 저장된 데이터가 어떻게 인코딩되고, 저장되는지 파악하여 데이터를 추출하거나 복원하는 과정에서 자료역공학이 사용됩니다.
• 활용: 주로 데이터 복구, 호환성 문제 해결, 파일 형식 분석 등에서 많이 사용됩니다.

주요 차이점:

• 논리역공학은 소프트웨어나 시스템의 논리적 흐름과 작동 원리를 분석하는 데 중점을 두고,
• 자료역공학은 데이터 구조 및 형식을 분석하여 데이터를 추출하거나 변환하는 데 중점을 둡니다.

학습 목표 

1. 소프트웨어의 특성과 문제점

2. 소프트웨어공학의 배경과 목적

3. 소프트웨어 개발 프로세스 모델

핵심 키워드

소프트에어의 특성

소프트웨어 생명주기

요구사항분석, 설계, 구현, 테스팅

소프트웨어 요구관리, 소프트웨어 유지관리, 소프트웨어 형상관리, 소프트웨어 품질관리

01 소프트웨어 공학의 배경과 목적

가) 소프트웨어 공학 소개

효과적인 소프트웨어 공학 기술 적용을 위한 3가지 요소

1. 체계적인 업무 방식 및 흐름의 정의와 이를 적용할 수 있는 프로세스(Process)

2. 전문적인 지식을 갖춘 조직 및 인력(People)의 구성

3. 정의된 업무 방식과 조직인력이 효율적으로 운영되기 위한 인프라 기술(Technology)

정리 : 

성공적인 SW 프로젝트의 핵심요소

Process (Procedures & Methods)

People (Process & Organization)

Technology (Tool & Equipments)

나) 소프트웨어 공학 배경

1950s : 소프트웨어 개발 프로젝트를 위한 소프트웨어 공학 개념 도입

1960s : 소프트웨어 수요 급증, "소프트웨어의 위기(Crisis)"-SW 구현하는 인력들의 경험과 능려그 수적인 부족이 원인

              -> 본격적인 소프트웨어 공학 도입

1970s : 소프트웨어 수요 급증 -> 소프트웨어 개발 인력 부족

             해결책 - 비전공자들도 대거 투입 -> 쉽게 수정될 수 있도록 해야됨. (선코딩-후수정 접근방식 이용)

1980s : 개발 생산성을 높이기 위한 방법들 연구.

1990s : 시장에서 경쟁우위 선점을 위한 제품의 시장출시 시간을 단축해야 됨. 

             -> 개발 생산성을 높이기 위한 방법들 연구 활성화. 동시공학(Concurrent Engineering) 모델 활용.

             동시공학 : 폭포수 모델에서 요구사항, 설계 및 구현 등을 동시에 진행할 수 있는 공학 모델

2000s : 급속한 변화에 효과적으로 대응하기 위한 애자일 방법론 도입.

다) 소프트웨어 공학의 4가지 중요요소

소프트웨어 공학

- 정의 : 소프트웨어의 개발, 운용, 유지보수 등의 생명주기 전반을 체계적이고 서술적이며 정량적으로 다루는 학문

- 4가지 중요 요소 : 방법, 도구, 절차, 사람

• 방법론: 프로젝트 계획, 분석, 설계 등 전체 소프트웨어 개발 프로세스를 체계적으로 관리하는 방법.
• 도구: 소프트웨어 개발을 자동화하고 효율성을 높이기 위한 도구들.
• 절차: 개발 과정을 체계적으로 정리하여 효율적으로 작업할 수 있도록 함.
• 사람: 소프트웨어 개발에 참여하는 인력의 중요성을 강조.

02 소프트웨어 개발 생명주기

가) 정의 

- 사용자 환경 및 문제점 이해에서 시작하여 운용/유지 보수에 이르기까지의 모든 과정을 의미함.

타당성 검토 → 개발 계획 →  요구사항 분석 →  설계 →  구현 →  테스트 →  운용 →  유지보수

나) 목적

- 프로젝트 비용 산정과 개발 계획 수립, 기본 골격 구성

- 용어의 표준화

- 프로젝트 관리

다) 소프트웨어 생명주기 선정

- 기업에서 프로젝트의 개발 프로세스를 테일러링하는데 중요한 활동

- 테일러링 : 소프트웨어 개발 프로세스에서 특정 프로젝트나 조직의 필요에 맞게 프로세스나 방법론을 조정하고 최적화하는 것을 의미

라) 소프트웨어 생명주기 모델 종류

1. V 모델

• 요구사항이 명확히 정의된 프로젝트에서 사용됨.
• 각 개발 단계와 그에 따른 검증 및 확인(Verification & Validation) 단계가 연관되어 있으며, 개발 초기부터 테스트를 고려함.
• 이 모델은 체계적이고 명확하게 관리되며, 요구사항 분석과 설계 단계에서 발생한 오류를 발견하기 용이함.

2. VP 모델 (V Model with Prototyping)

• VP 모델: V 모델에 프로토타이핑을 결합한 것으로, 시스템 이해와 리스크 감소를 목적으로 합니다. 이는 개발 초기 단계에서 시스템의 일부분을 신속하게 개발하고, 이를 통해 불확실성을 줄이는 데 도움을 줍니다.
• Prototyping이란 - 소프트웨어 개발 과정에서 최종 제품을 만들기 전에 핵심 기능을 미리 구현한 시제품 또는 초안
• 접근방법 1: 명확하지 않은 문제에 대해 가능한 해결책을 탐색하고 적용하는 방법으로, 반복적으로 시도하면서 불확실성을 줄이는 접근법입니다.
• 접근방법 2: 여러 해결책을 평가하여 가장 적합한 것을 선택하는 방법으로, 특정 기능이나 시스템 성능과 관련된 리스크가 존재할 때 유용합니다.

3. 점증적 모델 (Incremental Model)

• 시스템의 핵심 기능을 먼저 개발하고, 이후 추가 기능을 점진적으로 확장하는 방식입니다.
• 초기에는 제한된 기능만 제공하며, 각 단계에서 시스템이 점점 완성됩니다.
• 개발 초기의 리스크를 줄이고, 시간이 지남에 따라 개선이 필요한 경우에 유용합니다.

4. 진화 모델 (Evolutionary Model)

• 점증적 모델과 비슷하지만, 시스템의 각 버전을 반복적으로 개발하며 점차 완성도를 높입니다.
• 사용자 피드백을 반영하여 지속적으로 시스템을 개선하고, 새로운 기능을 추가합니다.
• 시스템이 완전히 불분명하거나 지속적인 개선이 필요한 경우에 적합합니다.

정리 :

V 모델, VP 모델, 점증적 모델, 진화 모델

03 소프트웨어 개발 방법론

소프트웨어 개발 방법론의 특징 :

- 개발 단계를 각각 정의하고

- 각 단계별 수행활동, 산출물, 검증절차, 산출물, 완료 기준을 정의하고 

- 개발 계획, 분석, 설계 및 구현의 수행 단계에 대해 정형화된 방법과 절차, 지원 도구를 정의한다.

가) 소프트웨어 개발 방법론의 필요성

1. 개발 경험의 축적 및 재활용을 통한 개발 생산성을 향상

2. 효과적인 프로젝트 관리

3. 공식 절차와 산출물을 제시하고 표준용어를 통일하여 의사소통 수단 제공

4. 각 단계별 검증과 승인된 종료를 통해 일정 수준의 품질 보증

나) 소프트웨어 개발 방법론의 필요성

다) 소프트웨어 개발 단계

소프트웨어 개발 활동은 소프트웨어 생명주기에 따라 정의됨.

1. 요구사항 분석: 개발할 소프트웨어의 목적과 요구사항을 명확히 정의하는 단계입니다.
2. 설계: 요구사항을 바탕으로 시스템의 구조와 설계를 구체화하는 단계입니다.
3. 구현: 설계된 내용을 실제 코드로 작성하여 소프트웨어를 개발하는 단계입니다.
4. 테스트: 개발된 소프트웨어가 요구사항을 충족하는지 확인하고 오류를 찾아내는 단계입니다.

정리:

소프트웨어 개발 단계는

요구사항 분석 → 설계 → 구현 → 테스팅

04 애자일 개발 방법론

가) 애자일 방법론 종류

• 애자일 선언문 이후 다양한 애자일 방법론이 등장했으며, 그 중 **스크럼(Scrum)**과 **익스트림 프로그래밍(XP)**이 널리 사용됩니다.
• 최근에는 **린 소프트웨어 개발(Lean Software Development)**도 주목받고 있습니다.
• 주요 애자일 방법론으로는 스크럼, XP, 린 소프트웨어 개발, 애자일 UP(AUP) 등이 있습니다.

나) 애자일 개발 방법론 - XP

1. XP 개요

• XP는 1990년대 후반에 켄트 벡(Kent Beck)이 개발한 방법론으로, 주로 소규모 개발 조직에 적합한 경량화된 개발 방식입니다.
• 테스트 주도 개발(TDD), 일일 빌드(Daily Build), 지속적 통합(Continuous Integration) 등의 기술과 연관됩니다.
• XP는 가치(Value)와 이를 실현하기 위한 실천법(Practice), 원칙(Principle)으로 구성되어 있으며, 반복적인 개발 과정을 통해 점진적으로 소프트웨어를 개선해 나갑니다.
• 국내에서는 스크럼과 같은 다른 애자일 방법론과 함께 적용되는 경우가 많습니다.

2. XP 개발절차

3. XP 가치

• 의사소통: 팀 내의 원활한 소통이 중요하며, 이를 통해 문제를 해결하고 팀워크를 강화합니다.
• 단순성: 불필요한 복잡성을 제거하고, 가능한 한 단순한 설계를 유지합니다.
• 피드백: 지속적인 피드백을 통해 개선하고, 변화에 유연하게 대응합니다.
• 용기: 요구사항의 변경에 용감하게 대처하고, 문제 해결을 주도적으로 수행합니다.
• 존중: 팀원들 간의 상호 존중을 중요하게 여겨야 프로젝트의 성공을 보장할 수 있습니다.

4. XP의 실천 방법

다) 스크럼(SCRUM)

1. 스크럼 개요

프로젝트 관리를 위한 애자일 방법론.

추정 및 조정 기반의 경험적 관리기법의 대표적인 형태이다.

스크럼 역할자 유형 : 제품 책임자, 스크럼 마스터, 스크럼 팀

2. 스크럼 프로세스

스크럼 프로세스는 다음과 같은 3가지 구성 요소를 갖는다. 

• 스프린트(Sprint) : 달력기준 1~4주 단위의 반복개발기간을 가리킨다.
• 3가지 미칭 : 일일 스크럼, 스프린트 계획, 스프린트 리뷰
• 3가지 산출물 : 제품 백로그, 스프린트 백로그, 소멸 차트

3. 스크럼 특징 

• 투명성 - 스크럼은 스크럼 회의, 소멸차트, 스프린트 리뷰와 같은 기법을 이용해서 프로젝트의 상태나 문제점을 효과적으로 파악할 수 있다.
• 타임박싱 - 스크럼을 진행하는 데 들어가는 시간을 제한. 프로젝트 진행에만 집중하는 것이 가능해진다.
• 커뮤니케이션 - 개발자들이 갖고 있는 문제점 공유, 플래닝 포커를 사용하여 사용자의 스토리 구현 난이도, 시간 토론하는 절차를 가짐.
• 경험주의 모델 - 프로젝트에 참여하는 개개인의 경험을 중요시 한다.

create table EMPLOYEE ( 
   id                  INT                 PRIMARY KEY,
   name                VARCHAR(20)         NOT NULL,
   birth_date          DATE,
   sex                 CHAR(1)             CHECK(sex in ('M', 'F')),
   position            VARCHAR(10),
   salary              INT                 DEFAULT 50000000,
   dept_id             INT,
   FOREIGN KEY (dept_id) references DEPARTMENT(id) 
       on delete SET NULL on update CASCADE,
   CHECK (salary >= 50000000)
   );

create table DEPARTMENT (

id               INT                 PRIMARY KEY,

name             VARCHAR(20)         NOT NULL            UNIQUE,

leader_id        INT

);

괄호() 안의 부분을 살펴보면,

attribute name = id

data type = INT

attribute data type 참고: https://spidyweb.tistory.com/61

※ Key constraints : PRIMARY KEY

- table의 tuple을 식별하기 위해 사용, 하나 이상의 attribute(s)로 구성

- primary key는 중복된 값을 가질 수 없으며, NULL도 값으로 가질 수 없다

PRIMARY KEY를 선언하는 방법은 두 가지가 있다. 

1) attribute 하나로 구성될 때

create table PLAYER (

   id          INT          PRIMARY KEY,

   ...

);

2) attribute 하나 이상으로 구성될 때

create table PLAYER (

   team_id           VARCHAR(12),

   back_number       INT,

   ...

   PRIMARY KEY(team_id, back_number)

);

즉, 2번을 적용하여 1을 이렇게 쓸 수도 있다.

create table PLAYER (

   id          INT,

   ...

   PRIMARY KEY(id)

);

※ Key constraints : UNIQUE

- UNIQUE로 지정된 attribute(s)는 중복된 값을 가질 수 없다.

- 단, NULL은 중복을 허용할 수도 있다. (RDBMS마다 다름)

- UNIQUE를 선언하는 방법은 PRIMARY KEY와 동일하게 attribute가 하나로 구성되는 경우, 하나 이상으로 구성되는 경우로 표현

※ NOT NULL constraint

- attribute가 NOT NULL로 지정되면 해당 attribute는 NULL을 값으로 가질 수 없다.

현재 접근 가능한 데이터베이스 보기

SHOW DATABASES;

데이터베이스 구축하기

CREATE DATABASE 데이터베이스명;

다시 SHOW DATABASES;를 하면 내가 생성한 데이터베이스가 보인다.

지금 선택된 데이터베이스 보고 싶을 때

SELECT database();

내가 사용하고자 하는 데이터베이스 보기

USE 데이터베이스명;

(-> 아마 Database changed라고 뜸)

잘 수행됐는지 확인해보자.

SELECT database();

(-> 아마 내가 만든 데이터베이스가 뜸. 아까 실행했을 땐 NULL이었을 것)

만약 내가 만든 데이터베이스를 지우고 싶다면?

DROP DATABASE 데이터베이스명;

DATABASE  vs  SCHEMA

- MySQL에서는 DATABASE와 SCHEMA가 같은 뜻을 의미한다. 

  즉, CREATE DATABASE 데이터베이스명 = CREATE SCHEMA 데이터베이스명

- 다른 RDBMS에서는 의미가 다르게 쓰인다

먼저, relational의 의미를 살펴보기에 앞서, set에 대해 알아보자.

set

- 서로 다른 elements를 가지는 collection

- 하나의 set에서 elements의 순서는 중요하지 않다

- ex) {1, 3, 22, 11, 7}

수학에서의 relation이란 어떤 의미가 있을까?

relation in mathematics

set A와 set B가 있다고 하자.

set A = {1, 2}

set B = {p, ,q, r}

Cartesian product A X B = {(a, b) | a ∈ A and b ∈ B}

여기에서 Cartesian product란, set A와 set B로 만들 수 있는 모든 pair의 조합즉, (1, p), (1, q), (1, r), (2, p), (2, q), (2, r)을 의미한다.

이와 같은 set A, set B 상황에서는 Cartesian product가 binary relation으로 밖에 나오지 않는다.

binary relation ⊆ A X B

※ ⊆ : 부분집합

이 개념을 확장해보자.

집합이 여러 개가 되면 어떻게 될까?

n개의 set이 있다고 하자. 

n-ary relation ⊆ A X B X C X D ..... 

이런 경우를 n 튜플이라고 한다. 

즉, relation in mathematics는 subset of Cartesian product, set of tuples 이다.

이제 수학적 의미에서의 relation이 relational data model에 어떻게 적용되었는지 살펴보자.

student relation을 예로 들어보자.

1. domain 정의하기

- student_ids : 학번 집합, 7자리 정수

- human_names : 사람 이름 집합, 문자열

- university_grades : 대학교 학년 집합 

- major_names : 대학교에서 배우는 전공 이름 집합

- phone_numbers : 핸드폰 번호 집합

2. attribute of student relation

- student_ids : id

- human_names : name

- university_grades : grade 

- major_names : major

- phone_numbers : phone_num (학생 번호)

- phone_numbers : emer_phone_num (비상연락망)

3. student relation in relational data model

relational data model에서의 주요 개념

domain : set of atomic values (더 이상 나누어질 수 없는 값들로 이루어져 있다)

domain name : domain 이름

attribute : domain이 relation에서 맡은 역할 이름

tuple : 각 attribute의 값으로 이루어진 리스트. 일부 값은 NULL일 수 있다

relation : set of tuples

relation name : relation 이름

relation schema

- relation의 구조를 나타낸다.

- relation의 이름과 attributes 리스트로 표기된다

- ex) STUDENT(id, name, grade, major, phone_num, emer_phone_num)

 - attribute와 관련된 constraints도 포함한다

degree of a relation

- relation schema에서 attribute의 수

- ex) STUDENT(id, name, grade, major, phone_num, emer_phone_num)  → degree 6

DDL (data definiton language)

- conceptual schema를 정의하기 위해 사용되는 언어

- internal schema까지 정의할 수 있는 경우도 있음 

SDL (storage definition language)

- internal schema를 정의하는 용도로 사용되는 언어

- 요즘은 특히 relational DBMS에서는 SDL이 거의 없고 파라미터 등의 설정으로 대체됨

VDL (view definiton language)

- external schemas를 정의하기 위해 사용되는 언어

- 대부분의 DBMS에서는 DDL이 VDL 역할까지 수행 

DML (data manipulation language)

- database에 있는 data를 활용하기 위한 언어

- data 추가, 삭제, 수정, 검색 등의 기능을 제공하는 언어

SQL (Structured Query Language)

- 통합된 언어

- 오늘날의 DBMS는 DML, VDL, DDL이 따로 존재하기 보다는 통합된 언어로 존재한다

- 대표적인 예가 relational database language에서 사용되는 SQL 

database schema

- data model을 바탕으로 database의 구조를 기술(description)한 것.

(data model이 database 구조를 모델링할 수 있는 방법을 제시한 것이라면, database schema는 그 모델을 바탕으로 실제로 그 database 구조를 표현하는 것.)

- schema는 database를 설계할 때 정해지며, 한 번 정해진 후에는 자주 바뀌지 않는다.

relational data model에서의 database schema는 학번, 이름, 학년, 전공

database state

- database에 있는 실제 데이터는 꽤 자주 바뀔 수 있다.

- 특정 시점에 database에 있는 데이터를 database state 혹은 snapshot이라고 한다.

- 혹은 database에 있는 현재 instances의 집합이라고도 한다.

three-schema architecture

- database system을 구축하는 architecture 중의 하나

- user application으로부터 물리적인 database를 분리시키는 목적

- 세 가지 level이 존재하며, 각각의 level 마다 schema가 정의되어 있다.

   external schemas (or user views) at external (or view) level

   conceptual schemas at conceptual level

   internal schemas at internal level

- 각 레벨을 독립시켜서 어느 레벨에서의 변화가 상위 레벨에 영향을 주지 않기 위함

- 대부분의 DBMS가 three level을 완벽하게 혹은 명시적으로 나누지는 않음

- 데이터가 존재하는 곳은 internal level

Data Models

- DB의 구조를 기술(descriptive)하는데 사용될 수 있는 개념들이 모인 집합

- DB 구조를 추상화해서 표현할 수 있는 수단을 제공.

   (이때, DB 구조는 데이터 유형, 데이터 관계, 데이터 제약 사항 등등을 포함하는 개)

- data model은 여러 종류가 있으며, 추상화 수준과 DB 구조화 방식이 조금씩 다르다

- DB에서 읽고 쓰기 위한 기본적인 동작들(operation)도 포함한다

data models 분류

총 세 개로 분류 가능하다.

conceptual (or high-level) data models

logical (or representational) data models

physical (or low-level) data models 

※ conceptual (or high-level) data models

- 일반 사용자들(비개발자)이 쉽게 이해할 수 있는 개념들로 이루어진 모델

- 추상화 수준이 가장 높음

- entity-relationship model

※ logical (or representational) data models

- 이해하기 어렵지 않으면서도 디테일하게 DB를 구조화할 수 있는 개념들을 제공

- 데이터가 컴퓨터에 저장될 때의 구조와 크게 다르지 않게 DB 구조화를 가능하게 함.

- 특정 DBMS나 storage에 종속되지 않는 수준에서 DB를 구조화할 수 있는 모델.

- 예를 들어, relational data model, object data model, object-relational data model이 있다. 

- 유명한 DBMS는 거의 다 relational data model이다. 중요하다는 뜻.

※ physical (or low-level) data models

- 컴퓨터에 데이터가 어떻게 파일 형태로 저장되는지를 기술할 수 있는 수단을 제공

- data format, data orderings, access path 등 실제로 컴퓨터에 저장되는 데이터와 밀접

- access path : 데이터 검색을 빠르게 하기 위한 구조체.  e.g.) index

DB란?

- DataBase

- 전자적으로 저장되고 사용되는 관련있는 데이터들의 조직화된 집합

자세하게 들여다보자.

전자적으로(electronically) 저장되고 사용되는 == 예를 들어 instagram 같은 sns

관련있는(related) 데이터들의  == sns에 올린 사진 정보 등

조직화된 집합(organized collection) == 찾으려는 데이터 쉽게 찾을 수 있음

DBMS란?

- DataBase Management Systems

- 사용자에게 DB를 정의하고 만들고 관리하는 기능을 제공하는 소프트웨어 시스템

- ex. PostgreSQL, MySQL, ORACLE, SQL Server

DB를 정의하다 보면 부가적인 데이터가 발생한다.

부가적인 데이터를 metadata라고 한다. 

metadata란?

- database를 정의하거나 기술하는(descriptive) 데이터

- catalog라고도 부름

- data about data, 즉, 데이터를 설명하기 위한 데이터

- 데이터 유형, 구조, 제약 조건, 보안, 저장, 인덱스, 사용자 그룹 등등이 있다.

- metadata 또한 DBMS를 통해 저장/관리된다.

DB System이란?

- DataBase System (database라고도 불리니까 문맥에 따라 구분 잘 해야됨.)

- database + DBMS + 연관된 Application