Sunny's Tech Blog

객체지향 프로그래밍이란?

객체 지향 프로그래밍(Object-Oriented Programming, OOP)은 컴퓨터 프로그래밍의 패러다임 중 하나로, 프로그램을 '객체'의 모임으로 파악하고자 하는 것이다. 객체 지향 프로그래밍은 유연하고 변경이 용이할 뿐만 아니라 유지 보수가 쉽기 때문에 대규모 SW개발에서 자주 사용된다.

객체지향 프로그래밍의 구성 요소

 * 클래스(Class)

- 같은 종류의 집단에 속하는 속성(attribute)과 행위(behavior)를 변수와 메서드로 정의한 것

- 객체를 만들기 위한 일종의 메타정보

- 클래스는 다른 클래스 또는 외부 요소와 독립적으로 디자인

- 쉽게 말해 클래스는 비슷한 구조를 계속 만들어 내기 위한 일종의 틀

* 객체(Object)

- 클래스에서 정의한 것을 토대로 실제 메모리에 할당된 것

- 구현된 모든 대상을 의미

- 물리적으로 존재하거나 추상적으로 생각할 수 있는 것 중에서 자신의 속성을 가지고 있고 다른 것과 식별 가능한 것

- 추상적이고 포괄적인 개념

* 인스턴스(Instance)

- 객체가 메모리에 할당되어 실제 사용되고 있음을 의미

클래스가 붕어빵 틀이라면 그 틀을 통해 생성된 객체(붕어빵) 하나하나를 해당 클래스의 인스턴스(Instance)라고 부른다. 즉, 인스턴스란 현실의 객체를 소프트웨어 내에서 구현한 실체라고 볼 수 있고, 이렇게 생성된 인스턴스들은 각자 고유의 특성을 가지고 독립적으로 존재한다.

* 메서드(Method)

- 클래스로부터 생성된 객체를 사용하는 방법

- 객체에 명령을 내리는 메시지

객체지향 프로그래밍의 등장 배경

1. 순차적 프로그래밍 (=비구조적 프로그래밍)

정의한 기능의 흐름에 따라 순서대로 동작을 추가하며 프로그램을 완성하는 방식이다.

간단한 프로그램의 경우, 이렇게 코드를 짜게 되면 흐름이 눈으로 보이기 때문에 매우 직관적일 것이다. 그러나, 조금이라도 프로그램의 규모가 커지게 되면 곤란해진다. 만일 A → B → C 라는 동작을 구현하다가, C 에서 A 로 돌아가야할 상황이라면 goto 를 활용해야 한다.

그러나 goto 문을 무분별하게 활용하게 되면, 그야말로 스파게티 그 자체가 완성된다. 쭉 나열된 코드 속에서 위로 갔다가 아래로 갔다가 난리도 아니게 된다.

2. 절차적 프로그래밍 (=구조적 프로그래밍)

순차적 프로그래밍을 보완하기 위해 탄생한 것이 절차적 프로그래밍이다. 절차적 프로그래밍에서 '절차'는 함수를 의미한다. 따라서 절차적 프로그래밍이란, 반복되는 동작을 함수 및 프로시저 형태로 모듈화하여 사용하는 방식이다.

반복 동작을 모듈화하여 코드를 많이 줄일 수 있다는 장점이 있지만, 프로시저라는 것 자체가 너무 추상적이라는 단점이 있어 이를 보완하기 위해 탄생한 것이 객체지향 프로그래밍이다.

※ 참고 ※

최근의 프로그래밍 패러다임

• 명령형 프로그래밍 : 무엇(What)을 할 건지를 나타내기 보다, 어떻게(How) 할 건지 설명하는 방식
  • 절차지향 프로그래밍 : 수행되어야 할 처리 과정을 포함하는 방식
  • 객체지향 프로그래밍 : 객체들의 집합으로 프로그램의 상호작용 표현
• 선언형 프로그래밍 : 어떻게(How) 할 건지를 나타내기 보다, 무엇(What)을 할 건지 설명하는 방식
  • 함수형 프로그래밍 : 순수 함수를 조합하고 소프트웨어를 만드는 방식

객체지향 프로그래밍의 특징

1. 추상화

필요로 하는 속성이나 행동을 추출하는 작업

추상적인 개념에 의존하여 설계해야 유연함을 갖출 수 있다.

즉, 세부적인 사물들의 공통적인 특징을 파악한 후 하나의 집합으로 만들어내는 것이 추상화

2. 캡슐화

낮은 결합도를 유지할 수 있도록 설계하는 것

* 결합도(coupling)란 어떤 기능을 실행할 때 다른 클래스나 모듈에 얼마나 의존적인가를 나타내는 말로, 독립적으로 만들어진 객체들 간의 의존도는 최대한 낮게 만드는 것이 중요하다.

즉, 한 곳에서 변화가 일어나도 다른 곳에 미치는 영향을 최소화 시키는 것이 캡슐화

객체가 내부적으로 기능을 어떻게 구현하는지 감추는 것이라고도 볼 수 있다.

캡슐화에서는 정보 은닉을 활용하여 외부에서 접근할 필요가 없는 것들은 private으로 접근하지 못하도록 제한을 둔다.

(객체안의 필드를 선언할 때 private으로 선언하는 이유)

3. 상속

여러 개체들이 지닌 공통된 특성을 부각시켜 하나의 개념이나 법칙으로 성립하는 과정

기존의 클래스에 기능을 추가하거나 재정의하여 새로운 클래스를 정의하는 것으로, 상속을 이용하면 기존에 정의되어 있는 클래스의 모든 필드와 메소드를 물려받아, 새로운 클래스를 생성할 수 있다.

상속을 활용하면 보다 적은 양의 코드로 새로운 클래스를 작성할 수 있고, 코드를 공통적으로 관리할 수 있기 때문에 코드의 추가 및 변경이 매우 용이하다.

4. 다형성

서로 다른 클래스의 객체가 같은 메시지를 받았을 때 각자의 방식으로 동작하는 능력

다형성은, 상속과 함께 활용할 때 큰 힘을 발휘한다. 이와 같은 구현은 코드를 간결하게 해주고, 유연함을 갖추게 해준다.
즉, 부모 클래스의 메소드를 자식 클래스가 오버라이딩해서 자신의 역할에 맞게 활용하는 것이 다형성

객체지향 설계 원칙

SOLID라고 부르는 5가지 설계 원칙이 존재

1 .SRP(Single Responsibility Principle) - 단일 책임 원칙

