그래프

• 그래프란 객체의 일부 쌍들이 연관되어 있는 객체 집합 구조를 말한다.

해밀턴 경로

• 해밀턴 경로는 각 정점을 한 번 씩 방문하는 무향 또는 유향 그래프 경로를 말한다.
• 오일러 경로의 차이점을 들자면 경로는 간선을 기준으로 하고 해밀턴 경로는 정점을 기준으로 한다는 점이다. 그러나 해밀턴 경로를 찾는 문제는 최적 알고리즘이 없는 np-완전 문제다.
• 원래의 출발점으로 돌아오는 경로는 해밀턴 순환이라고 부르는데 이 중에서도 특히 최단거리를 찾는 문제는 알고리즘 분야에서는 외판원 문제로 유명하다. 외판원 문제는 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 문제, 즉 최단 거리인 해밀턴 순환을 찾는 문제이며, np-난해 문제이다.

그래프 순회

• 그래프 순회란 그래프 탐색이라고도 불리우며 그래프의 각 정점을 방문하는 과정을 말한다.
• 그래프 순회에는 크게 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)의 2가지 알고리즘이 있다.
• DFS는 주로 스택으로 구현하거나 재귀로 구현하며, 이후에 살펴볼 백트래킹을 통해 뛰어난 효용을 보인다. 반면 BFS는 큐로 구현하며, 그래프의 최단 경로를 구하는 문제 등에 사용된다.
• 그래프를 표현하는 방법에는 크게 인접행렬과 인접리스트 2가지 방법이 있는데 여기서는 인접 리스트로 표현한다. 인접 리스트는 출발 노드를 키로, 도착 노드를 값으로 표현할 수 있다.

graph = {
    1:[2, 3, 4],
    2:[5],
    3:[5],
    4:[],
    5:[6, 7],
    6:[],
    7:[3]
}

깊이 우선 탐색(DFS)

• 재귀를 통해 DFS를 구현해보면 다음과 같다.

def DFS(v, discovered=[]):
    discovered.append(v)
    for w in graph[v]:
        if w not in discovered:
            discovered = DFS(w, discovered)
    return discovered

• 스택을 이용한 반복 결과로 DFS를 구현하면 다음과 같다. 코드가 빈틈없어 보이는 재귀 구현에 비해 우아함은 떨어지지만 좀 더 직관적이라 이해하기는 훨씬 더 쉽다. 실행 속도 또한 더 빠른 편이다.

def DFS(start_v):
    discovered = []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in discovered:
            discovered.append(v)
            for w in graph[v]:
                stack.append(w)
    return discovered

너비 우선 탐색(BFS)

• 스택을 사용하는 DFS와 달리 BFS를 반복 구조로 구현할 때는 큐를 이용한다. 최적화를 위해 데크 같은 자료형을 사용해 보는 것을 고민해볼 수 있다.

def BFS(start_v):
    discovered = [start_v]
    queue = [start_v]
    while queue:
        v = queue.pop(0)
        for w in graph[w]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered

• BFS는 재귀로 동작하지 않는다. 큐를 이용한 반복 구현만 가능하다.

백트래킹

• 백트래킹은 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기해 정답을 찾아가는 범용적인 알고리즘으로 제약 충족 문제에 특히 유용하다.
• 백트래킹은 DFS와 같은 방식으로 탐색하는 모든 방법을 뜻하며 DFS는 백트래킹의 골격을 이루는 알고리즘이다. 백트래킹은 주로 재귀로 구현하며 알고리즘 마다 DFS 변형이 조금씩 일어나지만 기본적으로 모두 DFS의 범주에 속한다.
• 브루트 포스와 유사하지만 한번 방문 후 가능성이 없는 경우엔 후보를 포기한다는 점에서 더 우아한 방식이다.

제약 충족 문제

• 제약 충족 문제란 수많은 제약 조건을 충족하는 상태를 찾아내는 수학문제를 일컫는다.
• 백트래킹은 제약 충족 문제를 풀이하는 데 필수적인 알고리즘이다.

섬의 개수

• 1을 육지로 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라.

예제

• 입력:

11110

11010

11000

00000

• 출력: 3

풀이 1. DFS로 그래프 탐색

• 입력값이 정확히 그래프는 아니지만 사실상 동서남북이 모두 연결된 그래프로 가정하고 동일한 형태로 처리할 수 있다.
• 육지인 곳을 찾아 진행하다가 육지를 발견하면 그때부터 DFS()를 호출해 탐색을 시작한다.
• DFS()는 동서남북을 모두 탐색하면서 재귀 호출한다. 함수 상단에 육지가 아닌 곳은 return으로 종료 조건을 설정해둔다. 이미 방문한 곳은 0으로 마킹한다.
• dfs 함수를 빠져나온 후에는 해당 위치에서 탐색할 수 있는 모든 육지를 탐색한 것이므로 카운트를 1 증가시킨다.

def solution(grid):
    def dfs(i, j):
        if i < 0 or i >= len(grid) or \
           j < 0 or j >= len(grid[0]) or \
           grid[i][j] != '1':
            return

        grid[i][j] = 0

        #동서남북 탐색
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)

    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(i, j)
                # 모든 육지 탐색 후 카운트 1 증가
                count += 1
    return count

전화번호 문자 조합

• 2에서 9까지 숫자가 주어졌을 때 전화번호로 조합 가능한 모든 문자를 출력하라

예제

• 입력: '23'
• 출력: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

풀이 1. 모든 조합 탐색

• 이 문제는 전체를 탐색하여 풀이할 수 있다. 항상 전체를 탐색해야하고 가지치기 등으로 최적화할 수 있는 문제는 아니기 때문에 어떻게 풀이하든 결과는 비슷하다. 모두 조합하는 형태로 전체를 탐색한 후 백트래킹하면서 결과를 조합한다.

