희연's 개발 일기장

데이터베이스

• 데이터베이스를 사용하기 전까지는 파일 시스템을 이용해서 데이터를 관리
  • 파일 시스템 : 파일(데이터의 모임)을 저장 장치에 저장하고 사용하기 위한 일종의 규칙이나 체계
  • 파일 시스템의 단점 : 데이터간 불일치, 동시성 제어 제공X, 회복 기능 X, 데이터 독립성과 무결성 X, 데이터 모델링 개념이 부족
• 데이터 종속성, 데이터 중복성, 데이터 무결성 문제를 해결하기 위해 데이터 베이스 사용

데이터베이스 특징

(1) 무결성

• 여러 경로를 통해 잘못된 데이터가 발생하는 경우를 방지
• 데이터의 오류 X, constraints(제약 조건) 사용

(2) 독립성

• DB 물리적 크기, 위치 변경에도 SW에 영향을 끼치지 않는다.

(3) 보안성 

• 인가된 사용자만 DB 접근 허용해서 데이터 보호, 계정 관리, 권한 설정

(4) 중복 최소화

• 데이터베이스의 데이터를 통합해서 관리해서 자료 중복, 데이터 종속성 해결

(5) 일관성

• 하나의 데이터를 변경했을 때, 발생할 수 있는 데이터의 불일치성 배제

컴퓨터

• 하드웨어 : 컴퓨터를 구성하는 기계적 장치
• 소프트웨어 : 하드웨어의 동작을 지시하고 제어하는 명령어 집합

하드웨어

• 중앙처리장치(CPU) : 비교와 연산을 담당하는 ALU와 명령어의 해석을 담당하는 제어장치, 빠른 속도의 데이터 기억장소인 레지스터로 구성
• 주기억 장치(Main Memory) : 프로그램, 데이터, 연산의 중간 결과를 저장하는 장치
• 입출력 장치(I/O devices)
• CPU, MM, I/O 장치는 시스템 버스로 연결되어 있으며, 시스템 버스는 데이터와 명령 제어 신호를 각 장치로 실어나르는 역할을 한다.
  • 용도에 따라 데이터 버스, 주소 버스, 제어 버스로 나뉜다.

소프트웨어

• 시스템 소프트웨어 : 사용자를 위해 응용 프로그램 간의 하드웨어 사용을 제어하고 조정하는 기능을 수행하는 프로그램
  • 운영체제, 컴파일러
• 응용 소프트웨어 : 사용자의 여러 요구사항을 해결하기 위해 제공되는 프로그램
  • 워드프로세서, 스프레드시트

데이터 버스

• CPU와 기타 장치 사이의 데이터를 전달하는 통로
• 양방향 버스

주소 버스

• 데이터를 정확하게 전달하기 위해서 기억장치 주소를 정해줘야 한다.
• 단방향 버스(CPU -> I/O)

제어 버스

• CPU, Main Memory, I/O 장치에 제어 신호를 전달하는 통로
• 제어 신호 종류 : 기억장치 읽기 및 쓰기, 버스 요청 및 승인, 인터럽트 요청 및 승인, 클락, 리셋 등
• 양방향 버스

중앙처리장치(CPU) 

• 연산장치
  • 산술 연산과 논리 연산 수행. (레지스터 -> 필요한 데이터 -> ALU -> 연산 결과 -> 레지스터)
• 제어 장치
  • 명령어를 순서대로 실행할 수 있도록 제어하는 장치
  • 주기억 장치 -> 프로그램 명령 -> 제어장치에서 해독 -> 기억장치 or 연산장치 or 입출력장치로 보냄
• 레지스터
  • 명령어 주소, 코드, 연산에 필요한 데이터 등등 데이터들을 임시로 저장

CPU 동작 과정

1. 주기억 장치는 입력 장치에서 입력받은 데이터 or 보조기억장치의 프로그램을 읽어온다.

2. CPU는 프로그램 실행을 위해 CPU에 저장된 프로그램 명령어와 데이터를 읽어와 처리하고 다시 주기억장치에 저장한다.

3. 주기억 장치는 처리 결과를 보조 기억장치에 저장하거나 출력 장치로 보낸다.

테스트 주도 개발 (Test-Driven Development)

• 설계 이후 코드 개발 및 테스트 케이스를 작성하는 것이 아니라
• 테스트 케이스 작성 후, 실제 코드를 개발하여 리팩토링 하는 절차

TDD 방식의 장점

• 객체 지향적 코드
• 재설계 시간의 단축
• 디버깅 시간의 단축
• 테스트 문서 대체 가능
• 추가 구현 용이