- 클래스는 단 한 개의 책임을 가져야 한다.

- 클래스를 변경하는 이유는 단 한 개이어야 한다.

- 단일 책임 원칙을 제대로 지키면 변경이 필요할 때 수정할 대상이 명확하다.

2. OCP(Open Closed Principle) - 개방 폐쇄 원칙

- 확장에는 열려 있어야 하고, 변경에는 닫혀 있어야 한다.

- 기능을 변경하거나 확장할 수 있으면서, 그 기능을 사용하는 코드는 수정하지 않는다.

- 개방 폐쇄 원칙을 지키지 않으면, instanceof와 같은 연산자를 사용하거나 다운 캐스팅이 일어난다.

3. LSP(Liskov Substitution Principle) - 리스코프 치환 원칙

- 하위 타입은 상위 타입을 대체할 수 있어야 한다.

- 상위 타입의 객체를 하위 타입의 객체로 치환해도, 상위 타입을 사용하는 프로그램은 정상적으로 동작해야 한다.

- 상속 관계가 아닌 클래스들을 상속 관계로 설정하면, 이 원칙이 위배된다.

4. ISP(Interface Segregation Principle) - 인터페이스 분리 원칙

- 인터페이스는 그 인터페이스를 사용하는 클라이언트를 기준으로 분리해야 한다.

- 클라이언트의 목적과 용도에 적합한 인터페이스만을 제공해야 한다.

- 각 클라이언트가 필요로 하는 인터페이스들을 분리함으로써, 해당 클라이언트가 사용하지 않는 인터페이스에서 변경이 발생하더라도 영향을 받지 않아야 한다.

5. DIP(Dependency Inversion Principle) - 의존 역전 원칙

- 고수준 모듈은 저수준 모듈의 구현에 의존해서는 안된다.

- 저수준 모듈이 고수준 모듈에서 정의한 추상 타입에 의존해야 한다.

- 즉, 추상화에 의존하며 구체화에는 의존하지 않는 설계 원칙을 의미한다.

* 고수준 모듈 : 변경이 없는 추상화된 클래스 (또는 인터페이스)

* 저수준 모듈 : 변하기 쉬운 구체적인 클래스

객체지향 프로그래밍의 장단점

장점

 - 코드의 재사용성이 증가한다.

 - 유지 보수가 용이하다.

단점

 - 설계에 시간과 비용이 많이 들 수 있다.

 - 객체가 많아지면 용량이 커지고, 처리속도가 상대적으로 느리다.

TDD란?

• Test Driven Development의 약자로 테스트 주도 개발 이라고 함
• 소프트웨어를 개발하는 여러 방법론 중 하나
• 반복 테스트를 이용한 소프트웨어 방법론으로, 작은 단위의 테스트 케이스를 작성하고 이를 통과하는 코드를 추가하는 단계를 반복하여 구현

TDD 개발주기

1. RED : 문제를 정의하는 것에 집중
2. GREEN : 그 문제를 해결하는데 집중
3. Refactor : 작성한 코드를 개선하는데 집중

TDD는 어떤 상황에서 해야할까

1. 처음 해보는 프로그램 주제 (내부적인 불확실성이 높은 경우)
2. 고객의 요구조건이 바뀔 수 있는 프로젝트 (외부적인 불확실성이 높은 경우)
3. 개발하는 도중 코드를 많이 바꿔야 된다고 생각하는 경우
4. 개발이 완료된 후, 해당 코드를 누가 유지보수 할지 모르는 경우

즉, 불확실성이 높을 때 TDD를 하면 된다.

TDD의 궁극적인 목표는 작동하는 깔끔한 코드를 작성하는 것이다.

TDD의 개발 단계에는 리팩토링이 있는데, 이 리팩토링 과정을 거치면서 중복된 코드들은 제거되고, 복잡한 코드들은 깔끔하게 정리하게 된다. 또한 테스트를 처음 작성할 때에는 귀찮고 개발을 느리게 한다는 느낌을 받을 수 있지만, 장기적으로 보면 개발 비용을 아껴줄 수 있다.

TDD 개발 방법론의 프로그래밍 순서

1. 실패하는 작은 단위 테스트를 작성한다.
2. 테스트를 통과하기 위해 프로덕션 코드(실제 동작하는 코드)를 작성한다.
3. 그 다음의 테스트 코드를 작성한다. 실패 테스트가 없을 경우에만 성공 테스트를 작성한다.
4. 새로운 테스트를 통과하기 위해 프로덕션 코드를 추가 또는 수정한다.
5. 1~4단계를 반복하여 실패/성공의 모든 테스트 케이스를 작성한다.
6. 개발된 코드들에 대해 모든 중복을 제거하며 리팩토링한다.

즉, 단위 테스트 작성 → 단위 테스트 실행 → 운영 코드 작성 → 단위 테스트 실행 → 설계 개선(리팩토링) → 단위 테스트 → …  의 실행을 반복

일반적인 개발 vs TDD 개발

1) 일반적인 개발

보통의 개발 방식은 '요구사항 분석 -> 설계 -> 개발 -> 테스트 -> 배포'의 형태의 개발 주기를 갖는데, 이러한 방식은 소프트웨어 개발을 느리게 하는 잠재적 위험이 존재한다.

그 이유로는, 

1. 소비자의 요구사항이 처음부터 명확하지 않을 수 있음
2. 처음부터 완벽한 설계는 어려움
3. 자체 버그 검출 능력 저하 또는 소스코드의 품질 저하
4. 자체 테스트 비용이 증가할 수도 있음

어느 프로젝트든 초기 설계가 완벽하다고 할 수 없기 때문에, 외부 또는 내부 조건에 의해 코드 재설계가 필요할 것이다.

하지만 재설계로 인해 코드를 삽입, 수정, 삭제 하는 과정에서 불필요한 코드가 남거나 중복 처리 될 가능성이 크다.

이러한 코드들은 재사용이 어렵고 관리가 어려워져 유지보수를 어렵게 만든다.

또한, 작은 부분의 기능 수정에도 모든 부분을 테스트해야 하므로 전체적인 버그를 검출하기 어려워진다.

따라서 자체 버그 검출 능력이 저하되고, 그 결과 어디서 버그가 발생할지 모르기 때문에 잘못된 코드도 고치지 않으려 하는 현상이 나타나고 이는 소스코드의 품질 저하과 직결된다.

2) TDD 개발

TDD와 일반적인 개발 방식의 가장 큰 차이점은 테스트 코드를 작성한 뒤에 실제 코드를 작성한다는 점이다.