def solution(digits):
    def dfs(index, path):
        # 끝까지 탐색하면 백트래킹
        if len(path) == len(digits):
            result.append(path)
            return

        # 입력값 자릿수 단위 반복
        for i in range(index, len(digits[i])):
            dfs(i + 1, path + j)

    # 예외 처리
    if not digits:
        return []

    dic = {'2': 'abc', '3': 'def', '4': 'ghi', '5'L 'jkl',
          '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    result = []
    dfs(0, "")

조합의 합

• 숫자 집합 cadidates를 조합하여 합이 target이 되는 원소를 나열하라. 각 원소는 중복으로 나열 가능하다.

예제

• 입력: candidates = [2, 3, 6, 7], target = 7
• 출력: [[7], [2, 2, 3]]

풀이 1. DFS로 중복 조합 그래프 탐색

• target을 만들 수 있는 모든 번호 조합을 찾는 문제이다. DFS와 백트래킹으로 풀이할 수 있다.
• 모든 중복 조합에서 찾아야 하기 때문에, 이 그림과 같이 항상 부모의 값부터 시작하는 그래프로 구성할 수 있다.
• DFS의 종료조건은 2가지 경우다. csum < 0인 경우, csum == 0인 경우

def solution(candidates, target):
    result = []

    def dfs(csum, index, path):
        # 종료 조건
        if csum < 0:
            return
        if csum == 0:
            result.append(path)
            return

        for i in range(index, len(candidates)):
            dfs(csum - candidates[i], i, path + [candidates[i]])

    dfs(target, 0, [])
    return result

• 입력값에 0이 포함되어 있다면 종료조건을 만족할 수 없기 때문에 무한히 깊이 탐색을 시도하게 된다. dfs(csum - candidates[i], 0, path + [candidates[i]])로 바꿔주면 항상 첫번째 값부터 탐색을 시도하기 때문에 순열로 풀이할 수 있다.

부분 집합

• 모든 부분 집합을 리턴하라.

예제

• 입력: nums = [1, 2, 3]
• 출력: [[3], [1], [2], [1, 2, 3], [1, 3], [2, 3], [1, 2], []]

풀이 1. 트리의 모든 DFS 결과

• 경로 path를 만들어 나가면서 인덱스를 1씩 증가하는 형태로 깊이 탐색한다. 별도의 종료 조건 없이 탐색이 끝나면 저절로 함수가 종료되게 한다.
• 부분 집합은 모든 탐색의 경로가 결국 정답이 되므로 다음과 같이 탐색할 때마다 매번 결과를 추가하면 된다.

def solution(nums):
    result = []

    def dfs(index, path):
        # 매번 결과 추가
        result.append(path)

        # 경로를 만들면서 DFS
        for i in range(index, len(nums)):
            dfs(i + 1, path + [nums[i]])

    dfs(0, [])
    return result

일정 재구성

• [from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행일정을 구성하라. 여러 일정이 있는 경우 사전 어휘 순으로 방문한다.

예제

• 입력: [['MUC', 'LHR'], ['JFK', 'MUC'], ['SFO', 'SJC'], ['LHR', 'SFO']]
• 출력: ['JFK', 'MUC', 'LHR', 'SFO', 'SJC']

풀이 1. DFS로 일정 그래프 구성

• 여행일정을 그래프로 구성하여 DFS로 문제를 풀이한다.
• 어휘 순으로 방문해야 하므로 일단 그래프를 구성한 후에 다시 꺼내 정렬한다.

def solution(tickets):
    graph = collections.defaultdict(list)
    # 그래프 순서대로 구성
    for a, b in sorted(tickets):
        graph[a].append(b)

    route = []
    def dfs(a):
        # 첫번째 값을 읽어 어휘 순 방문
        while graph[a]:
            dfs(graph[a].pop(0))
        route.append(a)

    dfs('JFK')
    # 다시 뒤집어 어휘 순 결과로
    return route[::-1]

풀이 2. 일정 그래프 반복

• 재귀가 아닌 스택을 이용한 반복으로 처리한다.

def solution(tickets):
    graph = collections.defaultdict(list)

    for a, b in sorted(tickets):
        graph[a].append(b)

    route, stack = [], ['JFK']
    while stack:
        # 반복으로 스택을 구성하되 막히는 부분에서 풀어내는 처리
        while graph[stack[-1]]:
            stack.append(graph[stack[-1]].pop(0))
        route.append(stack.pop())

    return route[::-1]

코스 스케줄

• 0을 완료하기 위해서는 1을 끝내야 한다는 것을 [0, 1] 쌍으로 표현하는 n개의 코스가 있다. 코스 개수 n과 이 쌍들을 입력으로 받았을 때 모든 코스가 완료 가능한지 판별하라.

예제

• 입력: 2, [[1, 0]]
• 출력: true

풀이 1. DFS로 순환 구조 판별

• 이 문제는 graph가 순환 구조인지를 판별하는 문제로 풀이할 수 있다. 순환 구조라면 계속 뱅글뱅글 맴돌게 될 것이고 해당 코스는 처리할 수 없기 때문이다.
• 이미 방문했던 곳을 중복 방문한다면 순환 구조로 간주할 수 있고, 이 경우 False를 리턴하고 종료할 수 있다.
• 순환이 아닌데 순환으로 판단할 수 있으므로 한번 경로가 탐색이 끝난 후에는 traced.remove(i)로 노드가 모두 삭제되어야 한다.

def solution(numCourses, prerequisites):
    graph = collections.defaultdict(list)
    # 그래프 구성
    for x, y in prerequisites:
        graph[x].append(y)

    traced = set()

    def dfs(i):
        # 순환 구조이면 False
        if i in traced:
            return False

        traced.add(i)
        for y in graph[i]:
            if not dfs(y):
                return False
        # 탐색 종료 후 순환 노드 삭제
        traced.remove(i)

        return True

    # 순환 구조 판별
    for x in list(graph):
        if not dfs(x):
            return False

    return True

풀이 2. 가지치기를 이용한 최적화

• 앞서 풀이한 DFS 풀이는 순환이 발견될 때 까지 모든 자식 노드를 탐색하는 구조로 되어 있다. 따라서 한 번 방문했던 그래프는 두번 이상 방문하지 않도록 무조건 True로 리턴하는 구조로 개선한다면 탐색시간을 획기적으로 줄일 수 있을 것이다.

def solution(numCouses, prerequsites):
    graph = collections.defaultdict(list)
    # 그래프 구성
    for x, y in prerequisites:
        graph[x].append(y)

    traced = set()
    visited = set()

    def dfs(i):
        # 순환구조이면 False
        if i in traced:
            return False

        # 이미 방문했던 노드라면 True
        if i in visited:
            return True

        traced.add(i)
        for y in graph[i]:
            if not dfs(y):
                return False

        traced.remove(i)
        visited.add(i)

        return True

    for x in list(graph):
        if not dfs(x):
            return False

    return True

연결리스트

• 연결리스트는 데이터 요소의 선형 집합으로 데이터의 순서가 메모리에 물리적인 순서대로 저장되지는 않는다.

연결리스트는 가장 기본이 되는 대표적인 선형 자료구조 중 하나로 다양한 추상 자료형 구현이 기반이 된다. 동적으로 새로운 노드를 삽입하거나 삭제하기가 간편하며, 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리도 쉽다.

특정 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야 하므로 상수 시간에 접근할 수 없다. 탐색에는 O(n)이 소모된다. 반면 삭제, 추출하는 작업은 O(1)에 가능하다.

펠린드롬 연결 리스트

• 연결리스트가 펠린드롬 구조인지 판별하라.

예제

• 입력: 1-> 2
• 출력: false

풀이 1. 리스트 변환

• 펠린드롬 여부를 판별하기 위해서는 앞뒤로 모두 추출할 수 있는 자료구조가 필요하다. 따라서 이 문제는 연결리스트를 파이썬의 리스트로 변환하여 리스트의 기능을 이용하면 쉽게 풀이 할 수 있을 것이다.

def solution(head):
    q = []

    if not head:
        return False

    node = head
    # 리스트 변환
    while node is not None:
        q.append(node.val)
        node = node.next

    # 펠린드롬 판별
    while len(q) > 1:
        if q.pop(0) != q.pop():
            return False

    return True

풀이 2. 데크를 이용한 최적화

• 리스트에선 q.pop(0)은 O(n) 시간복잡도를 가진다. 따라서 최적화를 위해선 데크가 필요하다.

def solution(head):
    q = collections.deque()

    if not head:
        return False

    node = head
    # 리스트 변환
    while node is not None:
        q.append(node.val)
        node = node.next

    # 펠린드롬 판별
    while len(q) > 1:
        if q.popleft() != q.pop():
            return False

    return True

풀이 3. 런너를 이용한 우아한 풀이

• 2개의 노드씩 건너뛰는 빠른 런너와 노드 1개씩 건너뛰는 느린 런너를 각각 출발시키면, 빠른 런너가 끝에 다다를때 느린 런너는 정확히 중간 지점에 도달하게 될 것이다. 느린 런너는 중간까지 이동하면서 역순으로 연결리스트 rev를 만들어간다. 이제 중간에 도달한 느린 런너가 나머지 경로를 이동할 때 역순으로 만든 연결 리스트의 값들과 일치하는지 확인해나가면 된다.

def solution(head):
    rev = None
    slow = fast = head
    # 런너를 이용해 역순 연결리스트 구성
    while fast and fast.next:
        fast = fast.next.next
        rev, rev.next, slow = slow, rev, slow.next
    # 노드의 갯수가 홀수 일 때 slow가 중앙을 벗어나냐함
    if fast:
        slow = slow.next

    while rev and rev.val == slow.val:
        slow, rev = slow.val, rev.val

    return not rev

런너 기법
런너는 연결 리스트를 순회할 때 2개의 포인터를 동시에 사용하는 기법이다. 한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있다.

두 정렬 리스트의 병합

• 정렬되어 있는 두 연결 리스트를 합쳐라.

예제

• 입력: 1->2->4, 1->3->4
• 출력: 1->-1>2->3->4->4

풀이 1. 재귀 구조로 연결

• 정렬된 리스트라는 점이 중요하다. 병합정렬처럼 하나씩 비교하면서 리턴한다.

def solution(l1, l2):
    if (not l1) or (l2 and l1.val > l2.val):
        l1, l2 = l2, l1
    if l1:
        l1.next = self.solution(l1,next, l2)
    return l1

역순 연결리스트

• 연결 리스트를 뒤집어라

예제

• 입력: 1->2->3->4->5->NULL
• 출력: 5->4->3->2->1->NULL

풀이 1. 재귀구조로 뒤집기

• 연결리스트를 뒤집는 문제는 매우 일반적이면서도 활용더가 높은 문제로, 실무에서도 빈번하게 쓰인다.

def solution(head):
    def reverse(node, prev = None):
        if not node:
            return prev
        next, node.next = node.next, prev
        return reverse(next, node)

    return reverse(head)

풀이 2. 반복구조로 뒤집기

def solution(head):
    node, prev = head, None

    while node:
        next, node.next = node.next, head
        prev, node = node, next

    return prev

두 수의 덧셈

• 역순으로 저장된 연결 리스트의 숫자를 더하라.

예제

• 입력: (2->4->3) + (5->6->4)
• 출력: 7->0->8

풀이 1. 전가산기 구현

• 전가산기는 입력값 A와 B, 자리올림수 3가지 입력으로 합과 다음 자리 올림수 여부를 결정한다. 입력값 A, B는 오른쪽으로는 XOR 게이트를 통과한 결과가 나아가고, 아래로는 AND 게이트를 통과한 결과가 나아간다. 그렇게 합과 다음 자리 올림수 위치에 도달한 결과가 진리표다. 덧셈 연산을 수행하는 논리회로의 원리다.

def solution(l1, l2):
    root = head = ListNode(0)

    carry = 0
    while l1 or l2 or carry:
        sum = 0
        # 두 입력값의 합 계산
        if l1:
            sum += l1.val
            l1 = l1.next
        if l2:
            sum += l2.val
            l2 = l2.next

        # 몫(자리 올림수)과 나머지(값) 계산
        carry, val = divmod(sum + carry, 10)
        head.next = ListNode(val)
        head = head.next

    return root.next    

페어의 노드 스왑

• 연결리스트를 입력받아 페어 단위로 스왑하라

예제

• 입력: 1->2->3->4
• 출력: 2->1->4->3

풀이 1. 값만 교환

• 연결리스트의 노드를 변경하는 게 아닌 노드 구조는 그대로 유지하 되 값만 병경하는 방법이다. 실용성과는 다소 거리가 있다.

def solution(head):
    cur = head

    while cur and cur.next:
        # 값만 교환
        cur.val, cur.next.val = cur.next.val, cur.val
        cur = cur.next.next

    return head

풀이 2. 반복구조로 풀이

• 1->2->3->4->5->6인 연결리스트가 있을 경우 3->4를 4->3으로 바꾸려면 그 앞인 2가 가리키는 연결리스트와 5로 연결되는 연결리스트도 다 같이 변경해야 한다.

• b = a.next
  a.next = b.next
  b.next = a

• 이처럼 b가 a를 가리키고 a는 b의 다음을 가리키도록 변경한다. 그러나 아직 a의 이전 노드가 b를 가리키지는 못한다.

• prev.next = b
  a = a.next
  prev = prev.next.next

• a의 이전 노드 prev가 b를 가리키게 하고 다음 비교를 위해 prev는 두칸 앞으로 이동한다. 그리고 다시 다음번 교환을 진행한다.

def solution(head):
    root = prev = ListNode(None)
    prev.next = head
    while head and head.next:
        # b가 a(head)를 가리키도록 할당
        b = head.next
        head.next = b.next
        b.next = head

        # prev가 b를 가리키도록 할당
        prev.next = b

        # 다음번 비교를 위해 이동
        head = head.next
        prev = prev.next.next

    return root.next

풀이 3. 재귀 구조로 스왑

• 재귀로는 훨씬 더 깔끔하게 풀이할 수 있다.

def solution(head):
    if head and head.next:
        p = head.next
        # 스왑된 값 리턴 받음
        head.next = solution(p.next)
        p.next = head
        return p
    return head

홀짝 연결 리스트

• 연결리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성하라. 공간복잡도 O(n), 시간복잡도 O(n)에 풀이하라.

예제

• 입력: 1->2->3->4->5->NULL
• 출력: 1->3->5->2->4->NULL

풀이 1. 반복구조로 홀짝 노드 처리

• 이런 문제는 제약이 없을 경우 연결리스트를 리스트로 바꾸고 파이썬 리스트가 제공하는 슬라이싱과 같은 다양한 함수를 사용하면 좀 더 쉽고 직관적이며 또한 빠르게 풀 수 있다. 하지만 우아하지 않다.

def solution(head):
    # 예외 처리
    if head is None:
        return None

    odd = head
    even = head.next
    even_head = head.next

    # 반복하면서 홀짝 노드 처리
    while even and even.next:
        odd.next, even.next = odd.next.next, even.next.next
        odd, even = odd.next, even.next

    # 홀수 노드의 마지막을 짝수 헤드로 연결
    odd.next = even_head
    return head

역순 연결 리스트 2

• 인덱스 m에서 n까지를 역순으로 만들어라. 인덱스 m은 1부터 시작한다.

예제

• 입력: 1->2->3->4->5->NULL, m = 2, n = 4
• 출력: 1->4->3->2->5->NULL

풀이 1. 반복 구조로 노드 뒤집기

def solution(head, m, n):
    # 예외 처리
    if not head or m == n:
        return head

    root = start = ListNode(None)
    root.next = head
    # start, end 지정
    for _ in range(m - 1):
        start = start.next
    end = start.next

    # 반복하면서 뒤집기
    for _ in range(n - m):
        tmp, start.next, end.next = start.next, end.next, end.next.next
        start.next.next = tmp

    return root.next

스택, 큐

• 스택과 큐는 프로그래밍이라는 개념이 탄생할 때 부터 사용된 가장 고전적인 자료구조 중 하나로 그 중에서도 스택은 거의 모든 애플리케이션을 만들 때 사용되는 자료구조다.
• 스택은 후입선출, 큐는 선입선출
• 파이썬은 리스트가 사실상 스택의 모든 연산을 지원하고 큐는 데크 자료구조형을 사용한다.
• 꽉 찬 스택에 요소를 삽입하고자 할 때 스택에 요소가 넘쳐서 에러가 발생하는 것을 스택오버플로우라고 한다.

유효한 괄호

• 괄호로 된 입력값이 올바른지 판별하라.

예제

• 입력: ()[]{}
• 출력: True

풀이 1. 스택 일치 여부 판별

• 스택에 푸시를 하고, 스택에서 팝한 결과가 매핑 테이블 결과와 매칭되는지 확인하면 된다.

def solution():
    stack = []
    table = {
        ')':'(',
        '}':'{'.
        ']':'['
    }

    # 스택 이용 예외 처리 및 일치 여부 판별
    for char in s:
        if char not in table:
            stack.append(char)
        elif not stack or table[char] != stack.pop():
            return False

    return len(stack) == 0

중복 문자 제거

• 중복된 문자를 제외하고 사전식 순서로 나열하라.

예제

• 입력: 'bcabc'
• 출력: 'abc'

풀이 1. 스택을 이용한 문자제거

• 문자를 앞에서부터 하나씩 차례대로 쌓아나간다. 만약 현재 문자 char가 스택에 쌓여있는 문자이고 뒤에 다시 붙일 문자가 남아 있다면 쌓아둔걸 꺼내서 없앤다. 카운팅에는 collections.Counter()를 사용한다.

def solution(s):
    counter, seen, stack = collections.Counter(s), set(), []

    for char in s:
        counter[char] -= 1
        if char in seen:
            continue

        # 뒤에 붙일 문자가 남아 있다면 스택에서 제거
        while stack and char < stack[-1] and counter[stack[-1]] > 0:
            seen.remove(stack.pop())
        stack.append(char)
        seen.add(char)

    return ''.join(stack)

일일 온도

• 매일의 화씨 온도 리스트 T를 입력받아서, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지를 출력하라.

예제

• 입력: [73, 74, 75, 71, 69, 72, 76, 73]
• 출력: [1, 1, 4, 2, 1, 1, 0, 0]

풀이 1. 스택 값 비교

• 빗물 트래핑과 유사한 방법으로 풀이할 수 있다.
• 현재의 인덱스를 계속 스택에 쌓아두다가, 이전보다 상승하는 지점에서 현재 온도와 스택에 쌓아둔 인덱스 지점의 온도 차이를 비교해서 더 높다면 다음과 같이 스택의 값을 pop()으로 꺼내고 현재 인덱스와 스택에 쌓아둔 인덱스의 차이를 정답으로 처리한다.

def solution(T):
    answer = [0] * len(T)
    stack = []
    for i, cur in enumerate(T):
        # 현재 온도가 스택값보다 높다면 정답 처리
        while stack and cur > T[stack[-1]]:
            last = stack.pop()
            answer[last] = i - last
        stack.append(i)

    return answer

데크, 우선순위 큐

데크

• deque는 double ended queue의 줄임말로 글자 그대로 양쪽끝을 모두 추출할 수 있는 큐를 일반화한 형태의 추상자료형이다.
• collections.deque는 이중 연결 리스트로 구현되어 있다.

우선순위 큐

• 우선순위 큐는 어떠한 특정 조건에 따라 우선순위가 가장 높은 요소가 추출되는 자료형이다. 대표적으로 최댓값 추출을 들 수 있다.
• 정렬 알고리즘을 사용하면 우선순위 큐를 만들 수 있다. 단순 정렬보다는 힙 정렬등의 좀 더 효율적인 방법을 활용한다.
• 최단경로를 탐색하는 다익스트라 알고리즘 등 우선순위 큐는 다양한 분야에 활용되며 힙 자료구조와도 관련이 깊다.

k개 정렬 리스트 병합

• k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합하라.

예제

• 입력: [1->4->5, 1->3->4, 2->6]
• 출력: 1->1->2->3->4->4->5->6

풀이 1. 우선순위 큐를 이용한 리스트 병합

• 파이썬에서는 대부분의 우선순위 큐 풀이에 거의 항상 heapq 모듈을 사용한다.
• 연결리스트 노드를 heap에 push한 뒤, heappop을 이용해 최소 노드를 추출해서 result에 붙인다. 그 후 다음 노드를 다시 heap에 push한다.

def solution(list):
    root = result = ListNode(None)
    heap = []

    # 각 연결리스트의 루트를 힙에 저장
    for i in range(len(lists)):
        if lists[i]:
            heapq.heappush(heap, (lists[i].val, i, lists[i]))

    # 힙 추출 이후 다음 노드는 다시 저장
    while heap:
        node = heapq.heappop(heap)
        idx = node[1]
        result.next = node[2]

        result = result.next
        if result.next:
            heapq.heappush(heap, (result.next.val, idx, result.next))

    return root.next

출처: 파이썬 알고리즘 인터뷰

배열

• 배열은 값 또는 변수 엘리먼트의 집합으로 구성된 구조로, 하나 이상의 인덱스 또는 키로 식별된다.

자료구조는 크게 메모리 공간 기반의 연속 방식과 포인터 기반의 연결 방식으로 나뉜다. 배열은 연속방식의 가장 기본이 되는 자료형이다. 연결 방식의 가장 기본이 되는 자료형은 연결 리스트다. 추상자료형(abstract data type)의 실제 구현 대부분은 배열 또는 연결리스트를 기반으로 한다. 스택은 연결리스트로 구현하고 큐는 배열로 구현한다.

배열은 어느 위치에나 O(1)에 조회가 가능하다는 장점이 있다. 그러나 배열은 고정된 크기 만큼의 연속된 메모리 할당이므로 너무 작은 영역을 할당하여 모자라거나 너무 많은 영역을 할당해서 낭비가 될 때도 있다. 이러한 고민을 해결하고자 크기를 지정하지 않고 자동으로 리사이징하는 배열인 동적 배열이 등장했다. 파이썬에선 리스트가 바로 동적 배열 자료형이다.

동적 배열의 원리는 미리 초깃값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면 늘려주고 모두 복사하는 식이다. 대개는 더블링이라 하며 2배씩 늘려주게 된다.

동적 배열은 정적 배열과 달리 크기를 지정할 필요가 없어 매우 편리하게 활용할 수 있으며 조회 또한 기존의 배열과 동일하게 O(1)에 가능하다 그러나 더블링이 필요할 만큼 공간이 차게 되면 기존 데이터를 복사하는 작업이 필요하므로 O(n) 비용이 발생한다.

두수의 합

• 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라.

예제

• 입력: nums = [2, 7, 11, 5], target = 9
• 출력: [0, 1]

풀이 1. 브루트 포스로 계산

• 배열을 2번 반복하면서 모든 조합을 더해서 일일이 확인해보는 무차별 대입 방식인 브루트 포스를 이용한다.
• 이 경우 시간복잡도는 O(n^2)이다.

def solution(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

풀이 2. in을 이용한 탐색

• target - n이 존재하는지 탐색하는 문제로 변경해보자.
• in의 시간복잡도는 O(n)이고 따라서 전체 시간복잡도는 이전과 동일하지만 in 연산이 더 가볍고 빠르다.

def solution(nums, target):
    for i, n in enumerate(nums):
        if target - n in nums[i + 1:]:
            returm [nums.index(n), nums[i+1:].index(target - n) + (i + 1)]

풀이 3. 첫번째 수를 뺀 결과 키 조회

def solution(nums, target):
    nums_map = {}
    # 키와 값을 바꿔서 딕셔너리로 저장
    for i, num in enumerate(nums):
        nums_map[num] = i

    # 타겟에서 첫번째 수를 뺀 결과를 키로 조회
    for i, num in enumerate(nums):
        if target - n in nums_map and i != nums_map[target - num]:
            return [i, nums_map[target - n]]

• 딕셔너리는 조회가 평균적으로 O(1)에 가능하다. 전체 시간복잡도는 O(n)이 된다

빗물 트래핑

• 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.

예제

• 입력: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
• 출력: 6

풀이 1. 투 포인터를 최대로 이동

• 투 포인터나 스택을 이용하면 O(n)으로 풀이가 가능하다.
• 가장 높은 막대를 살펴본다. 높고 낮음과 무관하게 전체 부피에 영향을 끼치지않으면서 그저 왼쪽과 오른쪽을 가르는 장벽 역할을 한다.
• 최대 높이의 막대까지 각각 좌우 기둥 최대 높이 left_max, right_max가 현재 높이와의 차이만큼 물 높이 volume을 더해 나간다.
• 낮은 쪽은 그만큼 항상 채워질 것이기 때문에 좌우 어느쪽이든 낮은 쪽은 높은 쪽을 향해서 포인터가 가운데로 점점 이동한다. 오른쪽이 크다면 left += 1로 이동하고 왼쪽이 크다면 right -= 1로 오른쪽이 이동한다. 이렇게 하면 가장 높이가 높은 막대, 즉 최대 지점에서 좌우 포인터가 만나게 되며 O(n)에 풀이가 가능하다.

def solution(height):
    if not height:
        return 0

    volume = 0
    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]

    while left < right:
        left_max, right_max = max(height[left], left_max), max(height[right], right_max)

        # 더 높은 쪽을 향해 투포인터 이동
        if left_max <= right_max:
            volume += left_max - height[left]
            left += 1
        else:
            volume += right_max - height[right]
            right -= 1

    return volume

풀이 2. 스택 쌓기

• 높이를 스택에 쌓아가면서 현재 높이가 이전 높이보다 높을 때, 즉 꺾이는 부분 변곡점을 기준으로 격차만큼 물 높이 volume을 채운다. 이전 높이는 고정된 형태가 아니라 들쑥날쑥하기 때문에 계속 스택으로 채워나가다가 변곡점을 만날 때마다 스택에서 하나씩 꺼내면서 이전과 차이만큼 물 높이를 채워 나간다.

def solution(height):
    stack = []
    volume = 0

    for i in range(len(height)):
        # 변곡점을 만나는 경우
        while stack and height[i] > height[stack[-1]]:
            # 스택에서 꺼낸다.
            top = stack.pop()

            if not len(stack):
                break

            # 이전과의 차이만큼 물 높이 처리
            distance = i - stack[-1] - 1
            waters = min(height[i], height[stack[-1]]) - height[top]

            volume += distance * waters

        stack.append(i)
    return volume

세 수의 합

• 배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라.

예제

• 입력: nums = [-1, 0, 1, 2, -1, -4]
• 출력: [[-1, 0, 1], [-1, -1, 2]]

풀이 1. 투 포인터로 합 계산

• i를 축으로 하고 중복된 값이 나오면 건너뛴다. i의 다음 지점과 마지막 지점을 left, right로 설정하고 간격을 좁혀가면서 sum을 계산한다. sum이 0보다 작다면 값을 키워야하므로 left를 우측으로 이동하고 0보다 크다면 값을 줄여야하므로 right를 좌측으로 이동한다.
• sum = 0이면 정답이므로 결과를 result에 저장한다. 추가한 다음은 left, right 양 옆으로 동일한 값이 있을 수 있으므로 left += 1, right -= 1을 반복해서 스킵 처리한다. 마지막으로 left를 한 칸 우측으로 right를 한 칸 왼쪽으로 더 이동하고 다음으로 넘긴다.

def solution(nums):
    result = []
    nums.sort()

    for i in range(len(nums) - 2):
        # 중복된 값 건너뛰기
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        # 간격을 좁혀가며 합 sum 계산
        left, right = i + 1, len(nums) - 1
        while left < right:
            sum = nums[i] + nums[left] + nums[right]
            if sum < 0:
                left += 1
            elif sum > 0:
                right -= 1
            else:
                # sum = 0인 경우이므로 정답 및 스킵 처리
                result.append([nums[i], nums[left], nums[right]])

                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1

    return result

배열 파티션 1

• n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력하라.

예제

• 입력: [1, 4, 3, 2]
• 출력: 4

풀이 1. 오름차순 풀이

• 페어의 min을 합산했을 때 최대를 만드는 것은 결국 min()이 되도록 커야한다는 뜻이고 뒤에서부터 내림차수능로 집어 넣으면 항상 min() 페어를 유지할 수 있다. 이 문제에서 배열 입력값은 항상 2n개일 것이므로 앞에서부터 오름차순으로 집어 넣어도 결과는 똑같을 것이다.

def solution(nums):
    sum = 0
    pair = []
    nums.sort()

    for n in nums:
        # 앞에서부터 오름차순으로 페어를 만들어서 합 계산
        pair.append(n)
        if len(pair) == 2:
            sum += min(pair)
            pair = []

    return sum

풀이 2. 짝수번째 값 계산

• 일일히 페어에 대해 값을 구하지 않아도 짝수 번째 값을 더하면 될 것 같다. 정렬된 상태에서는 짝수 번째 항상 작은 값이 위치하기 때문이다.

def solution(nums):
    return sum(sorted(nums)[::2])

자신을 제외한 배열의 곱

• 배열을 입력받아 output[i]가 자신을 제외한 나머지 요소의 곱셈 결과가 되도록 출력하라. 나눗셈을 하지 않고 O(n)에 풀이하라.

예제

• 입력: [1, 2, 3, 4]
• 출력: [24, 12, 8, 6]

풀이 1. 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈

• 자기 자신을 제외하고 왼쪽의 곱셈 결과와 오른쪽의 곱셈 결과를 곱해야한다.
• 왼쪽부터 곱해서 result에 추가한다. 곱셈 결과는 그대로 out 리스트 변수에 담기게 되며, 마지막 값 곰셈으 ㄹ제외하여 결과는 [1, 1, 2, 6]이 된다.
• 그 후 왼쪽 곱셈 결과에 오른쪽 마지막 값부터 차례대로 곱해 나간다.

def solution(nums):
    out = []
    p = 1
    # 왼쪽 곱셈
    for i in range(0, len(nums)):
        out.append(p)
        p = p * nums[i]
    p = 1

    # 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
    for i in range(len(nums) - 1, 0 - 1, -1):
        out[i] = p * out[i]
        p = p * nums[i]

    return out

주식을 사고 팔기 가장 좋은 시점

• 한 번의 거래로 낼 수 있는 최대 이익을 산출하라.

예제

• 입력: [7, 1, 5, 3, 6, 4]
• 출력: 5

풀이 1. 저점과 현재 값과의 차이 계산

• 포인터가 우측으로 이동하면서 이전 상태의 저점을 기준으로 가격 차이를 계산하고 만약 클 경우 최댓값을 계속 교체해나가는 형태로 O(n) 풀이가 가능하다.
• 최솟값 변수는 시스템의 최솟값으로 지정한다. 어떤 값이 들어오든 바로 교체될 수 있기 때문이다.
• 이 문제는 최대 서브 배열 문제와도 유사하다. 그 문제는 카데인 알고리즘이라는 방법으로 O(n)에 풀이가 가능하다. 마찬가지로 여기서도 카데인 알고리즘을 응용해 O(n)으로 풀이하였다.

def solution(prices):
    profit = 0
    min_price = sys.maxsize

    # 최솟값과 최댓값을 계속 갱신
    for price in prices:
        min_price = min(min_price, price)
        profit = max(profit, price - min_price)

    return profit

출처: 파이썬 알고리즘 인터뷰

문자열 조작

문자열 조작이란 문자열을 변경하거나 분리하는 등의 여러 과정을 말한다. 대부분의 언어에서는 문자열을 조작하기 위한 다양한 기능들을 기본적으로 제공하고 있기 때문에, 굳이 제약을 두지 않는 한 언어에서 제공하는 기본 기능들을 잘 활용하는 편이 좋다.

유효한 펠린드롬

• 주어진 문자열이 펠린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다.

예제

• 입력: "A man, a plan, a canal: Panama"
• 출력: true

• 펠린 드롬이란?: 앞뒤가 똑같은 단어나 문장으로 뒤집어도 같은 말이 되는 단어 또는 문장을 팰린드롬(palindrome)이라고 한다.

풀이 1. 리스트로 변환

def solution(s):
    strs = []
    for char in s:
        if char.isalnum():
            strs.append(char.lower())

    while len(strs) > 1:
        if strs.pop(0) != strs.pop():
            return False

    return True

풀이 2. 데크 자료형을 이용한 최적화

def solution(s):
    strs: Deque = collections.deque()

    for char in s:
        if char.isalnum():
            strs.append(char.lower())

    while len(strs) > 1:
        if strs.popleft() != strs.pop():
            return False

    return True

• 리스트의 pop(0)이 O(n)인데 비해 데크의 popleft()는 O(1)이기 때문에 성능차이가 크다.

풀이 3. 슬라이싱 사용

def solution(s):
    s = s.lower()
    # 정규식으로 불필요한 문자 제거
    s = re.sub('[a-z0-9]', '', s)

    return s[::-1] == s

• 파이썬은 문자열을 배열이나 리스트 처럼 자유롭게 슬라이싱할 수 있는 기능을 제공하며, [::-1]을 이용하면 뒤집을 수 있다. 내부적으로 C보다 빠르게 구현되어 있어 훨씬 더 좋은 속도를 기대할 수 있다.

문자열 슬라이싱

• 문자열 슬라이싱은 위치를 지정하면 해당 위치의 배열 포인터를 얻게 되며 이를 통해 연결된 객체를 찾아 실제 값을 찾아내는데, 이 과정은 매우 빠르게 진행되므로 문자열을 조작할 때는 항상 슬라이싱을 우선으로 사용하는 편이 속도 개선에 유리하다. 문자열을 별도로 리스트로 매핑하는 등의 처리는 데이터 구조를 다루는 입장에서는 좋은 방법이지만, 별도 자료형으로 매핑하는 과정에서 상당한 연산 비용이 필요하므로 전체적인 속도에서는 오히려 손해를 볼 수 있다.

문자열 뒤집기

• 문자열을 뒤집는 함수를 작성하라. 입력값은 문자 배열이며 리턴 없이 리스트 내부를 직접 조작하라.

예제

• 입력: ["h", "e", "l", "l", "o"]
• 출력: ["o", "e", "l", "l", "h"]

풀이 1. 투 포인터를 이용한 스왑

• 투포인터는 단어 그대로 2개의 포인터를 이용해 범위를 조정해가며 풀이하는 방식을 말한다. 문제에서 리턴 없이 리스트 내부를 직접 조작하라는 제약사항이 있으므로 다음과 같이 s 내부를 스왑하는 형태로 풀이하면 된다.

def solution(s):
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[rigth] = s[right], s[left]
        left += 1
        right -= 1

풀이 2. 파이썬다운 방식

• 파이썬의 기본 기능 reverse를 이용하면 한 줄로 쉽게 풀이할 수 있다.

def solution(s):
    s.reverse()

로그파일 재정렬

• 로그를 재정렬하라. 기준은 다음과 같다.
  1. 로그의 가장 앞 부분은 식별자다
  2. 문자로 구성된 로그가 숫자 로그보다 앞에 온다
  3. 식별자는 순서에 영향을 끼치지 않지만 문자가 동일할 경우 식별자 순으로 한다.
  4. 숫자로그는 입력순서대로 한다.

예제

입력: logs = ['dig1 8 1 5 1', 'let1 art can', 'dig2 3 6', 'let2 own kit dig', 'let3 art zero']

출력: ['let1 art can', 'let3 art zero', 'let2 own kit dig', 'dig1 8 1 5 1', 'dig2 3 6' ]

풀이 1. 람다와 + 연산자를 사용

• 문자로 구성된 로그가 숫자 로그보다 이전에 오며 숫자 로그는 입력순서대로 둔다. 그렇다면 문자와 숫자를 구분하고, 숫자는 나중에 그대로 이어 붙인다.
• isdigit()을 이용하여 숫자 여부를 판별해 구분한다.

def solution(logs):
    letters, digits = [], []
    for log in logs:
        if log.split()[1].isdigt():
            digits.append(log)
        else:
            letters.append(log)

    # 2개의 키를 람다 표현식으로 정렬
    letter.sort(key=lambda x: (x.split()[1:], x.split()[0]))
    return letters + digits

가장 흔한 단어

• 금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력하라. 대소문자 구분을 하지 않으며 구두점 또한 무시한다.

예제

• 입력: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit", banned = ['hit']
• 출력: "ball"

풀이 1. 리스트 컴프레헨션

• 입력값에는 대소문자가 섞여 있으며 쉼표 등 구두점이 존재한다. 따라서 데이터클렌징이라 부르는 입력값에 대한 전처리 작업이 필요하다. 정규식을 섞어 처리한다.
• defautldict(int)를 사용해 int값이 기본으로 부여되게 해서 단어의 갯수를 센다. max()함수에 key를 지정해 argmax를 간접적으로 추출한다.
• 혹은 collections의 Counter 모듈을 이용해 most_common으로 추출한다.

def solution(paragraph, banned):
    words = [word for word in re.sub('[^\w]', ' ', paragraph).lower().split() if word not in banned]
    counts = collections.Counter(words)
    return counts.most_common(1)[0][0]

그룹 애너그램

• 문자열 배열을 받아 애너그램 단위로 그룹핑하라.

예제

• 입력: ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']
• 출력: [['ate', 'eat', 'tea'], ['nat', 'tan'], ['bat']]
• 애너그램이란?: 일종의 언어유희로 문자을 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 말한다.

풀이 1. 정렬하여 딕셔너리 추가

• 애너그램을 판단하는 가장 간단한 방법은 정렬하여 비교하는 것이다. sorted()는 문자열도 잘 정렬하며 여기서 출력된 리스트를 join()으로 다시 합쳐 이 값을 키로 하는 딕셔너리를 구성한다.

def solution(strs):
    anagrams = collections.defauldict(list)

    for word in strs:
        anagrams[''.join(sorted(word))].append(word)

    return list(anagrams.values())

여러가지 정렬 방법

• 파이썬은 정렬 함수를 기본으로 제공한다. 파이썬에서 시작된 고성능 정렬 알고리즘은 팀소트이다.
• sorted()는 문자열과 리스트를 잘 정렬하며 리스트 자료형은 sort() 메소드를 함께 제공한다. 이를 제자리 정렬이라고 부르는데, 일반적으로 제자리 정렬 알고리즘은 입력을 출력으로 덮어 쓰기 때문에 별도의 추가 공간이 필요하지 않으며 리턴값이 없다. 따라서 정렬 결과를 별도로 리턴하는 sorted()와 다르므로 주의가 필요하다.
• sorted는 key= 옵션을 지정해 정렬을 위한 키 또는 함수를 별도로 지정할 수 있다.
• 팀소트는 실제 데이터는 대부분 어느정도 이미 정렬되어 있을 것이다라고 가정하고 실제 데이터에서 고성능을 낼 수 있도록 설계한 알고리즘이다.
• 팀소트 알고리즘은 시간복잡도가 평균 O(n log n)이다.

가장 긴 팰린드롬 부분 문자열

• 가장 긴 팰린드롬 부분 문자열을 출력하라.

예제

• 입력: "babad"
• 출력: "bab"

풀이 1. 중앙을 중심으로 확장하는 풀이

• 컴퓨터과학의 오랜 문제중에 최장 공통 부분 문자열이라는 문제가 있다. 여러개의 입력 문자열이 있을 때 서로 공통된 가장 긴 부분 문자열을 찾는 문제로, 다이나믹 프로그래밍으로 풀 수 있는 전형적인 문제다. 이 문제 또한 다이나믹 프로그래밍으로 풀 수 있지만 직관적으로 이해가 어렵고 일반적인 예상과 달리 실행속도가 늦다.
• 팰린드롬 판별만 하면 된다는 점에 착안해서, 매칭이 될 때 중앙을 중심으로 점점 확장해 나가면서 가장 긴 팰린드롬을 판별하는 알고리즘을 구현해보자.

def solution(s):
    # 팰린드롬 판별 및 투포인터 확장
    def expand(left, right):
        while left >= 0, and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]

    # 해당 사항이 없을 때 빠르게 리턴
    if len(s) < s or s == s[::-1]:
        return s

    result = ''
    # 슬라이딩 윈도우 우측으로 이동
    for i in range(len(s) - 1):
        result = max(result, 
                    expand(i, i + 1),
                    expand(i, i + 2),
                    key=len)

유니코드와 UTF-8

초기에 문자를 표현하던 대표적은 방식은 ASCII 인코딩 방식으로 1바이트에 모든 문자를 표현했다. 게다가 1은 체크섬으로 제외하여 7비트, 즉 128글자로 문자를 표현햇다. 그러다 보니 한글이나 한자 같은 문자는 2개 이상의 특수문자를 합쳐서 표현하곤 했는데, 이런 방식으론 표현하지 못했다. 이런 문제를 해결하기 위해 2~4 바이트 공간에 여유있게 문자를 할당하고자 등장한 방식이 유니코드다.

그러나 유니코드 자체는 메모리 낭비가 심해서 이를 가변 길이 문자 인코딩 방식으로 효율적으로 인코딩하는 대표적인 방식이 UTF-8이다.

만약 모든 문자를 4바이트로 표현한다면 python은 24바이트의 메모리를 차지하게 될 것이다. 영문자는 각 문자당 1바이트로 충분한데 3바이트씩 낭비가 되고 있다. UTF-8은 첫 바이트의 맨 앞비트를 확인해서 0이면 1바이트, 10이면 특정 문자의 중간 바이트, 110이면 2바이트, 1110이면 3바이트, 11110이면 4바이트라는 식으로 문자 바이트의 길이를 인식할 수 있다. 약 100만자 정도를 표현할 수 있게 됐다.

출처: 파이썬 알고리즘 인터뷰

pandas

• 구조화 된 데이터 처리를 지원하는 라이브러리
• python계의 엑셀
• panel data - > pandas
• 고성능 array 계산 라이브러리인 numpy와 통합하여 강력한 '스프레드시트' 처리 기능을 제공
• 인덱싱, 연산용 함수, 전처리 함수 등을 제공함
• 데이터 처리 및 통계 분석을 위해 사용

데이터 로딩

• pd.read_csv: csv 읽어옴
• head(): 처음 다섯 행 출력
• columns: 컬럼 이름 지정

series

• DataFrame: 데이터 테이블 전체를 포함하는 object
• 데이터 프레임중 하나의 column에 해당하는 데이터의 모음 object
• 데이터, 인덱스로 구성됨

import pandas as pd
list_data = [1, 2, 3, 4, 5]
list_name = ['a', 'b', 'c', 'd', 'e']
sample_obj = pd.Series(data=list_data, index=list_name)

sample_obj['a'] # 인덱스로 접근하기
sample_obj['a'] = 3.2 # 인덱스로 할당하기
sample_obj.astype(int) # 타입 변경
sample_obj.values # 값 리스트만
sample_obj.index # 인덱스 리스트만
sample_obj.name # 컬럼 이름 지정

• 인덱스 값을 기준으로 series 생성, 인덱스가 데이터보다 많으면 NaN 추가

DataFrame

• 데이터 테이블 전체를 포함하는 object
• series를 모아서 만든 데이터 테이블 = 기본 2차원

raw_data = {'first_name':['Jason', 'Molly', 'Tina', 'Jake', 'Amy'],
           'last_name':['Miller', 'Jaconbson', 'Ali', 'Milner', 'Cooze'],
           'age':[42, 52, 36, 24, 73],
           'city':['San Francisco', 'Baltimore', 'Douglas', 'Boston']}

df = pd.DataFrame(raw_data, colums = ['first_name', 'last_name', 'age', 'city'])

# column 선택 방법 - Serise 데이터
df.first_name
df['first_name']

DataFrame indexing

• loc[index, column]: 인덱스 이름으로 접근
• iloc: 숫자로 변형

DataFrame handling

df.debt = df.age > 40 #column에 새로운 값 할당

values = Serise(data=['M', 'F', 'F'], index=[0, 1, 3])
df['sex'] = values

df.T # transpose
df.values # array 타입으로 값 출력
df.to_csv() # csv형태로 출력

del df['debt'] # 컬럼 삭제
df.drop('debt', axis=1)

selection with column names

• 컬럼 하나: df['column']
• 컬럼 하나 이상: df[[column_1, column_2, column_3]]

selection with index number

• df[:1]
• 한 개 이상 인덱스: df[0, 1, 2]
• 불리언: df[column < 500]

basic, loc, iloc selection

• basic: df[['column_1', 'column_2']]
• loc: df.loc[1, 1]
• iloc: df.iloc[1, 1]

index 재설정

• df.index = list: 인덱스 할당
• df.reset_index(inplace=True): 인덱스 리셋, inplace - 원본 데이터를 변경함

data drop

• df.drop(index, inplace=True): 해당 인덱스 삭제

dataframe operation

serise operation

• index를 기준으로 연산 수행, 겹치는 index가 없을 경우 NaN 반환
• fill_value: NaN값 0으로 바꿔서 계산

series + dataframe

• axis를 기준으로 row broadcasting 실행
• df.add(s2, axis=0)

lambda, map, apply

• pandas의 series type에도 map 함수 사용 가능
• function 대신 dict, sequence 자료등으로 대체 가능

s1 = Series(np.arange(10))
s1.map(lambda x:x**2).head()

z = {1:'A', 2:'B', 3:'C'}
s1.map(z).head()
#dict type으로 데이터 교체

s2 = Series(np.arange(10, 20))
s1.map(s2).head(5)
#같은 위치의 데이터를 s2로 전환

apply for dataframe

• map과 달리 series 전체가 해당 함수에 들어감
• 입력 값이 series 데이터로 입력받아 handling 가능
• 내장 연산 함수를 사용할 때도 똑같은 효과를 거둘 수 있음
• mean, std, sum 등
• series 단위에 apply 적용시킬 때는 map과 같은 효과

applymap for dataframe

• series 단위가 아닌 element 단위로 함수를 적용함

pandas built-in function

describe

• numeric type 데이터의 요약 정보를 읽어줌

unique

• series data의 유일한 값을 list로 반환

sum

• 기본적인 column 또는 row 값의 연산을 지원
• sub, mean, min, max, count, median, mad, var 등

isnull

• column 또는 row값의 Nana 값의 인덱스를 반환함
• df.isnull().sum(): 널값이 몇갠지 보여줌

sort_values

• column 기준으로 데이터를 sorting

correlation & covariance

• 상관계수와 공분산을 구하는 함수
• corr(모든 column), cov, corrwith(특정 한 column)

• pd.option.display.max_rows: 디스플레이 행 수 늘리기

Groupby-1

• SQL groupby 명령어와 같음
• split -> apply -> combine 과정을 거쳐 연산함

df.groupby('Team')['Points'].sum()

• 한 개 이상의 column을 묶을 수 있음

df.groupby(['Team', 'Year'])['Points'].sum()

hierarchical index

• groupby 명령의 결과물도 dataframe
• 두개의 column으로 groupby를 할 경우, index가 두개 생성
• unstack(): 그룹으로 묶여진 데이터를 matrix 형태로 바꿔 줌
• swaplevel(): 인덱스 레벨을 바꿔 줌
• sort_index(level=0): 레벨을 기준으로 sort
• index level을 기준으로 기본 연산 수행 가능

Groupby-2

• groupby에 의해 split 된 상태를 추출 가능함

grouped = df.groupby('Team')

for name, group in grouped:
    print(name)
    print(group)

• tuple 형태로 그룹의 key, value 값이 추출 됨
• get_gorup(group_name): 특정 그룹의 정보를 가져올 수 있음
• 추출된 그룹 정보에는 세 가지 유형의 apply가 가능함
• Aggregation: 요약된 통계 정보를 추출해줌
• Transformation: 해당 정보를 변환해줌
• Filtration: 특정 정보를 제거하여 보여주는 필터링 기능

pivot table & crosstab

pivot table

• index 축은 groupby와 동일함
• column에 추가로 labeling 값을 추가하여
• value에 numeric type 값을 aggregation 하는 형태

df_phone.pivot_table(value=['duration'],
                    index=[df_phone.month, df_phone.item],
                    columns=df_phone.network,
                    aggfunc='sum',
                    fill_value=0)

# groupby로 구현

df_phone.groupby(['month', 'item', 'network'])['duration'].sum().unstack()

crosstab

• 두 칼럼의 교차 빈도, 비율, 덧셈등을 구할 때 사용
• pivot table의 특수한 형태
• user-item rating matrix등을 만들 때 사용

pd.crosstab(index=df_movie.critic,
           columns=df_movie.title,
           values=df_movie.rating,
           aggfunc='first',
           ).fillna(0)

merge & concat

merge

• SQL에서 사용하는 merge와 같은 기능
• 두개의 데이터를 하나로 합침

pd.merge(df_a, df_b, on='subject_id')
pd.merge(df_a, df_b, left_on='subject_id', right_on='subject_id') # 두 dataframe의 column 이름이 다를 때

join method

• inner join: 양쪽 테이블에 같은 subject_id가 있어야 함
• left/right join: 어느 한 쪽을 기준으로 join, 없는 것은 NaN 처리
• full(outer) join: 같은 것은 join하고 다른 것은 NaN

index based join

pd.merge(df_a, df_b, right_index=True, left_index=True)

concat

• 같은 형태의 데이터를 붙이는 연산작업

pd.concat([df_a, df_b], axis=1)

• 예제) 날짜 별로 다른 파일에 저장이 되어 있을 때