TDD 방식의 단점

• 생산성 저하

객체 지향 프로그래밍(Object Oriented Programming)

• 프로그램 설계 방법론
• 명령형 프로그래밍 : 프로그램 상태에 대한 문장들을 작성하는 스타일
• 초기 프로그래밍 방식인 절차적 프로그래밍에서 복잡한 순서도를 가진 코드의 문제점을 해결하기 위해 구조적 프로그래밍 방식이 생겨났다.
• 하지만 데이터의 구조화는 하지 못했기 때문에 전역 네임스페이스 포화 문제, 실행 콘텍스트를 저장할 방법이 없는 문제 등등 여러 문제들이 있었다.
• 객체 지향 프로그래밍으로, 큰 문제를 작게 쪼개는 것이 아니라 먼저 작은 문제를 해결할 수 있는 객체를 만든 후, 객체를 조합해서 큰 문제를 해결하는 상향식(Bottom-up) 방식을 도입했다.
• 객체 지향 프로그램이 복잡해지면서 간결하게 정리할 수 있는 디자인 패턴이 생겼다.
  • 디자인 패턴 : 프로그래밍 형식을 정하는 일종의 약속
• 객체 지향 프로그래밍은 객체가 상태를 갖기 때문에, 변수가 존재하고 이 변수를 통해 객체가 예측할 수 없는 상태를 갖게 되어 애플리케이션 내부에서 버그를 발생시킨다는 단점이 있다. -> 함수형 프로그래밍

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

• 캡슐화(encapsulation)
  • 변수와 함수를 하나의 단위로 묶는 것
  • 해당 클래스의 인스턴스 생성을 통해 클래스 안에 포함된 멤버 변수와 메소드에 쉽게 접근할 수 있다.
  • 정보 은닉(information hiding) : 응집도를 높이고, 결합도를 떨어트려 유연함과 유지보수 향상
• 상속(inheritance)
  • 자식 클래스가 부모 클래스의 특성과 기능을 그대로 물려받는 것
  • 오버라이딩(Overriding) : 자식 클래스에서 상속받은 기능을 재정의
• 다형성(polymorphism)
  • 하나의 변수, 또는 함수가 상황에 따라 다른 의미로 해석될 수 있는 것 
  • 서브타입 다형성(subtype polymorphism)
    • 기초 클래스나 인터페이스를 구현하는 상위 클래스를 생성해서, 해당 클래스를 상속받는 다수의 하위 클래스들을 만들어 상위 클래스의 포인터나 참조 변수들이 하위 클래스의 객체를 참조하게 하는 것
    • 상속받은 상위 클래스의 메소드를 하위 클래스에서 재정의해서 사용할 수 있다. -> 오버라이딩
  • 매개변수 다형성(parametric polymorphism)
    • 타입을 매개변수로 받아 새로운 타입을 되돌려주는 기능
    • 데이터 타입이나 함수를 범용적으로 작성하여 세부 타입에 상관없이 동일하게 처리 가능
    • 제네릭(generic)
      • 지정한 타입 매개변수에 해당하는 타입만 사용하겠다고 약속하는 방식
  • 임시 다형성(ad hoc polymorphism)
    • 함수 오버로딩(function overloading)
      • 같은 이름의 함수를 매개 변수의 개수 또는 타입을 변경하여, 여러 개의 함수가 서로 다르게 행동할 수 있는 성질
      • 잦은 함수 오버로딩은 전체적은 코드의 유지보수가 어렵기 때문에, 템플릿이나 제네릭으로 대체한다.
    • 연산자 오버로딩(operator overloading)
  • 강제 다형성(coercion polymorphism)
    • 묵시적 형변환(implicit type coercion)
    • 명시적 형변환(explicit type coercion)

double a = 30;
// int형 값 30은 double으로 묵시적 형변환

double a = (double)30;
// 결과는 위와 동일하지만, (double)을 통해 int형 값 30이 double으로 변환

객체 지향적 설계 원칙

• SPR(Single Responsibility Principle) : 단일 책임 원칙
  • 클래스는 단 하나의 책임을 가진다. 클래스를 변경하는 이유는 단 하나의 이유이어야 한다.
• OCP(Open-Closed Principle) : 개방-폐쇄 원칙
  • 확장에는 열려 있고, 변경에는 닫혀 있어야 한다.
• LSP(Liskov Substitution Principle) : 리스코프 치환 원칙
  • 상위 타입의 객체를 하위 타입의 객체로 치환해도 상위 타입을 사용하는 프로그램은 정상적으로 동작해야 한다.