디자인(설계) 단계에서 프로그래밍 목적을 반드시 미리 정의하고, 무엇을 테스트할지 테스트 케이스를 작성해야 한다. 

1. 테스트 코드를 작성하는 도중 발생하는 예외 사항(버그, 수정사항)들은 테스트 케이스에 추가하고 설계를 개선
2. 이후 테스트가 통과된 코드만을 코드 개발 단계에서 실제 코드로 작성

이러한 반복적인 단계가 진행되면서 자연스럽게 코드의 버그가 줄어들고, 소스코드는 간결해진다.

또한, 테스트 케이스 작성으로 인해 자연스럽게 설계가 개선됨으로 재설계 시간이 절감된다.

TDD 개발 방식의 장점

1) 튼튼한 객체 지향적인 코드 생산

TDD는 코드의 재사용 보장을 명시하므로, 소프트웨어 개발 시 기능별 철저한 모듈화가 이뤄진다. 이는 종속성과 의존성이 낮은 모듈로 조합된 소프트웨어 개발을 가능하게 하며, 필요에 따라 모듈을 추가하거나 제거해도 소프트웨어 전체 구조에 영향을 미치지 않게 된다.

2) 재설계 시간의 단축

테스트 코드를 먼저 작성하기 때문에 개발자가 지금 무엇을 해야하는지 분명히 정의하고 개발을 시작하게 된다. 또한 테스트 시나리오를 작성하면서 다양한 예외사항에 대해 생각해볼 수 있다. 이는 개발 진행 중 소프트웨어의 전반적인 설계가 변경되는 일을 방지할 수 있다.

3) 디버깅 시간의 단축

TDD 개발 방식 프로세스 중 단위 테스트가 이루어지는 것에 대한 이점이기도 하다. 예를 들면 사용자의 데이터가 잘못 나온다면 DB의 문제인지, 비즈니스 레이어의 문제인지 UI의 문제인지 실제 모든 레이러들을 전부 디버깅 해야하지만, TDD의 경우 단위테스트가 이루어지기 때문에 특정 버그를 손쉽게 찾아낼 수 있다.

4) 테스트 문서 대체 가능

주로 SI 프로젝트 진행 과정에서는 어떤 요소들이 테스트 되었는지 테스트 정의서를 만든다. 이것은 단순 통합 테스트 문서에 지나지 않는다. 하지만 TDD를 하게 되면 테스팅을 자동화시킴과 동시에 보다 정확한 테스트 근거를 산출할 수 있다.

5) 추가 구현의 용이함

개발이 완료된 소프트웨어에 어떤 기능을 추가할 때 가장 우려되는 점은 해당 기능이 기존 코드에 어떤 영향을 미칠지 알지 못한다는 것이다. 하지만 TDD의 경우 자동화된 단위 테스트를 전제하므로 테스트 기간을 획기적으로 단축시킬 수 있고, 이는 곧 추가 구현의 용이함으로 이어진다.

TDD 개발 방식의 단점

가장 큰 단점은, 생산성의 저하이다.

처음부터 2개의 코드를 짜야하고, 중간에 테스트를 하면서 고쳐나가야 하기 때문에 생산성이 저하될 수 있다. TDD 방식의 개발 시간은 일반적인 개발 방식에 비해 대략 10~30% 정도로 늘어난다고 한다.

그리고 SI 프로젝트에서는 소프트웨어의 품질보다 납기일 준수가 훨씬 중요하기 때문에 TDD 방식을 잘 사용하지 않는다.

다익스트라 알고리즘이란?

그래프에서 여러 개의 노드가 존재할 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘.

주로 최단 경로를 찾는 문제에서 자주 사용하는 알고리즘이다.

* 다익스트라 알고리즘 동작 원리

1. 출발 노드를 설정
2. 각 노드의 최단 거리를 기록할 테이블 정의 후, 최단 거리 테이블을 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 
4. 해당 노드를 거쳐 다른 노드로 가는 간선 비용을 계산하여 최단 거리 테이블을 업데이트
5. 위 과정에서 3, 4번을 반복

(단, 음의 간선이 존재하지 않을 때 즉, 간선(edge)의 값이 0 이상의 양수일 때 다익스트라 알고리즘이 정상적으로 동작)

* 동작 원리 상세 설명

1. 출발 노드 설정 및 최단 거리 테이블 초기화

2. 시작 노드인 1번 노드에 인접한 노드들의 거리를 갱신 (최단 거리 테이블 갱신)

3.

3-1) 방문하지 않은 노드들 중에서 최단 거리가 가장 짧은 노드를 선택 > 4

3-2) 1번 노드 방문 처리 및 새롭게 변경된 시작 노드(4)를 기준으로 인접한 노드들의 거리를 갱신

3번 노드의 경우, min(5,1+3) 이라고 되어 있다. 여기서 5는 시작 노드 1번에서 3번 노드로 한 번에 갈 수 있는 거리였다. 그리고 1+3 이라고 되어 있는 부분은 시작노드 1번에서 4번 노드로 가는 거리비용 1 과 4번 노드에서 3번 노드로 가는 거리비용 3을 의미한다. 이 중 거리비용을 최소화하는 경로는 시작노드인 1번에서 3번으로 다이렉트로 한 번에 가는 것보다 4번 노드를 거쳐 3번 노드로 가는 1 -> 4 -> 3 으로 가는 경로가 최단 경로이다.

이와 같이 간선 비용을 계산하여 최단 거리 테이블을 업데이트 해준다.

4. 가장 마지막으로 갱신된 최단 거리 테이블 기준으로, 방문하지 않은 노드 중 가장 거리가 작은 노드를 다음 탐색 노드로 선정 (거리 비용이 동일할 경우에는 노드 번호가 작은 것부터 탐색)

새로 변경된 시작 노드 2에 인접한 노드 (3, 4)의 거리를 갱신한다. 3번 노드의 경우는, 기존의 최단 경로 값인 4와 1번에서 2번 노드로 가는 거리비용 2 와 2번 노드에서 3번 노드로 가는 거리비용 3 을 의미한다. 이때는 기존 최단 경로값이 더 최소값이기 때문에 최단 거리 테이블을 갱신하지 않는다. 4번 노드도 이와 마찬가지로 갱신되지 않는다.

그리고 방문하지 않은 노드 (3, 5, 6) 중 가장 거리가 작은 5번 노드를 다음 탐색 노드로 선정한다.

이런식으로 모든 노드를 한 번씩 탐색하여 다익스트라 알고리즘 과정을 최종적으로 완료한다.