import os
import pandas as pd

files = [file_name for file_name in os.listdir('./data') if file_name.endswith('xlsx')]

df_list = [pd.read_excel(os.path.join('data', df_filename) for df_filename in files)]
status = df_list[0]
sales = pd.concat(df_list[1:])

persistence

Database connection

• data loading시 db connection 기능 제공함

import sqlite3

conn = sqlite3.connect('./data/flights.db')
cur = conn.cursor()
cur.execute('select * from airlines limit 5;')
result = cur.fetchall()
result

df_airlines = pd.read_sql_query('select * from airlines;', conn)
df_airlines

XLS persistence

• dataframe의 엑셀 추출 코드
• xls 엔진으로 openpyxls 또는 XlsxWrite 사용

writer = pd.ExcelWriter('./data/df_routes.xlsx', engine='xlsxwriter')
df_routes.to_excel(writer, sheet_name='Sheet1')

출처: boostcamp precourse

Numerical Python - Numpy

"어떻게 행렬과 매트릭스를 코드로 표현할 것인가?"

coefficient_matrix = [[2, 2, 1], [2, -1, 2], [1, -1, 2]]
constant_vector = [9, 6, 5]

• 다양한 matrix 계산을 어떻게 만들 것인가?
• 굉장히 큰 matrix에 대한 표현(메모리 효율 x)
• 처리 속도 문제 - python은 interpreter 언어