• ISP(Interface Segregation Princinple) : 인터페이스 분리 원칙
  • 인터페이스는 그 인터페이스를 사용하는 클라이언트를 기준으로 분리해야 한다.
• DIP(Dependency Inversion Principle) : 의존 역전 원칙
  • 고수준 모듈은 저수준 모듈의 구현에 의존해서는 안된다.

비트마스크(bitmask)

• 원소의 수가 많지 않을 때 사용
• 집합을 배열의 인덱스로 표현할 때 사용한다.
• 이진수로 비트 연산을 활용하는 방법

비트마스크 활용

• [1,2,3,4,5] 집합이 있을 때 부분 집합을 만든다.
• [1], [2], ... ,[1,2],[1,3], ... , [1,2,3], ... [1,2,3,4,5]
• 비트 마스크를 사용하면 각 요소를 인덱스로 표현하여 효율적인 접근이 가능하다.
• [1,2,3,4,5] -> 11111
• [2,3,4,5] -> 11110
• [1,2,5] -> 10011

비트의 연산

• AND, OR, NOT, XOR

쉬프트(Shift) 연산자

• << : 왼쪽 시프트, A * 2^B, 0001 -> 0010 -> 0100 -> 1000 : 1 -> 2 -> 4 -> 8
• >> : 오른쪽 시프트, A / 2^B 1000 -> 0100 -> 0010 -> 0001 : 8 -> 4 -> 2 -> 1
• N&1 : N이 짝수인지 홀수인지 구하기 위해 2로 나눈 나머지를 1과 비교하는 연산, N%2==1

삽입, 삭제, 조회

• 삽입(OR)
  • 이진수가 10101일 때, i 번째 비트 값을 1로 변경하려고 한다. i=3일 때 변경 후에는 11101
  • 10101 | 1 << 3 
  • 10101 | 01000 = 11101
• 삭제(AND, NOT)
  • 11101 & ~1 << 3
  • 11101 & 10111 = 10101
• 조회(AND)
  • 10101 & 1 << i
  • 3번째 비트 값 : 10101 & 01000 = 0
  • 4번째 비트 값 : 10101 & 10000 = 10000

비트마스킹 문제 - 1094번 막대기

https://www.acmicpc.net/problem/1094

x = int(input())
x = bin(x)
answer = 0
# 가지고 있는 막대 길이 모두 더하기
# 합이 X보다 크면 , 가장 길이 짧은 것을 절반으로 자르기
# 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같으면 위에서 자른 막대의 절반 중 하나를 버린다.

for i in x:
    if i == '1':
        answer += 1
print(answer)

비트마스킹 문제 - 11723번 집합

https://www.acmicpc.net/problem/11723

#M = 26 # 연산의 수
import sys
M = int(sys.stdin.readline())
S = 0 # 공집합

for _ in range(M):
    command = sys.stdin.readline().split()
    opt = command[0]
    if len(command)>1:
        x = int(command[1]) - 1

    if opt == 'add': # S에 x를 추가한다.
        S = S | (1 << x)
    elif opt == 'remove': # S에서 x를 제거한다.
        S = S & ~(1 << x)
    elif opt == 'check': # S에 x가 있으면 1을, 없으면 0 출력
        if S & (1 << x) == 0:
            print(0)
        else:
            print(1)
    elif opt == 'toggle': # S에 x가 있으면 x 제거, 없으면 x 추가
        S = S ^ (1 << x)
    elif opt == 'all': # S를 {1,2, ..., 20} 으로 바꾼다.
        S = (1 << 20)-1
    elif opt == 'empty': # S를 공집합으로 바꾼다
        S = 0

다익스트라(Dijkstra) 알고리즘

• 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘
• 음수의 가중치가 없을 때 사용 -> 음수 가중치 있는 경우 벨만포드 알고리즘

다익스트라 알고리즈 구현 과정 - O(N^2)

1. 출발 노드 설정

2. 출발 노드 기준으로 노드의 각 최소 비용 저장

3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택

4. 해당 노드를 거쳐서 특정 노드로 가는 경우를 고려해서 최소 비용 갱신

5. 3~4번 반복

다익스트라 알고리즈 구현 과정 - 힙 사용 O(N*logN)

다익스트라 문제 - 1753번 최단경로

https://www.acmicpc.net/problem/1753