결국 다익스트라 알고리즘은 방문하지 않은 노드 중에서 가장 거리가 짧은 노드를 선택하는 과정을 반복하는 게 핵심

* 다익스트라 알고리즘 구현 방법

방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위한 방법으로는 순차 탐색 & 최소힙 2가지가 있다.

1) 순차 탐색

O(N^2)의 시간 복잡도를 가진다. 총 O(N)번에 걸쳐 가장 짧은 노드를 매번 선형 탐색 해야하고, 현재 노드와 연결된 노드를 매번 일일히 확인해야 하기 때문이다. 따라서 전체 노드의 수가 5,000개 이하라면 순차탐색 방법을 써도 괜찮지만, 그 이상이라면 힙을 사용하는 개선된 다익스트라 알고리즘을 이용하는 것이 좋다.

import sys

input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 노드 방문 여부 확인을 위한 테이블
visited = [False]*(n+1)
# 최단 거리 테이블
distance = [INF]*(n+1)

# 노드 연결정보
graph = [[] for i in range(n+1)]

for _ in range(m):
  # a번 노드에서 b번 노드로 가는 비용 c
  a,b,c = map(int, input().split())
  graph[a].append((b,c))

# 방문하지 않은 노드 중 가장 최단거리가 짧은 노드의 번호를 반환
def get_smallest_node():
  min_value = INF
  index = 0
  for i in range(1, n+1):
    if distance[i] < min_value and not visited[i]:
      min_value = distance[i]
      index = i
  return index




# 다익스트라 알고리즘
def dijkstra(start):
  # 시작 노드
  distance[start] = 0
  visited[start] = True
  
  # 출발노드와 인접한 노드들에 대해 최단 거리 테이블 갱신
  for j in graph[start]:
    distance[j[0]] = j[1]

  # 모든 노드에 대해 반복
  for i in range(n-1):
    # 현재 최단거리가 가장 짧은 노드를 꺼내서 방문처리
    now = get_smallest_node()
    visited[now] = True
    # 선택된 노드와 연결된 다른 노드를 확인
    for j in graph[now]:
      # 선택된 노드를 통해 가는 비용을 다시 계산
      # 선택된 노드의 비용 + 연결된 노드로 가는 비용
      cost = distance[now] + j[1]
      # 선택된 노드를 거쳐서 가는 비용이 더 짧은 경우
      if cost<distance[j[0]]:
        distance[j[0]] = cost # 최단거리 테이블 갱신

2) 최소힙 (우선순위 큐 자료구조 활용)

파이썬의 heapq 라이브러리는 원소로 튜플을 받으면 튜플의 첫 번째 원소를 기준으로 우선순위 큐를 구성한다. 따라서 (거리, 노드 번호) 순서대로 튜플 데이터를 구성해 우선순위 큐에 넣으면 거리순으로 정렬된다. 이를 통해 거리가 가장 짧은 노드를 선택한다. 힙에서 노드를 꺼냈는데 만약 해당 노드를 이미 처리한적이 있다면 무시하고 아직 처리하지 않은 노드에 대해서만 처리한다.

import heapq
import sys

input = sys.stdin.readline # 빠른 입력
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 최단 거리 테이블
distance = [INF]*(n+1)

# 노드 연결정보
graph = [[] for i in range(n+1)]

for _ in range(m):
  # a번노드에서 b번 노드로 가는 비용c
  a,b,c = map(int, input().split())
  graph[a].append((b,c))






# 다익스트라 알고리즘(최소힙 이용)
def dijkstra(start):
  q=[]
  # 시작 노드
  heapq.heappush(q, (0,start))
  distance[start] = 0

  while q:
    # 가장 최단거리가 짧은 노드에 대한 정보 꺼내기
    dist, now = heapq.heappop(q)

    # 이미 처리된 노드였다면 무시
    # 별도의 visited 테이블이 필요없이, 최단거리 테이블을 이용해 방문 여부 확인
    if distance[now] < dist:
      continue
    # 선택된 노드와 인접한 노드를 확인
    for i in graph[now]:
      cost = dist + i[1]
      # 선택된 노드를 거쳐서 이동하는 것이 더 빠른 경우
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q, (cost,i[0]))

개선된 다익스트라 알고리즘의 시간 복잡도는 O(ElogV)이다. 이때 E는 간선의 개수, V는 노드의 개수를 의미한다.

간선의 개수 E가 시간 복잡도에 관여하는 이유로는,

위 소스코드를 보면 우선순위 큐에서 꺼낸 노드를 탐색할 때, 해당 노드와 연결된 노드들만 탐색하므로 최악의 경우라도 총 간선의 개수인 E만큼을 반복하게 된다. 따라서 E개의 간선을 힙에 넣었다 빼는 것으로 볼 수 있으므로 O(ElogE)가 되게 된다. (힙에서 삽입, 삭제 시간복잡도는 O(logN)이다.)

logE < log(V^2)이고, log(V^2)은 2logV이기 때문에 O(logV)로 표현할 수 있다. 따라서, 다익스트라 알고리즘 전체 시간 복잡도를 O(ElogV) 로 표현할 수 있다.

BFS (Breadth First Search)

너비 우선 탐색이라고 부르며, 가까운 노드부터 탐색하는 알고리즘이다.

​

BFS는 큐(Queue) 자료구조를 이용하며, 동작 방식은 다음과 같다.

​

• 탐색시작 노드를 큐에 저장(q.push()) 후 *방문 처리
• 큐에서 노드를 꺼내(q.pop()) 해당 노드의 인접 노드들을 큐에 저장 후 방문 처리
• 큐가 빌 때까지 반복

여기서 *방문 처리란 탐색한 노드를 재방문하지 않도록 구분하는 것. 즉, 큐에 한 번이라도 삽입된 노드를 다시 삽입하지 않도록 체크하는 것을 의미

BFS 동작 과정

1) 시작 노드인 노드 1을 큐에 삽입하고 방문 처리

2) 큐에서 노드 1을 꺼내고 노드 1과 인접한 노드 2, 3을 큐에 삽입하고 방문 처리

3) 큐에서 노드 2를 꺼내고 노드 2와 인접한 노드 8을 큐에 삽입하고 방문 처리

(일반적으로 인접한 노드가 2개 이상인 경우에는 해당 노드들 중 번호가 낮은 노드부터 처리)

4) 큐에서 노드 3을 꺼내고 노드 3과 인접한 노드 4, 5를 큐에 삽입하고 방문 처리