numpy

• numerical python
• 파이썬의 고성능 과학 계산용 패키지
• matrix와 vector와 같은 array 연산의 사실상의 표준

numpy의 특징

• 일반 list에 비해 빠르고, 메모리 효율적
• 반복문 없이 데이터 배열에 대한 처리를 지원함
• 선형대수와 관련된 다양한 기능을 제공함
• C, C++, 포트란 등의 언어와 통합 가능

ndarray

import numpy as np

test_array = np.array([1, 4, 5, 8], float)
print(test_array)
type(test_array[3])

• np.array 함수를 통해 배열을 생성함
• numpy는 하나의 데이터 type만 배열에 넣을 수 있음
• list와 가장 큰 차이점: 다이나믹 타이핑 x
• C의 array를 사용하여 배열을 생성함

array creation

• ndarray는 데이터가 차례대로 메모리에 할당
• python 리스트는 데이터가 메모리에 차례대로 들어가는 것이 아니라 데이터의 주소를 리스트에 넣음(주소로 부터 메모리로 들어가는 단계를 한번 더 거쳐야 함)
• shape: array의 dimension 구성을 반환
• dtype: array의 데이터 타입을 반환

array.shape

• array의 rank에 따라 불리는 이름이 있음
• 0: scalar, 1: vector, 2: matrix, 3: 3-tensor, n: n-tensor
• ndim - number of dimensions = rank
• size - data의 갯수