import heapq
import sys
input = sys.stdin.readline
#V, E = 5, 6  # 정점의 개수, 간선의 개수
V, E = map(int, input().split())
K = int(input())
#k = 1  # 시작 정점의 번호
inf = float('inf')
graph = [[] for _ in range(V + 1)]
distance = [inf]*(V+1) # 가중치 테이블 dp
pq = []  # 우선순위 큐

for _ in range(E):
    u, v, w = map(int, input().split())  # u에서 v로 가는 가중치 w 간선
    graph[u].append((v, w))

def dijkstra(start):
    distance[start] = 0
    heapq.heappush(pq, [0, start])  # 거리, 시작 정점 번호

    while pq: # 우선순위 큐를 사용해서 가장 최단 거리의 노드 고르기
        dist, now = heapq.heappop(pq)

        # 현재 노드가 이미 방문된 기록이 있으면 무시
        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(pq, [cost, i[0]])

dijkstra(K)

for i in distance[1:]:
    if i == inf:
        print("INF")
    else:
        print(i)

플로이드 와샬(Floyd Warshall)

• 모든 정점에서 모든 정점으로의 최단 경로를 구하기 위해 사용하는 알고리즘
• 무방향, 방향 그래프에서 사용 가능하지만 음수 사이클이 있으면 X

플로이드 와샬 구현 방법

• 일단 자기 자신은 0, 간선 1개로 얻을 수 있는 값들로 2차원 배열(최단 거리 테이블)을 만든다.
• x에서 y로 가는 최소 비용 vs x에서 노드1으로 가는 최소 비용 + 노드 1에서 y로 가는 최소 비용
  • ex. D[2, 3] = min((D[2,1] + D[1,3]), D[2,3])
• 1부터 n까지의 노드들 최소 비용 갱신

플로이드 와샬 문제 - 11404번 플로이드

https://www.acmicpc.net/problem/11404

#n = 5 # 도시의 개수
#m = 14 # 버스의 개수
n = int(input())
m = int(input())
inf = float('inf')
dp = [[inf for _ in range(n+1)] for _ in range(n+1)] # 최소 비용 테이블
# 버스의 정보 : 시작 도시 a, 도착 도시 b, 필요 비용 c
for _ in range(m):
    a, b, c = map(int, input().split())
    dp[a][b] = min(c, dp[a][b])

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i == j: # 자기 자신은 X
                dp[i][j] = 0
            else:
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])

for x in range(1, n+1):
    for y in range(1, n+1):
        if dp[x][y] == inf:
            print(0, end=' ')
        else:
            print(dp[x][y], end=' ')
    print()

위상 정렬(Topological Sort)

• 방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 정렬
• ex. 선수 과목 : 특정 과목에 선수 과목이 있을 경우 선수 과목부터 수강해야 하는 상황에서 위상정렬으로 순서 찾기 
• 그래프 순환이 존재하지 않아야 한다.
• DAG(Directed Acyclic Graph) : 사이클이 존재하지 않는 방향 그래프

위상 정렬의 수행 과정

1. 자기 자신을 가리키는 변이 없는 꼭짓점을 찾는다.

2. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제한다.

3. 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료한다.

위상 정렬 알고리즘

1. 맨 처음 모든 간선을 읽으며 indegree 테이블을 채운다.

2. indegree가 0인 정점들을 모두 큐에 넣는다.

3. 큐에서 정점을 꺼내 위상 정렬 결과에 추가한다.

4. 해당 정점으로부터 연결된 모든 정점의 indegree 값ㅇ르 1 감소시키고, indegree가 0이 되면 정점을 큐에 추가한다.

5. 큐가 빌 때까지 3,4번을 반복

위상 정렬 문제 - 2252번 줄 세우기 

https://www.acmicpc.net/problem/2252

from collections import deque
#n, m = 3, 2 # 학생의 번호 1~n, m는 키를 비교환 횟수
n, m = map(int, input().split())
inDegree = [0]*(n+1)
graph = [[] for i in range(n+1)]
queue = deque()
answer = []
arr = []
# 1 -> 3
# 2 -> 3

# 키를 비교한 두 학생의 번호 a,b (학생 a가 b앞에)
# 그래프에 정점끼리 연결된 정보들 입력
for _ in range(m):
    a, b = map(int, input().split())
    arr.append([a,b])

for a, b in arr:
    inDegree[b] += 1
    graph[a].append(b)

for i in range(1, n+1):
    if inDegree[i] == 0:
        queue.append(i)

while queue:
    top = queue.popleft() # 큐 최상위 정점
    for b in graph[top]:
        inDegree[b] -= 1
        if inDegree[b] == 0:
            queue.append(b)
    answer.append(top)

print(*answer)