5) 큐에서 노드 8을 꺼내고 노드 8과 인접한 노드 6, 7을 큐에 삽입하고 방문 처리

6) 그래프 내 노드에서 방문하지 않은 노드가 없으므로 큐에서 모든 노드를 차례대로 꺼냄

결과적으로 노드의 탐색 순서, 즉 큐에 삽입한 순서는 다음과 같다.
1 -> 2 -> 3 -> 8 -> 4 -> 5 -> 6 -> 7

BFS 구현 코드

# deque 라이브러리 불러오기
from collections import deque

# BFS 메서드 정의
def bfs (graph, node, visited):
    # 큐 구현을 위한 deque 라이브러리 활용
    queue = deque([node])
    # 현재 노드를 방문 처리
    visited[node] = True
    
    # 큐가 완전히 빌 때까지 반복
    while queue:
        # 큐에 삽입된 순서대로 노드 하나 꺼내기
        v = queue.popleft()
        # 탐색 순서 출력
        print(v, end = ' ')
        # 현재 처리 중인 노드에서 방문하지 않은 인접 노드를 모두 큐에 삽입
        for i in graph[v]:
            if not (visited[i]):
                queue.append(i)
                visited[i] = True

DFS (Depth First Search)

깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

​

DFS는 스택 자료구조를 이용하며, 동작 방식은 다음과 같다.

​

• 현재 노드 방문처리​
• 현재 노드와 연결된 다른 노드들 방문
• 해당 노드를 방문하지 않았다면 재귀적으로 dfs 함수 실행

​

​

DFS 동작 과정

1) 시작 노드인 노드 1을 스택에 삽입하고 방문 처리

2) 스택 내 최상단 노드인 노드 1에 인접한 노드는 2, 3이 있음. 번호가 낮은 노드 2를 스택에 삽입하고 방문 처리

3) 스택 내 최상단 노드인 노드 2에 인접한 노드 8을 스택에 삽입하고 방문 처리

4) 스택 내 최상단 노드인 노드 8에 인접한 노드는 6과 7이 있으며, 번호가 낮은 노드 6을 스택에 삽입하고 방문 처리

5) 스택 내 최상단 노드인 노드 6에 인접하며 방문하지 않은 노드 7을 스택에 삽입하고 방문 처리

6) 최상단 노드인 노드 7에 인접하며 방문하지 않은 노드가 없으므로 스택에서 노드 7을 꺼냄

7) 최상단 노드인 노드 6에 인접하며 방문하지 않은 노드가 없으므로 스택에서 노드 6을 꺼냄

8) 마찬가지로 노드 8, 2도 위와 같은 과정을 거친 후, 노드 1에 인접하면서 방문 이력이 없는 노드 3을 스택에 삽입하고 방문 처리

9) 노드 3에 인접하면서 방문하지 않은 노드는 노드 4와 5가 있지만, 번호가 낮은 노드 4를 스택에 삽입하고 방문 처리

10) 노드 4에 인접한 노드 5를 스택에 넣고 방문 처리

11) 방문하지 않은 노드가 없기 때문에 스택에서 모든 노드를 차례대로 꺼냄

결과적으로 노드의 탐색 순서, 즉 스택에 삽입한 순서는 다음과 같다.

1 -> 2 -> 8 -> 6 -> 7 -> 3 -> 4 -> 5

DFS 구현 코드

# DFS 메서드 정의
def dfs (graph, node, visited):
    # 해당 노드를 방문 처리
    visited[node] = True
    # 탐색 순서 출력
    print(node, end = ' ')
    # 한 노드로부터 인접한 다른 노드를 재귀적으로 방문 처리
    for i in graph[node]:
        if not visited[i]:
            dfs(graph, i, visited)

이분탐색(=이진탐색)이란?

정렬되어 있는 배열에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

• 이분 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
• 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점 존재
• 변수 3개(start, end, mid)를 사용하여 탐색. 찾으려는 데이터와 중간점 위치(mid)에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정

이분탐색 과정

1. 배열의 중간 값(mid)을 가져옴

2. 중간 값과 찾으려는 데이터 값을 비교

3. 중간 값이 찾고자 하는 데이터와 같다면 종료 (mid = key)

   ▷ 중간 값보다 찾고자 하는 데이터 값이 크다면, 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색 (mid < key)

   ▷ 중간 값보다 찾고자 하는 데이터 값이 작다면, 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색 (mid > key)

4. 값을 찾을 때까지 반복

예시) 찾고자 하는 key 데이터 = 32

1) low, mid, high 값 설정

2) Mid < key 이므로, Mid값을 기준으로 오른쪽 구간을 탐색 범위로 설정

3) 변경된 low, high값에 기반해 Mid 값 다시 설정

4) 이번에는 Mid > key 이므로, Mid 값을 기준으로 왼쪽 구간을 탐색 범위로 설정

5) Mid 값 다시 설정

6) 찾고자 하는 값 (32)와 Mid 값이 동일하므로, 데이터를 반환

이분탐색 코드

1) 반복문 이용

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        # 원하는 값 찾은 경우 인덱스 반환
        if array[mid] == target:
            return mid
        # 원하는 값이 중간점의 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
        elif array[mid] > target:
            end = mid - 1
        # 원하는 값이 중간점의 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
        else:
            start = mid + 1

2) 재귀함수 이용

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2

    # 원하는 값 찾은 경우 인덱스 반환
    if array[mid] == target:
        return mid
    # 원하는 값이 중간점의 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    # 원하는 값이 중간점의 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
    else:
        return binary_search(array, target, mid + 1, end)

이분탐색 시간복잡도

O(logN)

단계마다 탐색 범위를 반으로 나누므로 위와 같은 시간 복잡도를 가짐

EX) 처음 데이터의 개수가 32개라면, 이론적으로 1단계를 거치면 약 16개의 데이터가 남고, 2단계에서 약 8개, 3단계에서 약 4개의 데이터만 남게 됨.
즉, 이분 탐색은 탐색 범위를 절반씩 줄이고, O(logN)의 시간 복잡도를 보장

HTTP (HyperText Transfer Protocol)

• Hypertext인 HTML을 전송하기 위한 통신 규약
• 서버와 클라이언트 간의 데이터를 주고 받는 프로토콜
• 텍스트, 이미지, 영상, JSON 등등 거의 모든 형태의 데이터를 전송 가능함
• 80번 포트 사용
• 클라이언트가 서버에 요청을 보내고, 서버가 응답을 클라이언트에 보내면 바로 연결이 끊어짐 (비연결, Connectionless)
• 연결을 끊는 순간, 클라이언트와 서버 간의 통신은 끝나며 상태 정보를 유지하지 않음 (무상태, Stateless)