array.dtype

• single element가 가지는 data type
• 각 element가 차지하는 memory의 크기가 결정됨(ex. np.float32, np.int8 ...)

array.nbytes

• nbytes: array object의 메모리 크기를 반환함

Handling shape

reshape

• reshape: array의 shape의 크기를 변경함, element의 갯수는 동일

import numpy as np
np.array(test_matrix).reshape(2, 4)
np.array(test_matrix).reshape(-1, 2)
# -1: size를 기반으로 row 갯수 선정

flatten

• flatten: 다차원 array를 1차원 array로 변환

np.array(test_matrix).flatten()

indexing & slicing

• list와 달리 이차원 배열에서 [0, 0] 표기법을 제공함
• matrix일 경우 앞은 row 뒤는 column을 의미함

a = np.array([[1, 2, 3], 
              [4, 5, 6]])

print(a[0][2])
print(a[0, 2])
a[0, 2] = 10 # 0, 2에 10 할당

• 리스트와 달리 행과 열을 나눠서 slicing이 가능함
• matrix의 부분 집합을 추출할 때 유용함

a = np.array([[1, 2, 3, 4, 5],
             [6, 7, 8, 9, 10]])

a[:, 2:] # 전체 row의 2열 이상
a[1, 1:3] # 1 row의 1~2열
a[1:3] # 1~2 row 전체

