희연's 개발 일기장

객체 지향 프로그래밍(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) : 의존 역전 원칙
  • 고수준 모듈은 저수준 모듈의 구현에 의존해서는 안된다.

import re
def solution(new_id):
    # 아이디 제한 - 3~15길이, 소문자 숫자 - _ . 문자 사용 가능, 마침표(.)는 처음과 끝, 연속 사용 불가능
    answer = ''

    # 1번 : 대문자 -> 소문자
    one = new_id.lower()
    
    # 2번 : 소문자, 숫자, -, _, . 제외 문자 제거
    condition = '[^a-z0-9-_.]'
    two = re.sub(condition, '', one)
    
    # 3번 : .. -> .
    three = two
    while True:
        if '..' in three:
            three = three.replace('..', '.')
        else:
            break
    
    # 4번 : 첫 번째 or 마지막에 . 제거
    four = three
    if three[0] == '.':
        four = four[1:]
    if three[-1] =='.':
        four = four[:-1]

    # 5번 : 빈 문자열은 a 입력
    five = four
    if len(four)==0:
        five = 'a'
    
    # 6번 : 문자열 길이가 16이상이면, 앞의 15개 제외 뒤에 제거
    six = five
    if len(five)>=16:
        six = five[:15]
        # 맨 뒤에 . 있으면 제거
        if six[-1] == '.':
            six = six[:-1]
    
    # 7번 : 문자열 길이가 2 이하면, 문자열의 마지막 문자를 길이가 3이 될 때까지 붙이기
    seven = six
    if len(six)<=2:
        while True:
            word = six[-1]
            seven += word
            if len(seven)==3:
                break
    
    answer = seven
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/118667

queue1 = [1,2,1,2]
queue2 = [1,10,1,2]
from collections import deque
answer = 0
p1 = deque(queue1)
p2 = deque(queue2)
sum1 = sum(p1)
sum2 = sum(p2)

while True:
    if sum1 == sum2:
        break
    else:
        answer += 1
        if sum1 > sum2:
            e1 = p1.popleft()
            p2.append(e1)
            sum1 -= e1
            sum2 += e1
        else:
            e2 = p2.popleft()
            p1.append(e2)
            sum2 -= e2
            sum1 += e2
    if len(queue1)*3 < answer:
        answer = -1
        break
print(answer)

비트마스크(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)

깊이 우선 탐색 DFS(Depth First Search)

• 하나의 루트에서 탐색하다가 특정 상황에서 깊게 들어가서 확인하고 다시 돌아와서 다른 루트로 탐색하는 방법
• 백트래킹에서 사용
• 재귀, 스택으로 구현

구현 과정

• 탐색 시작 노드를 스택에 넣고 방문 처리
• 스택에서 원소를 꺼내서 방문하지 않은 인접 노드가 있을 경우 그 노드를 스택에 넣고 방문 처리
• 스택이 빌때까지 반복

DFS 문제 - 2468번 안전 영역

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

DFS 문제 - 10026번 적록색약

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

DFS 문제 - 1987번 알파벳 

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