◆ HTTP의 문제

1. 암호화 기능이 없음

서버에서부터 브라우저로 전송되는 정보가 암호화되지 않는다는 문제가 존재. 단순 text 형식으로 주고받기 때문에 중간에 누군가가 신호를 가로챈다면 내용이 그대로 노출됨

2. 통신 내용 변경 가능

요청을 보낸 곳과 받은 곳의 리소스가 정확히 일치하는지 확인할 수 없으므로, 누군가가 중간에 데이터를 가로채 악의적으로 변조한다면 정확한 데이터를 주고받을 수 없게 됨

3. 신뢰할 수 있는 사이트인지 확인 불가

통신하려는 사이트를 따로 확인하는 작업이 없어, 다른 사이트가 통신하려는 사이트로 위장이 가능함

HTTPS (HyperText Transfer Protocol Secure)

• HTTP + SSL(Secure Socket Layer) = 보안이 강화된 HTTP
• 서버와 클라이언트 간의 모든 통신 내용이 암호화됨
• 개인 정보와 같은 민감한 데이터를 주고 받아야 한다면 HTTPS를 이용
• 443번 포트 사용

* SSL = TLS(Transport Layer Security)

인터넷에서 정보를 암호화해서 송수신하는 프로토콜

◆ HTTPS의 동작 과정

HTTPS는 대칭키 & 비대칭키(공개키) 암호화를 모두 사용

HTTPS 연결과정(Hand-Shaking)에서 먼저 서버와 클라이언트 간에 세션키를 교환함

여기서 세션키는 주고 받는 데이터를 암호화하기 위해 사용되는 대칭키이며, 데이터 간의 교환에는 빠른 연산 속도가 필요하므로 세션키는 대칭키로 만들어짐

이 세션키를 클라이언트와 서버가 교환하는 과정에서 비대칭키가 사용됨

즉, 처음 연결을 성립하여 안전하게 세션키를 공유하는 과정에서 비대칭키가 사용되고,

이후에는 데이터를 교환하는 과정에서 빠른 연산 속도를 위해 대칭키가 사용되는 것

흐름제어

송신 측과 수신 측의 TCP 버퍼 크기 차이로 인해 생기는 데이터 처리 속도 차이를 해결하기 위한 기법

* TCP 버퍼란?

송신 측은 버퍼에 TCP 세그먼트를 보관한 후 순차적으로 전송하고, 수신 측은 도착한 TCP 세그먼트를 애플리케이션이 읽을 때까지 버퍼에 보관

수신 측이 송신 측보다 데이터 처리 속도가 빠르다면 문제가 없지만,
송신 측의 속도가 빠를 경우에는 수신 측에서 제한한 저장 용량을 초과한 이후에 도착하는 패킷은 손실될 수 있음. 

만약 손실된다면 불필요한 추가 패킷 전송이 발생하게 됨

◆ 흐름 제어 기법

1) Stop and Wait

• 매번 전송한 패킷에 대해 확인 응답을 받아야만, 그 다음 패킷을 전송하는 방법
• 패킷을 하나씩 보내기 때문에 비효율적인 방법

2) Sliding Window

• 수신 측에서 설정한 윈도우 크기만큼 송신 측에서 확인 응답(ACK) 없이 패킷을 전송할 수 있게 하여 데이터 흐름을 동적으로 조절하는 제어 기법
• 윈도우에 포함된 패킷을 계속 전송하고, 수신 측으로부터 확인 응답이 오면 윈도우를 옆으로 옮겨 다음 패킷들을 전송함

혼잡제어

송신 측의 데이터 전달과 네트워크의 데이터 처리 속도 차이를 해결하기 위한 기법

데이터의 양이 라우터가 처리할 수 있는 양을 초과하면 초과된 데이터는 라우터가 처리하지 못함
이때 송신 측에서는 라우터가 처리하지 못한 데이터를 손실 데이터로 간주하고 계속 재전송하여 네트워크를 혼잡하게 함

이런 상황은 송신 측의 전송 속도를 적절히 조절하여 예방 가능한데, 이를 혼잡제어라고 함

◆ 혼잡 제어 기법

1) AIMD (Additive Increase/Multicative Decrease)

• 처음에 패킷을 하나씩 보내고 문제 없이 도착하면 윈도우의 크기를 1씩 증가시켜가며 전송 (=Additive Increase)
• 만약 전송에 실패한다면, 윈도우 크기를 반으로 줄임 (=Multicative Decrease)
• 윈도우 크기를 너무 조금씩 늘리기 때문에 네트워크의 모든 대역을 활용하여 제대로 된 속도로 통신하기까지 시간이 오래 걸린다는 단점이 존재

2) Slow Start (느린 시작)

• 윈도우의 크기를 1, 2, 4, 8, ... 과 같이 지수적으로 증가시키다가 혼잡이 감지되면 윈도우 크기를 1로 줄이는 방식
• 보낸 데이터의 ACK가 도착할 때마다 윈도우 크기를 증가시키기 때문에, 처음에는 윈도우 크기가 조금 느리게 증가하더라도 시간이 갈수록 점점 빠르게 증가한다는 장점이 존재

3) 빠른 재전송 (Fast Retransmit)

• 수신 측에서 순서대로 도착한 마지막 패킷의 다음 순번을 ACK 패킷에 실어서 보냄
• 이러한 ACK를 중복해서 3개 받으면 재전송이 이루어짐
• 송신 측은 자신이 설정한 타임 아웃 시간이 지나지 않았어도 바로 해당 패킷을 재전송할 수 있기 때문에 보다 빠른 재전송률을 유지할 수 있음

4) 빠른 회복 (Fast Recovery)

• 혼잡한 상태가 되면 윈도우 크기를 반으로 줄이고, 선형 증가시키는 방법
• 해당 방법을 적용하면 혼잡 상황을 한 번 겪고 나서부터는 AIMD 방식으로 동작함

결론적으로...

흐름제어는 송수신 측 사이의 패킷 수를 제어하는 기능

혼잡제어는 네트워크 내의 패킷 수를 조절하여 네트워크의 오버플로우를 방지하는 기능

TCP (Transmission Control Protocol)