• a[start : end : step]

creation function

• arange: array의 범위를 지정하여 값의 list를 생성하는 명령어
• zeros: 0으로 가득찬 array 생성
• ones: 1로 가득찬 array 생성
• empty: memory만 주어지고 비어있는 array 생성
• somthing_like: array의 shape 크기 만큼 1, 0, 또는 empty array를 반환

identity

• 단위 행렬을 생성함

eye

• 대각선의 값이 1인 행렬, k값의 시작 index의 변경이 가능

diag

• 대각 행렬의 값을 추출함, k값 지정 가능

random sampling

• 데이터의 분포에 따른 sampling으로 array 생성

np.random.uniform(0, 1, 10).reshape(2, 5)

operation functions

sum

• array의 element 간의 합

axis

• 모든 operation function을 실행할 때 기준이 되는 dimension 축
• (3, 4): axis = 0은 3, axis = 1은 4

mean & std

• array의 element들 간의 평균 또는 표준편차를 반환

mathmatical functions

• 그 외에도 다양한 수학 연산자를 제공함

concatenate

• array를 합치는 함수
• vstack: 세로로 붙이기
• hstakc: 가로로 붙이기
• concatenate: axis를 기준으로 붙임
• np.newaxis: 축을 추가해줌

operations b/t array

• numpy는 array간의 기본적인 사칙 연산을 지원함
• element-wise operations: array간 shape이 같을 때, 같은 위치에 있는 element끼리 연산

Dot product

• matrix의 기본연산, dot 함수 사용

test_a.dot(test_b)

transpose

• transpose 함수 또는 T attribute 사용

broadcasting

• shape이 다른 배열 간 연산을 지원하는 기능

test_matrix = np.array([[1, 2, 3],
                       [4, 5, 6]])
scalar = 3
print(test_matrix + scalar)

• scalar-vector 외에도 vector-matrix 간의 연산도 지원

numpy performace

• timeit: jupyter 환경에서 코드의 퍼포먼스를 측정하는 함수
• 일반적인 속도: for loop < list comprehension < numpy
• numpy는 C로 구현되어 있어 성능을 확보하는 대신 dynamic typing을 포기함
• concatenate 처럼 계산이 아닌 할당에서는 연산 속도의 이점이 없음

comparison

All & Any

• array의 데이터 전부 또는 일부가 조건에 만족 여부 반환

comparison operation

• 배열의 크기가 동일할 때, element간 비교의 결과를 boolean type으로 반환(element-wise)
• logical_and, logical_not, logical_or

np.where

np.where(a > 0, 3, 2) # where(condition, True, False)

a = np.arange(10)
np.where(a>5) # index 값 반환