• 인터넷상에서 데이터를 메세지의 형태로 보내기 위해 IP와 함께 사용되는 프로토콜
• TCP는 애플리케이션에 신뢰적이고 연결지향적 서비스를 제공함
• IP는 배달을, TCP는 패킷의 추적 및 관리를 함
• 3-way handshaking 과정을 통해 연결을 설정하고 4-way handshaking을 통해 연결을 해제함
• 흐름 제어 및 혼잡 제어 수행
• 높은 신뢰성을 보장하지만, 속도가 느림

3 way handshake와 4 way handshake 사전 지식

▶ 포트(Port) 상태 정보

- CLOSED : 포트가 닫힌 상태

- LISTEN : 포트가 열린 상태로 연결 요청 대기 중

- SYN_RCV : SYN 요청을 받고 상대방의 응답을 기다리는 중

- ESTABLISHED : 포트 연결 상태

▶ 플래그 정보

TCP Header에는 Control Bit (플래그 비트, 6bit)가 존재하며, 각각의 bit는 'URG-ACK-PSH-RST-SYN-FIN'의 의미를 가짐

즉, 해당 위치의 BIT가 1이면 해당 패킷이 어떤 내용을 담고 있는 패킷인지를 나타냄

- SYN(Synchronize Sequence Number) / 000010

□ 연결 설정. Sequence Number를 랜덤으로 설정하여 세션을 연결하는 데 사용하며, 초기에 Sequence Number를 전송

- ACK(Acknowledgement) / 010000

□ 응답 확인. 패킷을 받았음을 의미함

- FIN(Finish) / 000001

□ 연결 해제. 세션 연결을 종료시킬 때 사용되며, 더 이상 전송할 데이터가 없음을 의미함

TCP 3 way handshake

• TCP 통신을 이용하여 데이터를 전송하기 위해 네트워크 연결을 설정하는 과정
• 양쪽 모두 데이터를 전송할 준비가 되었다는 것을 보장하고, 실제 데이터 전달이 시작하기 전에 한 쪽에서 다른 쪽이 준비되었음을 알 수 있도록 함
• 즉, TCP/IP 프로토콜을 이용해서 통신을 하는 응용 프로그램이 데이터를 전송하기 전에, 먼저 정확한 전송을 보장하기 위해 상대방 컴퓨터와 사전에 세션을 수립하는 과정을 의미

Step 1

• 클라이언트는 서버에 연결을 요청하는 SYN 패킷을 보낸 후 서버의 응답을 기다리며 SYN_SENT 상태를 유지하고, 서버는 클라이언트의 요청을 받기 전엔 Wait for Client 상태를 유지함
• 송신자가 최초로 데이터를 전송할 때는 Sequence Number를 임의의 랜덤 숫자로 지정하고, SYN 플래그 비트를 1로 설정한 세그먼트를 전송

Step 2

• 서버는 클라이언트가 보낸 SYN 패킷을 받고 SYN_RECEIVED 상태가 되고 SYN+ACK를 보내 응답
• ACK Number 필드를 Sequence Number + 1로 지정하고, SYN과 ACK 플래그 비트를 1로 설정한 세그먼트를 전송

Step 3

• 서버의 응답을 받은 클라이언트는 다시 서버에 ACK 패킷으로 응답하고, 이를 서버가 받은 후부터 세션이 생성되어 연결이 완료됨

이러한 3 단계를 거치면 클라이언트와 서버 모두 데이터를 전송하고 받을 준비가 되었다는 것을 보장하여 안전한 데이터 전송이 이루어짐

TCP 4 way handshake

• 데이터를 주고 받은 뒤 연결을 해제하는 과정

Step 1

• 클라이언트는 연결을 종료하고자 서버에 FIN 플래그를 보내고 FIN_WAIT 상태에 들어감

Step 2

• 서버는 클라이언트로부터 FIN 플래그를 받은 뒤 확인했다는 ACK 패킷을 보내고, 자신의 통신이 끝날 때까지 기다림
• 서버는 클라이언트에게 응답을 보내고 CLOSE_WAIT 상태에 들어간 후, 아직 남은 데이터가 있다면 마저 전송을 함
• 클라이언트에서는 서버에서 ACK를 받은 후에 서버가 남은 데이터 처리를 끝내고 FIN 패킷을 보낼 때까지 기다림

Step 3

• 서버가 연결을 종료할 준비가 되면, 연결을 해제할 준비가 되었다는 FIN 플래그를 클라이언트에 전송하고, 서버는 LAST_ACK 상태가 됨

Step 4

• 클라이언트는 서버에 ACK를 보내 응답하고 클라이언트의 상태는 FIN_WAIT → TIME_WAIT으로 변경
• 클라이언트의 ACK 응답을 받은 서버는 연결을 해제함
• 이때 클라이언트는 ACK를 보낸 이후 일정 시간 기다리게 되는데, 아직 서버에서 받지 못한 데이터가 유실되는 경우를 대비해 잉여 패킷을 기다리는 TIME_WAIT 상태를 일정 시간 유지함

서버는 ACK를 받은 이후 소켓을 닫고, TIME_WAIT 시간이 끝나면 클라이언트도 닫음

이러한 4 단계를 통해 클라이언트와 서버 간의 연결을 해제함

OSI 7계층이란

네트워크 프로토콜이 통신하는 구조를 7개의 계층으로 분리하여 각 계층간 상호 작용하는 방식을 정해 놓은 것

* 7계층으로 나누는 이유

통신이 일어나는 과정을 단계별로 알 수 있고, 특정한 곳에 이상이 생기면 해당 단계만 수정하면 되기 때문

Layer 1: 물리 계층

• 통신 케이블을 통해 전기적 신호를 사용하여 비트 스트림을 전송하는 계층
• 실제 장치들을 연결하기 위한 전기적 및 물리적 세부 사항을 정의함
• 데이터를 전기적인 신호로 변환해서 주고받는 기능만 함
• 데이터 전송 단위 - 비트(bit)

Layer 2 : 데이터 링크 계층

• 물리적인 네트워크 사이에 Data 전송을 담당하는 계층
• 물리계층을 통해 송수신되는 정보의 오류와 흐름을 관리하여 정보의 전달을 수행할 수 있도록 도와줌
• 맥 주소(Mac Address)를 가지고 통신
• 두 장치간의 신뢰성 있는 전송을 보장하는 계층
• 데이터 전송 단위 - 프레임(Frame)

Layer 3 : 네트워크 계층

• 데이터를 목적지까지 가장 안전하고 빠르게 전달하는 기능을 담당
• 라우터를 통해 이동할 경로를 선택하여 IP 주소를 지정하고, 해당 경로에 따라 패킷을 전달하는 것이 계층의 주 역할
• 라우팅, 흐름제어, 세그멘테이션, 오류제어 등을 수행
• 인터넷이 가능하게 만드는 계층
• 데이터 전송 단위 - 패킷(Packet)

Layer 4 : 전송 계층

• 헤더(Header)에 송수신지 포트번호를 포함하여, 데이터가 올바르게 전달될 수 있도록 하는 계층
• 패킷의 전송이 유효한지 확인, 전송 실패한 패킷을 재전송 하는 등 신뢰성 있는 통신을 보장 (보통 TCP 프로토콜을 주로 사용)
• 데이터가 왔다면, 4계층(전송계층)에서 해당 데이터를 하나로 통합하여 5계층(세션계층)으로 전달함
• 종단 간(end-to-end) 통신을 다루는 최하위 계층으로 종단 간 신뢰성 있고 효율적인 데이터를 전송
• 오류 검출, 복구, 흐름 제어, 중복검사 등을 수행
• 데이터 전송 단위 - TCP일 때 Segment, UDP일 때 Datagram

Layer 5 : 셰션 계층

• 데이터가 통신하기 위한 논리적 연결을 담당
• 네트워크 상의 양쪽 연결을 관리하고, 연결을 지속시켜주는 계층
• 통신 연결이 손실되는 경우 연결 복구 시도가 가능하며, 연결 시도 중 장시간 연결이 되지 않았다면 세션 계층의 프로토콜이 연결을 닫고 다시 연결을 시작
• TCP/IP 세션을 만들고 없애고 통신하는 사용자들을 동기화하며, 오류 복구 명령들을 일괄적으로 다뤄 통신을 하기 위한 세션을 확립, 유지, 중단하는 작업을 수행
• 세션 계층의 중요한 기능인 동기화
  • 전이중 통신 (Full Duplex) : 두 대의 단말기가 데이터를 송수신하기 위해 동시에 각각 독립된 회선을 사용하는 통신 방식
  • 반이중 통신 (Half Duplex) : 한쪽이 송신하는 동안 다른 쪽에서 수신하는 통신 방식으로, 전송 방향을 교체
• 데이터 전송 단위 - 메시지(message)

Layer 6 : 표현 계층

• 응용 계층으로부터 받은 데이터를 하위 계층인 세션 계층에 보내기 전, 통신에 적당한 형태로 변환
• 세션 계층에서 받은 데이터는 응용 계층에 맞게 변환하는 역할을 수행
• 코드 변환, 데이터 압축 및 암호화 등의 기능 수행
• 데이터 전송 단위 - 메시지(message)

Layer 7 : 응용 계층

• 응용 프로세스와 직접 관계하여 일반적인 응용 서비스를 수행 → 최상위 계층으로 사용자에게 직접적으로 보이는 부분
• 응용 프로세스 간의 정보 교환, 전자 메일, 파일 전송 등의 서비스를 제공
• ex) 웹 브라우저 Chrome, Firefox 등 / 응용 프로그램인 Skype, Office 등
• 데이터 전송 단위 - 메시지(message)

트랜잭션 (Transaction) 이란?

데이터베이스의 상태를 변환시키는 하나의 논리적 기능을 수행하기 위한 작업의 단위 또는 한꺼번에 모두 수행되어야 할 일련의 연산들을 의미

트랜잭션의 특징

1. 데이터베이스 시스템에서 병행 제어 및 회복 작업 시 처리되는 작업의 논리적 단위

2. 사용자가 시스템에 대한 서비스 요구 시 시스템이 응답하기 위한 상태 변환 과정의 작업 단위

3. 하나의 트랜잭션은 Commit 또는 Rollback 수행

트랜잭션의 성질

Atomicity(원자성)

1. 트랜잭션의 연산은 데이터베이스에 모두 반영되든지 아니면 전혀 반영되지 않아야 한다.

2. 트랜잭션 내의 모든 명령은 반드시 완벽히 수행되어야 하며, 모두가 완벽히 수행되지 않고 어느하나라도 오류가 발생하면 트랜잭션 전부가 취소되어야 한다.

Consistency(일관성)

1. 트랜잭션이 그 실행을 성공적으로 완료하면 언제나 일관성 있는 데이터베이스 상태로 변환한다.

2. 시스템이 가지고 있는 고정요소는 트랜잭션 수행 전과 트랜잭션 수행 완료 후의 상태가 같아야 한다.

Isolation(독립성,격리성)

1. 둘 이상의 트랜잭션이 동시에 병행 실행되는 경우 어느 하나의 트랜잭션 실행중에 다른 트랜잭션의 연산이 끼어들 수 없다.

2. 수행중인 트랜잭션은 완전히 완료될 때까지 다른 트랜잭션에서 수행 결과를 참조할 수 없다.

Durablility(영속성,지속성)

1. 성공적으로 완료된 트랜잭션의 결과는 시스템이 고장나더라도 영구적으로 반영되어야 한다.

트랜잭션 연산 및 상태

1) Commit연산

- 한 개의 논리적 단위(트랜잭션)에 대한 작업이 성공적으로 끝났고 데이터베이스가 다시 일관된 상태에 있을 때, 이 트랜잭션이 수행한 연산이 완료된 것을 트랜잭션 관리자에게 알려주는 연산

2) Rollback연산

- 하나의 트랜잭션 처리가 비정상적으로 종료되어 데이터베이스의 일관성을 깨뜨렸을 때, 이 트랜잭션의 일부가 정상적으로 처리되었더라도 트랜잭션의 원자성을 구현하기 위해 이 트랜잭션이 행한 모든 연산을 취소(Undo)하는 연산

- Rollback시에는 해당 트랜잭션을 재시작하거나 폐기함

3) Savepoint 연산

- 현재 작업 중인 트랜잭션을 잘게 쪼개는 역할

- 저장점(Savepoint)을 정의하면 Rollback할 때 트랜잭션에 포함된 전체 작업을 Rollback하는 것이 아니라, 현 시점에서 SAVEPOINT까지 트랜잭션의 일부만 Rollback

트랜잭션 상태

활동(Active) : 트랜잭션이 실행중인 상태

실패(Failed) : 트랜잭션 실행에 오류가 발생하여 중단된 상태

철회(Aborted) : 트랜잭션이 비정상적으로 종료되어 Rollback 연산을 수행한 상태

부분 완료(Partially Committed) : 트랜잭션의 마지막 연산까지 실행했지만, Commit 연산이 실행되기 직전의 상태

완료(Committed) : 트랜잭션이 성공적으로 종료되어 Commit 연산을 실행한 후의 상태