a = np.array([1, np.NaN, np,Inf])
np.isnan(a)
np.isfinite(a)

argmax & argmin

• array내 최대값 또는 최소값의 index 반환
• axis 기반의 반환

a = np.array([[1, 2, 4, 7],
             [9, 88, 6, 45],
             [9, 76, 3, 4]])

np.argmax(a, axis=1)
# array([3, 1, 1])

• argsort(): 오름차순으로 정렬한 index 반환

boolean & fancy index

boolean index

• 특정 조건에 따른 값을 배열 형태로 추출
• comparison operation 함수들도 모두 사용 가능

test_array = np.array([1, 4, 0, 2, 3, 8, 9, 7])

test_array[test_array > 3]

fancy index

• array를 index value로 사용해서 값 추출

a = np.array([2, 4, 6, 8])
b = np.array([0, 0, 1, 3, 2, 1]) # 반드시 integer로 선언
a[b] # b 배열의 값을 index로 하여 a 값을 추출함
a.take(b) # bracket index와 같은 효과

• matrix도 사용 가능

numpy data i/o

loadtxt & savetxt

• text type의 데이터를 읽고 저장하는 기능

a = np.loadtxt('population,txt', delimiter='\t')

np.savetxt('int_data_2.csv', a_int_3, fmt='%.2e', delimiter=',')

numpy object - npy

np.save('npy_test.npy', arr=a_int)

npy_array = np.load(file='npy_test.npy')

• 피클 형태로 저장

출처: boostcamp precourse

Comma separte value(csv)

• csv, 필드를 쉽표로 구분한 텍스트 파일
• 엑셀 양식의 데이터를 프로그램에 상관없이 쓰기 위한 데이터 형식
• 탭(TSV), 빈칸(SSV) 등으로 구분해서 만들기도 함
• 통칭하며 character separated values(CSV)
• 엑셀에서는 '다른 이름 저장' 기능으로 사용 가능

엑셀로 CSV 파일 만들기

1) 파일 다운로드
2) 파일 열기
3) 파일 -> 다른 이름 저장 -> CSV 선택
4) 엑셀 종료 후 notepad로 파일 열어보기

파이썬으로 CSV 파일 읽기/쓰기

• 일반적 textfile을 처리하듯 파일을 읽어온 후, 한줄 한 줄씩 데이터를 처리함

line_counter = 0
data_handler = [] # 데이터의 헤드
customer_list = [] # customer 개별 리스트

with open ('customer.csv') as f:
    while True:
        data = f.readline()
        if not data: break
        if line_counter == 0:
            data_handler = data.split(',')
        else:
            customer_list.append(data.split(','))
        line_counter += 1

csv 객체로 csv 처리

• text 파일 형태로 데이터 처리시 전처리 과정이 필요
• 파이썬에서는 간단히 csv 파일을 처리하기 위해 csv 객체를 제공함

import csv
reader = csv.reader(f,
                   delimiter = ','
                   quotechar="'",
                   quoting=csv.QOUTE_ALL)

Web

• 인터넷 = Web
• 데이터 송수신을 위한 HTTP 프로토콜 사용
• 데이터를 표시하기 위해 HTML 사용

web은 어떻게 동작하는가?

1. 요청: 웹주소, form, header 등
2. 처리: Database 처리 등 요청 대응
3. 응답: HTML, XML 등으로 결과 반환

HTML(Hyper Text Markup Language)

• 웹상의 정보를 구조적으로 표현하기 위한 언어
• 제목, 단락, 링크 등 요소 표시를 위해 Tag 사용
• 모든 요소들은 꺾쇠 괄호 안에 둘러 쌓여 있음
• ex)
• 모든 HTML은 트리 모양의 포함 관계를 가짐
• HTML 소스파일을 컴퓨터 브라우저가 해석

왜 웹을 알아야 하는가?

• 정보의 보고, 많은 데이터들이 웹을 통해 공유됨
• HTML도 일종의 프로그램, 페이지 생성 규칙이 있음: 규칙을 분석하여 데이터의 추출이 가능
• 추출된 데이터를 바탕으로 하여 다양한 분석이 가능

정규식(regular expression)

• 복잡한 문자열 패턴을 정의하는 문자 표현 공식
• 특정한 규칙을 가진 문자열의 집합을 추출
• HTML 역시 tag를 사용한 일정한 형식이 존재하여 정규식으로 추출이 용이함
• 문법은 매우 방대, 스스로 찾아서 하는 공부 필요

정규식 연습장 활용하기: regexr.com

정규식 기본 문법 - 메타문자

• 정규식 표현을 위해 다른 용도로 사용되는 문자
• {m, n}: 반복 횟수를 지정
• ?: 반복 횟수가 1회
• |: or, ^: not

정규식 in 파이썬

• re모듈을 import하여 사용
• 함수: search - 한개만 찾기, findall - 전체 찾기
• 추출된 패턴은 tuple로 반환 됨

import re
import urllib.request

url = 'hhtps://bit.ly/3rxQFS4'
html = urllib.request.urlopen(url)
html_contents = str(html.read())
id_results = re.findall(r'([A-Za-z0-9]+\*\*\*)', html_contents)

for result in id_results:
    print(result)

XML(extensive markup language)

• 데이터의 구조와 의미를 설명하는 Tag를 사용하여 표시하는 언어
• Tag와 Tag 사이에 값이 표시되고 구조적인 정보를 표현할 수 있음
• HTML과 문법이 비슷, 대표적인 데이터 저장 방식

XML이란

• 정보 구조에 대한 정보인 스키마와 DTD 등으로 정보에 대한 정보가 표현되며, 용도에 따라 다양한 형태로 변경가능
• XML은 컴퓨터(PC와 스마트폰)간에 정보를 주고 받기 매우 유용한 저장 방식으로 쓰이고 있음

Beautifulsoup

• html, xml등 markup 언어 scraping을 위한 대표적인 도구
• lxml과 html5lib 과 같은 parser를 사용함
• 속도는 상대적으로 느리나 간편히 사용할 수 있음

# 모듈 호출
from bs4 import BeautifulSoup

# 객체 생성
soup = BeautifulSoup(books_xml, 'lxml')
# 태그 찾는 함수 find_all 생성
for book_info in soup.find_all('author'):
    print(book_info.get_text())

JavaScript Object Notation

• 원래 웹 언어인 java Script의 데이터 객체 표현 방식
• 간결성으로 기계/인간이 모두 이해하기 편한
• 데이터 용량이 적고, code로 전환이 편함
• xml 대체제로 많이 활용 됨

Json overview

• python의 dict type과 유사
• key:value 쌍으로 전환 가능

Json in python

• 데이터 저장 및 읽기는 dict type과 상호호환 가능
• 웹에서 제공하는 API는 대부분 정보 교환시 Json 활용

import json

# 읽기
with open('json_example.json', 'r', encoding='utf8') as f:
    contents = f.read()
    json_data = json.loads(contents)

# 쓰기
dict_data = {'name':'Zara', 'Age':7, 'Class':'First'}

with open('data.json', 'w') as f:
    json.dump(dict_data, f)

출처: boostcamp precourse

프로그램 사용할 때 일어나는 오류들

• 주소를 입력하지 않고 배송 요청
• 저장도 안했는데 컴퓨터 전원이 나감
• 게임 아이템 샀는데 게임에서 튕김1) 예상이 가능한 예외
  2) 예상이 불가능한 예외
• exception

예상 가능한 예외

• 발생 여부를 사전에 인지할 수 있는 예외
• 사용자의 잘못된 입력, 파일 호출 시 파일 없음
• 개발자가 반드시 명시적으로 정의 해야 함

예상이 불가능한 예외

• 인터프리터 과정에서 발생하는 예외, 개발자 실수
• 리스트의 범위를 넘어가는 값 호출, 정수 0으로 나눔
• 수행 불가시 인터프리터가 자동 호출

예외 처리

• 예외가 발생할 경우 후속 조치 등 대처 필요
  1) 없는 파일 호출 -> 파일 없음을 알림
  2) 게임 이상 종료 -> 게임 정보 저장
• 프로그램 = 제품, 모든 잘못된 상황에 대처가 필요

"Exception Handling"

Exception handling

try ~except 문법

try:
    # 예외 발생 가능 코드
except <Exception Type>:
    # 예외 발생 시 대응하는 코드

예시. 0으로 숫자를 나눌 때 예외 처리

for i in range(10):
    try:
        print(10/i)
    except ZeroDivisionError:
        print('Not divided by 0')

built-in Exception: 기본적으로 제공하는 예외

• IndexError: 리스트 인덱스 범위를 넘어갈 때
• NameError: 존재하지 않은 변수 호출
• ZeroDivisionError: 0으로 숫자를 나눌 때
• ValueError: 변환할 수 없는 문자/숫자를 변환할 때
• FileNotFoundError: 존재하지 않는 파일 호출

tryexceptelse

try:
    # 예외 발생 가능 코드
except <Exception Type>:
    # 예외 발생 시 대응하는 코드
else:
    # 예외가 발생하지 않았을 경우

tryexceptfinally

try:
    # 예외 발생 가능 코드
except <Exception Type>:
    # 예외 발생 시 대응하는 코드
finally:
    # 예외가 발생했을 경우, 안했을 경우 모두 실행

raise 구문

• 필요에 따라 강제로 Exception을 발생

while True:
    value = input('변환할 정수 값을 입력해주세요')
    for digit in value:
        if digit not in '0123456789':
            raise ValueError('숫자값을 입력하지 않으셨습니다')
    print('정수 값으로 변환한 숫자')

assert 구문

• 특정 조건에 만족하지 않을 경우 예외 발생

def get_binary_number(decimal_number):
    assert isinstance(dicimal_number, int)
    return bin(decimal_number)

File handling

• File System: OS에서 파일을 저장하는 트리구조 저장 체계
• File from wiki: 컴퓨터 등의 기기에서 의미 있는 정보를 담는 논리적인 단위. 모든 프로그램은 파일로 구성되어 있고 파일을 사용한다.

파일의 종류

• 기본적인 파일 종류로 text 파일과 binary 파일로 나눔
• 컴퓨터는 text 파일을 처리하기 위해 binary 파일로 변환시킴
• 모든 text 파일도 실제는 binary 파일
• ASCII/Unicode 문자열 집합으로 저장되어 사람이 읽을 수 있음

Python File I/O

• 파이썬은 파일 처리를 위해 open 키워드를 사용함

파이썬의 File read

• read(): text 파일안에 있는 내용을 문자열로 반환

f = open('dream.txt', 'r')
contents = f.read()
print(contents)
f.close()

• with 구문과 함께 사용하기

with open('dream.txt', 'r') as f:
    # 파일 전체를 리스트로 변환
    content_list = f.readlines()

• 실행 시마다 한 줄 씩 읽어 오기 (한 줄 씩 읽으면서 그때 그때 메모리에 올리기)

with open('dream.txt', 'r') as f:
    i = 0
    while True:
        line = f.readline()
        if not line:
            break
        print(str(i) + '===' + line.replace('\n', '')) # 한 줄 씩 값 출력
        i += 1

파이썬의 File Write

• mode는 'w', encoding='utf8'

f = open('count.txt', 'w', encoding='utf8')
for i in range(1, 11):
    data = '%d번째 줄입니다\n' % i
    f.write(data)
f.close()

• mode 'a'는 추가 모드

with open('count.txt', 'a', encoding='utf8') as f:
    for i in range(1, 11):
        data = '%d번째 줄입니다.\n' % i
        f.write(data)

파이썬의 directory 다루기

import os
os.mkdir('log') # log 폴더 만들기
os.path.exists('log') # 폴더가 있는지 확인

import shutil
source = 'dream.txt'
dest = os.path.join('abc', 'sc.txt')
# os마다 폴더 seperator가 다르기 때문에 join을 사용한다.
shutil.copy(source, dest) # 파일 복사

• 최근에는 pathlib 모듈을 사용하여 path를 객체로 다룸

import pathlib

cwd = pathlib.path.cwd()
print(cwd.parent) # 부모 폴더
print(list(cwd.parents)) # 부모 폴더 리스트
print(list(cwd.glob('*')) # 폴더 내 모든 파일

예제. Log 파일 생성하기

import os
if not os.path.isdir('log'):
    os.mkdir('log')
if not os.path.exists('log/count_log.txt'):
    f = open('log/count_log.txt', 'w', encoding='utf8')
    f.write('기록이 시작됩니다\n')
    f.close

with open('log/count_log.txt', 'a', encoding='utf8') as f:
    import random, datetime
    for i in range(1, 11):
        stamp = str(datetime.datetime.now())
        value = random.random() * 1000000
        log_line = stamp + '\t' + str(value) + '값이 생성되었습니다' + '\n'
        f.write(log_line)

Pickle

• 파이썬의 객체를 영속화(파일로 씀)하는 built-in 객체
• 데이터, object 등 실행중 정보를 저장 -> 불러와서 사용
• 저장해야하는 정보, 계산 결과(모델) 등 활용이 많음
• Binary 파일

import pickle

f = open('list.pickle', 'wb')
test = [1, 2, 3, 4, 5]
pickle.dump(test, f) # 피클에 저장
f.close()

f = open('list.pickle', 'rb')
test_pickle = pickle.load(f) # 피클 열기
test_pickle
f.close()

Logging handling

logging

• 프로그램이 실행되는 동안 일어나는 기록을 남기기
• 유저의 접근, 프로그램의 Exception, 특정 함수의 사용
• 어디에? - console 화면에 출력, 파일에 남기기, DB에 남기기 등등
• 기록된 로그를 분석하여 의미있는 결과를 도출 할 수 있음
• 실행시점에서 남겨야 하는 기록, 개발시점에서 남겨야 하는 기록

print vs logging

• 기록을 print로 남기는 것도 가능
• 그러나 console 창에만 남기는 기록은 분석시 사용 불가
• 때로는 레벨별(개발, 운영)로 기록을 남길 필요도 있음
• 모듈별로 별도의 logging을 남길 필요도 있음
• 이런 기능을 체계적으로 지원하는 모듈이 필요함

logging level

• 프로그램 진행 상황에 따라 다른 레벨의 로그를 출력함
• 개발시점, 운영시점 마다 다른 로그가 남을 수 있도록 지원함
• debug > info > warning > error > critical
• log 관리시 가장 기본이 되는 설정 정보

import logging

logging.debug #개발시 처리 기록을 남겨야하는 로그 정보
logging.info # 처리가 진행되는 동안의 정보
logging.warning # 사용자가 잘못 입력한 정보다 원래 개발시 의도치 않는 정보가 들어왔을 때
logging.error # 잘못된 처리로 에러가 났으나, 프로그램은 동작할 수 있음
logging.critical # 잘못된 처리로 데이터 손실이나 더이상 프로그램이 동작할 수 없음을 알림

• 기본 레벨은 warning부터 사용자가 확인 가능
• logging.basicConfig()로 기본 레벨 변경 가능
• logging.FileHandler(): 파일에 로그 저장

configparser

• 프로그램의 실행 설정을 file에 저장함
• section, key, value 값의 형태로 설정된 설정 파일을 사용
• 설정파일을 dict type으로 호출 후 사용

import configparser
config = configparser.ConfigParser()

config.read('example.cfg')
config.sections()

for key in config['SectionOne']:
    print(key)

config['SectionOne']['status']

argparser

• console 창에서 프로그램 실행시 setting 정보를 저장함
• 거의 모든 console 기반 python 프로그램 기본으로 제공
• 특수 모듈도 많이 존재하지만(TF), 일반적으로 argparse를 사용
• Command-Line option이라고 부름

import argparse

parser = argparse.ArgumentParser(description='Sum two integers.')

parser.add_argument('-a', '--a_value', dest='A_value', help='A integers', type=int)
parser.add_argument('-b', '--b_value', dest='B_value', help='B integers', type=int)

args = parser.parse_args()
print(args)
print(args.a)
print(args.b)
print(args.a + args.b)

Logging formater

• 로그 결과값의 format을 지정해줄 수 있음

formatter = logging.Formatter('%(asctime)s %(levelname)s %(process)d %(message)s/')

Log config file

logging.config.fileConfig('logging.conf')
logger = logging.getLogger()

출처: boostcamp precourse

module and project

• 파이썬은 대부분의 라이브러리가 이미 다른 사용자에 의해서 구현되어 있음

그런데 어떻게 쓰이나요?

• 남이 만든 프로그램 쓰는 법 객체 > 모듈

모듈과 패키지

• 모듈은 하나의 패키지 안에 들어가 있음
• 모듈: 어떤 대상의 부분 혹은 조각
• 모듈 > 패키지 > 프로젝트(패키지 공개)

모듈

• 프로그램에서 사용하는 작은 프로그램 조각들
• 모듈을 모아서 하나의 큰 프로그램을 개발함
• 프로그램을 모듈화 시키면 다른 프로그램이 사용하기 쉬움 (ex. 카카오톡 게임을 위한 카카오톡 접속 모듈)

모듈 in python

• Built in module

import random
random.randint(1, 1000)

Built-in module인 random을 사용, 난수를 쉽게 생성할 수 있음

패키지

• 모듈을 모아놓은 단위, 하나의 프로그램

직접 구현을 해봐야 알 수 있다!

• 모듈 만들기

1. 파이썬의 module == py. 파일을 의미
2. 같은 폴더에 module에 해당하는 .py파일과 사용하는 .py파일을 저장한 후
3. Import문을 사용해서 module을 호출

# fah_converter.py
def convert_c_to_f(celsius_value):
    return celsius_value * 9.0 / 5 + 32

# module_ex.py
Import fah_converter

print(‘Enter a celsius value: ‘)
celsius = float(input())
fahrenheit = fah_converter.convert_c_to_f(celsius)
print(‘That’s’, fahrenheit, ‘degrees Fahrenheit’)

• Name space
  • 모듈을 호출할 때 범위 정하는 방법
  • 모듈 안에는 함수와 클래스 등이 존재 가능
  • 필요한 내용만 골라서 호출 할 수 있음
  • From과 import 키워드를 사용함

Name space example

• Alias 설정하기 – 모듈명을 별칭으로 써서

import fah_converter as fah 

• 모듈에서 특정 함수 또는 클래스만 호출하기

from fah_converter improt convert_c_to_f

• 모듈에서 모든 함수 또는 클래스를 호출하기

from fah_converter import *

• Built-in module
  • 파이썬이 기본적으로 제공하는 모듈
  • 수많은 파이썬 모듈들은 어떻게 쓸 것인가
  • 구글에 물어본다
  • Import후 help 사용
  • 파이썬 공식 문서를 읽어본다

패키지

• 하나의 대형 프로젝트를 만드는 코드의 묶음
• 다양한 모듈들의 합, 폴더로 연결됨
• __init__, __main__등 키워드 파일명이 사용됨
• 다양한 오픈 소스들이 모두 패키지로 관리됨

패키지 만들기

1) 기능들을 세부적으로 나눠 폴더로 만듦
2) 각 폴더별로 필요한 모듈을 구현함
3) 1차 test python shell (폴더로 구성되어도 모듈처럼 from과 import로 호출가능)
4) 폴더별로 __init__.py 구성하기

• 현재 폴더가 패키지임을 알리는 초기화 스크립트
• 없을 경우 패키지로 간주하지 않음(3.3+ 부터는 x)
• 하위 폴더와 py파일(모듈)을 모두 포함함
• mport와 __all__ keyword 사용(ex. __all__ = [‘image’, ‘sound’, ‘stage’])

5) __main__.py 만들기

패키지 내에서 다른 폴더의 모듈을 부를 때 상대 참조로 호출하는 방법

from game.graphic.render import render_test # 절대 참조
from .render import render_test # .현재 디렉토리 기준
from ..sound.echo import echo_test # ..부모 디렉토리 기준                   

오픈 소스 라이브러리 사용하기

• 두개의 다른 패키지를 설치할 경우엔 패키지끼리 서로 충돌이 날 경우가 있다
• 가상환경 설정하기!

가상환경 설정하기(virtual environment)

• 프로젝트 진행시 필요한 패키지만 설치하는 환경
• 다양한 패키지 관리 도구를 사용함
• 대표적인 도구 virtualenv와 conda가 있음
• Virtualenv + pip: 가장 대표적인 가상환경 관리 도구
• Conda: 상용 가상환경도구, miniconda 기본 도구, windows에서 장점

conda 가상환경

• conda create -n my_project python=3.9
• conda activate my_project: 가상환경 진입
• conda deactivate: 가상환경 나오기
• conda install matplotlib: 가상환경에서 패키지 설치

출처: boostcamp precourse