위키백과의 정의에 따르면 자료형(data type)이란 "컴퓨터 과학과 프로그래밍 언어에서 실수치, 정수, 불린 자료형 따위의 여러 종류를 데이터로 식별하는 분류로서, 더 나아가 해당 자료형에 대한 가능한 값, 해당 자료형에서 수행을 마칠 수 있는 명령들, 데이터의 의미, 해당 자료형의 값을 저장하는 방식을 결정하는 것"이다.

파이썬을 조금이라도 배운 사람이라면 적어도 자료형이 무엇인지는 익숙할 것이다. int, float, list와 같은 예시들이 떠오를 수도 있을 것이다. 하지만 이런 자료형들은 어떻게 만들어진 것이고 무엇을 위해 존재하는 것일까? 그저 유용하게 사용하기만 했지 나는 이 자료형들의 존재 이유에 관해서는 별로 생각해본 적이 없었다. 이 자료형들의 의미에 대해서 알기위해선 과거 컴퓨터 언어들은 어떤 자료형을 가지고 있었는지 알아보면 좋을 것 같다. 예를 들면 여러 컴퓨터 언어 중 가장 할아버지라고 볼 수 있는 C언어다.

 구글에서 C언어의 자료형에 대해서 서치해보면 파이썬과는 사뭇 다른 분위기를 풍긴다. 파이썬은 흔히 수치형으로 퉁치고 넘어가는 자료형이 short, int, long, float, double... 등 바이트 수에 따라 굉장히 세분화하여 분류하고 있다.  char의 경우 파이썬의 문자열과는 달리 보통 글자 "하나"(character)를 뜻한다.  C언어의 경우 파이썬과는 달리 정적 언어이므로 변수를 선언할 때마다 int a같이 특정 자료형을 지정해주어야 하며 위의 자료형들은 변수를 선언할 때 사용하는 "기본 자료형"들이다.

 물론 위의 자료형들은 기본 자료형이고 이 기본 자료형들이 응용되어 더 복잡한 자료형을 만들기도 한다. 하지만 내가 느낀 것은 다른 자료형들도 결국은 저 "숫자"로 귀결된다는 것이다. 문자도 결국 아스키 코드 규칙에 따라 변형된 "숫자"이며, 포인터는 자료가 담긴 메모리의 주소를 "숫자"로 표현한다. C언어에서 배열은 메모리의 연속적으로 저장된 자료 중 맨 앞 자료가 담긴 메모리의 "포인터"이므로 결국 숫자다.

 나는 이런 개념들이 상당히 복잡하다고 느꼈고 숫자를 극한으로 이용하면 이렇게 까지 되는구나라고 생각했다. 하지만 한편으로는 간결해보이기도 한다. 하드웨어에는 0과 1로 이루어진 비트들이 존재하고, 이를 이용해 숫자를 표현하고, 이 숫자를 아스키 코드로 해석하면 문자가 되고, 메모리의 위치를 표시하면 포인터가 된다. 그리고 이 자료들을 메모리에 인접하게 저장하면 배열이 된다. 파이썬에선 잘 느껴지지 않던 자료형들 간의 관계가 너무 잘 보인다.

 파이썬도 결국 런타임이 C언어로 작성된 프로그래밍 언어다. 파이썬은 C언어와는 매우 다르지만 인터프리터가 작동하고 있는 내부에서는 C언어를 이용해 해석되고 있을 것이다. 굳이 그냥도 사용할 수 있는 C언어를 이용해 파이썬이라는 새로운 언어를 만든 것은 분명한 이유가 있을 것이다. 파이썬의 철학에서 이 이유를 추측할 수 있다. 파이썬은 가독성과 단순성, 효율성을 극도로 추구하고 있다. C언어는 한 번 읽고 이해하기가 어려운 것이 사실이며 낮은 가독성은 개발의 효율성을 떨어트리고 커뮤니케이션을 어렵게 한다. 파이썬은 C언어의 이 단점을 해결하기 위해 등장했다고 볼 수 있다.

여기서 파이썬의 자료형을 어떻게 봐야 좋을지에 대한 해답이 나온다. 파이썬의 자료형은 결국엔 C언어의 자료형을 응용해 더 다양한 기능을 수행할 수 있도록 만들어진 것이다. 그렇다면 이 파이썬의 자료형이 C언어의 어떤 번거로움을 해결하기 위해 만들어진 것인지 알게 된다면 그 자료형의 존재 이유가 밝혀지게 되는 것이다. 파이썬의 각 자료형들을 C언어의 관점에서 본다면 어떤 느낌인지 살펴보겠다. 밑의 자료형들은 파이썬의 공식문서 Built-in Types에 등장하는 분류대로 분류한 것이다. 

수치형(numerics)

파이썬의 수치형 자료형은 integer, float, complex 등 수를 나타내는 자료형들을 포괄적으로 부른다. C언어는 수치 자료형을 shor, int, long, float, double등 사용되는 메모리의 바이트를 기준으로 세세하게 나눠놓은 반면 왜 파이썬에서는 수치형을 하나로 뭉뚱그려 묶어서 부르는 경우가 많은 것일까? 파이썬 공식문서에 따르면 파이썬의 integer는 기본적으로 무한한 숫자를 표현할 수 있으며 float는 C언어의 double로 표현된다고 한다. 파이썬은 C언어와 달리 동적 언어이기 때문에 메모리를 할당하고 자료를 집어넣는 C언어와 달리 넣는 자료에 따라 메모리가 자동으로 할당되는 성격이 있기 때문에 굳이 바이트에 따라 수치 자료형을 나누지 않는 것으로 보인다. 또한 수치형에서 파이썬과 C언어가 근본적으로 다른 점은, 파이썬에서는 숫자가 웬만하면 숫자의 용도로 사용된다는 것이다. C언어는 숫자가 문자, 포인터 등의 형태로도 존재하는 것과 달리 파이썬에서는 수치형 자료형의 숫자들이 말 그대로 "숫자"그 자체의 목적으로 존재한다. 즉, 파이썬의 수치형 자료형은 C언어와 달리 상당한 유연성을 가졌으면서 용도 면에서는 더 명확한 자료형이라고 할 수 있다.

시퀀스(Sequence)

파이썬의 시퀀스 자료형은 리스트, 튜플, 문자열, 바이트 등을 포함하는 자료형이다.(다만 문자열과 바이트는 리스트, 튜플과는 조금 다른점이 있다) C언어의 배열과 비슷해보이는데 C언어의 배열과 파이썬의 시퀀스 자료형은 굉장히 큰 괴리감이 느껴졌다. 파이썬이 C언어의 바이트별로 다양한 수치 자료형들을 하나로 통합했다면, 시퀀스 자료형은 C언어의 배열을 세분화, 특수화해서 만들었다는 느낌이 강하다.

파이썬의 시퀀스 자료형은 공통되는 한가지 특징이 있고, 그 특징이 C언어의 배열과의 큰 차이점이다. 그것은 C언어가 데이터를 배열로 저장하는 것과 달리 파이썬은 포인터를 배열로 저장한다는 것이다. 포인터라는 것은 앞에서도 언급했다시피 메모리의 위치를 나타내는 것이다. C언어의 배열은 데이터가 일렬로 저장된 메모리의 맨 앞을 가리키는 포인터이다. C언어가 배열을 다룰땐 포인터를 이용해 배열의 맨 앞부분으로 접근하고, 배열의 끝을 알려주는 메모리가 나올때까지 옆으로 읽어 나간다. 때문에 옆으로 계속 읽어 나가기 위해선 배열이 한가지 자료형만으로 이루어져야 해석할 수 있고, 어디까지 읽어야 하는지 정해줘야 하기에 배열의 길이도 미리 선언해줘야 한다. 반면에 파이썬은 데이터 자체가 아닌 데이터가 담긴 포인터를 배열로 저장하기에 "데이터"의 자료형이 같을 이유가 없다. 어차피 배열 안은 똑같은 포인터 자료형이고, 포인터가 가리키는 데이터의 자료형은 마음대로 바꿀 수 있기 때문이다. 또한 파이썬은 포인터의 배열을 저장할 메모리를 일정 값으로 알아서 선언해주므로 시퀀스의 길이를 직접 선언해 줄 필요가 없다.

그런데 여기서 리스트와 튜플의 차이점이 드러난다. 파이썬에는 객체를 mutable 객체와 immutable 객체로 나눌 수 있는데 mutable 객체는 '뮤턴트' 처럼 값을 바꾸는게 가능하고 immutable 객체는 값을 바꾸는 것이 불가능하다. 리스트는 mutable이고 튜플은 immutable은 이유는, 리스트는 포인터의 배열의 크기가 데이터의 크기에 따라 동적으로 변하는 반면, 튜플은 튜플 생성시의 크기로 고정되기 때문이다. 그래서 리스트는 내부의 데이터가 바뀌더라도 바뀐 크기에 따라 메모리를 알아서 할당하지만 튜플은 그렇지 못하기때문에 오류가 생기는 것이다. 튜플에 + 연산으로 데이터를 추가할 수 있기 때문에 의아하게 생각할 수도 있으나 그것은 튜플에 데이터를 더 붙이는 것이 아니라, 튜플의 데이터와 + 연산해준 데이터를 순서대로 포함한 새로운 튜플을 생성하는 것뿐이다.

C언어의 배열은 튜플과 달리 배열 안의 값을 바꾸는 것에 대해서는 제한이 없다. 어차피 배열 안의 모든 자료형이 동일하기 때문에 다른 값으로 바꾼다고 해서 메모리 사용량이 변하지 않으므로 메모리 크기를 추가로 할당할 필요도 없긴하다. 근데 왜 파이썬은 mutable/immutable 객체를 구분하고 있는 것일까? 대부분의 파이썬 학습서에서 이 부분에 대한 설명은 없이 단순히 리스트는 가변객체이고 튜플은 불변객체라는 차이점이 있다는 식으로 넘어가기 때문에 따로 찾아보는 수밖에 없었다. immutable 객체가 필요한 이유는 크게 두가지로, '스레드 안전(thread-safety)'과 '시간과 메모리의 절약'이다.

스레드 안전은 어느 함수나 변수가 여러 스레드에 의해 호출되더라도 실행에 문제가 없는 것을 말한다. mutable 객체의 경우 값이 변할 수 있기 때문에 어떤 스레드에서 값을 변화시키면 다른 스레드에서의 작업이 잘못될 수 있다. 반면 immutable 객체는 그럴 걱정이 없다. 또한 mutable 객체가 값을 변화시키기 위해 실제로 필요한 메모리보다 더 많은 메모리를 할당하고 있는것과 달리, immutable 객체는 필요한 메모리만 할당시킨다. 때문에 mutable 객체보다 메모리 사용량이 적고 속도도 더 빠르다.

문자열 역시 시퀀스 타입에 속한다. 다만 다른 시퀀스와는 달리 문자 자료형으로 원소들의 자료형이 고정되고, immutable 객체이다. C언어도 문자열을 char의 배열로 다루지만 파이썬 문자열의 편의성이 훨씬 크다. 개인적인 느낌을 말하자면 C언어의 문자열은 문자의 탈을 쓴 배열이라는 느낌이지만 파이썬의 문자열은 더 직관적으로 문자열이라고 느껴진다. C언어에서 문자열을 다루는 것은 매우 어려운 반면 파이썬에서는 쉬운 이유다. 또한 파이썬의 문자열은 문자열끼리의 연산도 제공한다.

매핑(mapping)

매핑 자료형에는 딕셔너리가 속한다. 파이썬의 딕셔너리는 key와 value 구조를 가져서 시퀀스 자료형이 인덱스로 데이터에 접근하는 것처럼 key를 이용해 value에 접근할 수 있다. 딕셔너리의 key가 주어지면 해시함수를 통해 key를 인덱스로 매핑하고, 그 인덱스를 이용해 value를 찾는 방식이다. 이런 자료구조를 해시테이블(hash table)이라고도 한다. 

파이썬의 딕셔너리가 특이한 점은 배열과 해시테이블의 특징을 모두 가졌다는 것이다. 3.6버전부터 파이썬의 딕셔너리는 일정한 순서를 가지게 되었다. 그로 인해 for loop에서 더 유용하게 사용할 수 있게 되었다. 이는 파이썬 딕셔너리 자료형의 내부구조에 indicis 를 저장한 배열이 있기 때문이다. 다만 추가적인 메모리를 요구하기 때문에 시퀀스 자료형보다 메모리 낭비가 크다는 것은 단점이다. 파이썬의 딕셔너리는 JSON 형식의 파일을 다루는 데도 매우 유용하다. JSON 형식 자체가 딕셔너리와 완벽히 매칭되기 때문이다.

C언어에서는 딕셔너리와 같은 해시테이블을 사용하려면 직접 구현해야 한다. 이렇게 다른 언어에서는 직접 구현해서 사용해야하는 자료구조를 기본 자료형으로 제공하고 있다는 것은 파이썬의 철학을 잘 보여주는 사례라고 할 수 있다.

집합(Set)

집합 자료형에는 set과 frozenset이 있다. 두 자료형의 차이는 set은 mutable이고 frozenset은 immutable이라는 점이다. 집합 자료형은 데이터의 탐색이 O(1)로 빠르고 데이터들의 유일성을 보장한다. 사실 집합 자료형은 C언어 뿐만 아니라 다른 프로그래밍 언어에서도 잘 볼 수 없는 자료형이다. C언어에서 집합을 구현하는 것은 번거로운 일이라고 하는데 이런 자료형을 파이썬에선 built-in으로 사용할 수 있다는 것이 매우 편리하다.

마치며

글을 쓰다보니 다른 자료형에 비해 시퀀스 자료형에서 글이 너무 길어졌다. 사실 내가 이 글을 쓰게 된 계기가 시퀀스 자료형에 있기 때문이다. 파이썬을 배웠다고 하면서도 나는 이제까지 자료형들이 왜 존재하는지에 대해서 궁금해본적이 없는데, 리스트와 튜플에 대해 생각하다가 "리스트도 튜플이 할 수 있는 작업들을 모두 할 수 있는데 튜플이 왜 필요하지?" 라는 생각이 문득 들게 된 것이다. 나는 평소에도 배열을 쓸 일이 있으면 리스트를 사용하지 튜플을 사용한 적은 거의 없었고 딕셔너리의 items나 함수의 리턴값 정도로나 봐왔기 때문이다. 튜플에 대해 생각하다보니 다른 자료형들에 대해서도 생각하게 되었다. 그래서 결국 이번 기회에 한번 제대로 조사해보자는 생각으로 이 글을 작성하게 된 것이다. 좀 더 C언어랑 잘 비교하면서 본질을 꿰뚫 수 있는 글이 되었으면 좋았을텐데 C언어에 대한 사전 지식이 부족해서 아쉽다. 하지만 이번 기회에 자료형에 대해 깊게 이해하게 되면서 좀 더 파이썬과 가까워진 느낌이다. 앞으로도 종종 내가 가볍게 넘겨버려서 놓쳐버린 인사이트들을 다시 깊게 배우면서 되찾아야겠다.

• 링크: https://programmers.co.kr/learn/courses/30/lessons/43105

def solution(triangle):
    n_layer = len(triangle)
    memory = [[0 for j in range(len(triangle[i]))] for i in range(n_layer)]


    for layer in range(n_layer-1, -1, -1):
        if layer == n_layer-1:
            for idx, node in enumerate(triangle[layer]):
                memory[layer][idx] = node
        else:
            for idx, node in enumerate(triangle[layer]):
                memory[layer][idx] = node + max(memory[layer+1][idx], memory[layer+1][idx+1])

    return memory[0][0]

• 메모이제이션으로 풀이했다. 삼각형의 밑바닥부터 시작해서 왼쪽과 오른쪽 노드 중 큰 값을 판별해서 자기 자신 값과 더한 후, 그 값을 메모리의 해당 인덱스에 저장했다. 그런 방식으로 풀면 memory[0][0]에는 정답이 들어가게 된다.
• 일단 트라이앵글의 모양이 이진트리와 유사한 것을 이용해서 문제를 분할해보려 했다. 왼쪽 삼각형에서 최대 합, 오른쪽 삼각형에서 최대합을 구한 뒤, 그 중에서 더 큰 값을 자기 자신과 더하는 방식으로 재귀적으로 풀 수 있을 것 같았다. 그 후 재귀적 풀이를 메모이제이션으로 변형했다.

• 링크: https://programmers.co.kr/learn/courses/30/lessons/49189

from collections import deque, defaultdict
def solution(n, vertex):
    graph = defaultdict(list)
    distance = {i:0 for i in range(1, n + 1)}
    queue = deque([[1, 0]])

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

    while queue:
        node, dist = queue.popleft()
        if distance[node] == 0:
            distance[node] = dist

            for i in graph[node]:
                queue.append([i, dist+1])

    distance[1] = 0
    distance = list(distance.values())
    max_dist = max(distance)

    return distance.count(max_dist)

• BFS를 이용해서 1번 노드와 다른 노드들 간의 최소 거리를 구한 후 가장 먼 노드의 갯수를 세었다.
• 처음엔 최소힙을 이용한 다익스트라 알고리즘을 이용해서 풀이하려고 했는데 오히려 시간초과가 났다. 일반 BFS보다 다익스트라 알고리즘이 더 효율적이라고 생각해왔었는데 오히려 더 효율적이지 못했던 것이다. 찾아보니 노드 간의 거리가 모두 똑같은 경우 BFS가 더 효율적일 수 있다고 한다.

• 링크: https://programmers.co.kr/learn/courses/30/lessons/42895

def solution(N, number):
    if N == number:
        return 1

    candidate = {1:[N, -N]}
    key = 2

    while True:
        new_candidate = set()
        new_candidate.add(int(str(N) * key))
        new_candidate.add(-int(str(N) * key))

        for i in range(1, key):
            lst_x = candidate[i]
            lst_y = candidate[key - i]

            for x in lst_x:
                for y in lst_y:
                    new_candidate.add(x + y)
                    if y != 0:
                        new_candidate.add(x // y)
                    new_candidate.add(x * y)
                    new_candidate.add(x - y)

        candidate[key] = list(new_candidate)

        if number in candidate[key]:
            return key

        key += 1

        if key > 8:
            return -1

• 다이나믹프로그래밍 중 메모이제이션을 사용해서 풀었다. N을 k번 사용해서 나올 수 있는 모든 값을 N(k)라고 할 때, N(k)는 <N(1), N(k-1)>, <N(2), N(k-2)>... 등의 조합으로 구할 수 있다. 따라서 N(k)는 더 하위 문제의 값들을 조합해서 만들어지는 분할정복이 가능한 문제라는 뜻이다.

• 이 코드에서 사용한 풀이는 N을 1번 써서 나올 수 있는 값, 2번 써서 나올 수 있는 값.. 을 딕셔너리에 저장하고 N을 3번 써서 나올 수 있는 값들을 구해야할 때엔 1번써서 나올 수 있는 값 리스트와 2번 써서 나올 수 있는 값 리스트를 불러와 조합하는 방식이다.

• N == number인 경우를 고려하지 못하여 생각보다 푸는 시간이 길어졌다.

• 이 코드에선 조합이 뒤집어지는 경우를 빼지 않았기 때문에 예를 들어 key가 3일 경우 (1, 2), (2, 1) 같은 식으로 두번씩 값을 구하게 되기 때문에 시간적으론 완전히 효율적이지 않다. key가 8일 경우까지만 고려하면 되기에 고치지 않았으나 이 부분을 고치면 더 완벽한 답이 될 것 같다.

링크: https://www.acmicpc.net/problem/11047

N, K = map(int, input().split())
coins = []
answer = 0

for i in range(N):
    value = int(input())
    coins.append(value)

for value in coins[::-1]:
    n, K = divmod(K, value)
    answer += n

print(answer)

• 동전문제를 그리디 방식으로 풀이하는 것은 전에 파이썬 알고리즘 리뷰 책으로 공부를 했을 때에도 해본 것이라 어려운 문제는 아니었다. 다시 한번 그 책의 내용을 생각해보면 동전의 액수가 서로 배수 관계일 때만 그리디 방식으로 이 문제를 풀 수 있다. 동전의 액수가 배수 관계가 아닌 동전이 하나라도 있을 경우 그리디 방식으로 풀 수 없다.
• 구현은 어렵지 않았지만 뒷부분에서 약간 실수가 있어 첫 제출은 시간 초과가 났다. 그 코드는 동전의 갯수를 세는 방식을 반복문을 사용했는데 시간초과가 나서 그 다음 제출한 코드는 위처럼 divmod를 사용하여 나눗셈의 몫과 나머지를 이용했다.

시간초과가 난 풀이

N, K = map(int, input().split())
coins = []
answer = 0

for i in range(N):
    value = int(input())
    coins.append(value)

for value in coins[::-1]:
    while K >= value:
        K -= value
        answer += 1

print(answer)

링크: https://www.acmicpc.net/problem/1003

def fibonacci(n):
    if n == 0:
        return 1, 0
    elif n == 1:
        return 0, 1

    prev_0, prev_1 = 1, 0
    present_0, present_1 = 0, 1

    for i in range(n - 1):
        prev_0, prev_1, present_0, present_1 = present_0, present_1, present_0 + prev_0, present_1 + prev_1

    return present_0, present_1

n = int(input())

for i in range(n):
    input_n = int(input())
    answer = fibonacci(input_n)
    print(answer[0], answer[1])

• 동적계획법을 사용하는 피보나치 풀이는 워낙 많이 봐서 외운지라 어렵지 않게 풀었다. 다만 이 문제는 피보나치 수열을 직접 구현하는 것이 아니라 0과 1을 호출하는 횟수를 구하는 문제라 조금은 신선했던 것 같다.
• 나는 0을 호출하는 횟수와 1을 호출하는 횟수를 따로따로 변수로 선언해서 prev_0, prev_1, present_0, present_1로 4개의 변수를 사용했는데 좀 더 간결한 풀이가 있지 않을까 싶어 아쉬운점이 있다.

링크: https://www.acmicpc.net/problem/15649

from collections import deque
n, m = map(int, input().split())

lst = [str(i) for i in range(1, n + 1)]
queue = deque([[str(i)] for i in lst])
answer = []

while queue:
    pop = queue.popleft()

    if len(pop) == m:
        print(' '.join(pop))
        continue

    for i in lst:
        if i not in pop:
            temp = pop + [i]
            queue.append(temp)

• 사실 파이썬에는 itertools 패키지에 permutation을 만들 수 있는 메소드가 있어 직접 구현할 필요는 없으나 BFS를 연습해볼 생각으로 일부러 BFS로 풀이했다.
• collections의 deque를 사용하여 큐를 만들고 그 안에 시작할 수 있는 모든 노드를 시작점으로 한 route를 리스트로 넣어 구현했다.

정렬

K 번째 수

• start와 end를 input으로 받아 sorted하고 k번째 수를 인덱싱으로 뽑는다.

def solution(array, commands):
    answer = []
    for command in commands:
        # start, end 저장
        start = command[0] - 1
        end = command[1]
        k = command[2] - 1

        # 자른 배열 sorted
        temp = sorted(array[start:end])
        answer.append(temp[k])
    return answer

가장 큰 수

• 처음엔 정렬로 접근했지만 numbers에 들어오는 숫자의 자릿수가 모두 다를 가능성이 있어서 잘 풀리지 않았다. 예를 들어 3, 30이 들어올경우 330이 맞는 답이지만 단순히 정렬로 풀면 303이 되어버린다.
• 검색을 통해 다른 사람들의 풀이를 참고하니 functools.cmp_to_key 메소드를 쓴 풀이가 눈에 띄었다.
• cmp_to_key는 sorted와 같은 정렬 함수의 key 매개변수에 함수를 전달할 때 사용되는 함수로, 두개의 인수를 받아들이고 첫번째 인수를 기준으로 그들을 비교하여 작으면 음수, 같으면 0, 크면 양수를 반환하는 비교함수여야 한다.

cmp-to-key 예시

import functools

def xy_compare(n1, n2):
    if n1[1] > n2[1]:         # y 좌표가 크면
        return 1
    elif n1[1] == n2[1]:      # y 좌표가 같으면
        if n1[0] > n2[0]:     # x 좌표가 크면
            return 1
        elif n1[0] == n2[0]:  # x 좌표가 같으면
            return 0
        else:                 # x 좌표가 작으면
            return -1
    else:                     # y 좌표가 작으면
        return -1

src = [(0, 4), (1, 2), (1, -1), (2, 2), (3, 3)]
result = sorted(src, key=functools.cmp_to_key(xy_compare))
print(result)

• cmp_to_key는 정렬을 할 때, 대소관계를 새로 정의할 수 있는 유용한 함수로 꼭 암기해둬야겠다고 생각했다.

# 모범 답안
import functools

def comparator(a,b):
    t1 = a+b
    t2 = b+a
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) #  t1이 크다면 1  // t2가 크다면 -1  //  같으면 0

def solution(numbers):
    n = [str(x) for x in numbers]
    n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
    answer = str(int(''.join(n)))
    return answer

H-Index

• citations를 내림차순으로 정렬하여 반복문을 돌면서 h번 이상 인용된 논문의 갯수가 몇개 포함되어 있는지 체크할 수 있도록 한다.
• max를 이용해 h를 계속 최댓값으로 업데이트하여 최댓값을 리턴하도록 한다.

def solution(citations):
    # 내림차순 정렬
    citations.sort(reverse=True)
    h = 0 

    # 반복문을 돌면서 h값 최대화
    for i in range(len(citations)):
        if citations[i] >= i+1: 
            h = max(h, i+1)
    return h

힙(Heap)

더 맵게

• 배열을 heapq로 만든 뒤, 문제 조건에 따라 두번 heappop을 하고 새 값을 만들어 배열에 다시 heappush하는 것을 반복한다.
• 다만 계속 반복해도 모든 음식의 스코빌 지수가 K 이상으로 올라가지 않을 경우 -1을 리턴해야 하므로 heap에 마지막 남은 원소하나가 K보다 큰지 작은지 판별하는 예외처리를 추가한다.

def solution(scoville, K):
    import heapq
    # 힙 만들기
    heapq.heapify(scoville)

    # 예외 처리(배열이 비어있을 경우)
    if sum(scoville) == 0 and K > 0:
        return -1

    cnt = 0
    # 과정 반복(배열에 원소가 하나만 남을때까지)
    while len(scoville) > 1:
        p = heapq.heappop(scoville)
        # 최솟값이 K보다 작을 경우(모든 음식이 K 이상이 아님)
        if p < K:
            q = heapq.heappop(scoville)
            heapq.heappush(scoville, p+2*q)
            cnt += 1
        # 모든 음식이 K 이상임 -> break
        else:
            break

    # 모든 과정을 거쳤음에도 K 이상이 되지 않으면 -1 리턴
    if scoville[0] < K:
        return -1

    return cnt

디스크 컨트롤러

• 이 문제의 목적은 작업 요청부터 종료까지 걸린 시간의 평균을 최소화해야 하므로, 작업 요청부터 종료까지의 시간을 계산하여 heap에 넣은뒤, heappop으로 처리한 작업을 없애는 식으로 구현한다.

import heapq
def solution(jobs):
    # 먼저 요청한 작업이 맨 뒤로 가게 정렬
    jobs.sort(reverse=True)
    result = 0
    length = len(jobs)

    # 요청받은 작업을 담아두는 heap
    on_request = []
    # 걸린 시간을 저장하는 변수
    time = 0

    # 모든 작업을 처리할때까지 반복문
    while jobs or on_request:
        # on_request에 해당 시간에 요청받은 작업 heappush
        while (not on_request) or (jobs and time >= jobs[-1][0]):
            job = jobs.pop()
            # 걸리는 시간을 기준으로 heappush
            heapq.heappush(on_request, [job[1], job[0]])

        # 처리할 작업을 heappop
        work = heapq.heappop(on_request)

        # 만약 요청받은 시간이 현재 시간보다 뒷 시간일 경우, time을 요청받은 시간으로 변경해주기
        if time < work[1]:
            time = work[1]

        # 걸린 시간을 time에 더해주고, 평균 시간을 구하기 위해 result에 요청부터 종료까지의 시간을 더해주기
        time += work[0]
        result += time - work[1]

    return int(result / length)

이중 우선순위 큐

• 최솟값을 pop할때는 heapify, heappop을 이용하고, 최댓값을 pop할때는 sort와 pop을 사용한다.
• heapify + heappop의 시간복잡도는 O(n) + O(1) = O(n), sort + pop의 시간복잡도는 O(n log n) + O(1) = O(n log n) 이므로, 전체 알고리즘의 시간복잡도는 평균적으로 추출 명령의 수가 K일때, O(K * n log n)일 것이다.
• 두개의 배열을 사용하는 방법도 생각해봤지만 두 배열에서 동일한 값을 지우는 과정에서 더 많은 시간이 소요될 것 같아 이 방식으로 변경했다.

import heapq
def solution(operations):
    q = []

    for op in operations:
        op = op.split()
        if op[0] == 'I':
            q.append(int(op[1]))
        elif op[0] == 'D':
            if q:
                if op[1] == '1':
                    q.sort()
                    q.pop()
                else:
                    heapq.heapify(q)
                    heapq.heappop(q)

    if not q:
        return [0, 0]

    return [max(q), min(q)]

DFS & BFS

타겟 넘버

• root가 0이고 그 아래로 + number와 - number 해준 것들이 가지로 달려있는 트리 형태의 그래프로 생각한다.
• dfs를 이용해 모든 경우의 수를 탐색하고 그 갯수를 센다.

def solution(numbers, target):
    n_numbers = len(numbers)

    # dfs 구현
    def dfs(index, csum):
        cnt = 0

        if index == n_numbers:
            # target이면 1, target 아니면 0
            return int(csum == target)

        # cnt에 모두 더해주기
        cnt += dfs(index + 1, csum + numbers[index])
        cnt += dfs(index + 1, csum - numbers[index])

        return cnt

    return dfs(0, 0)

네트워크

• input을 이용해서 그래프 맵을 그리고 그래프 맵을 DFS로 순회하며 방문하는 노드들을 visited에 append한다. 그 후 DFS가 끝날 때 카운트를 하여 네트워크의 갯수를 센다.

from collections import defaultdict
def solution(n, computers):
    graph, stack = defaultdict(list), []
    visited = []

    # 그래프 맵 만들기
    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1:
                graph[i].append(j)

    # dfs 구현
    def dfs(a):
        stack.append(a)
        visited.append(a)
        while stack:
            for i in graph[stack.pop()]:
                if i not in visited:
                    stack.append(i)
                    visited.append(i)

    # 네트워크 순회가 끝나면 count + 1
    count = 0
    for i in list(graph):
        if i not in visited:
            dfs(i)
            count += 1

    return count

단어 변환

• 한 글자만 다른 단어 사이가 연결된 그래프라고 생각하고 BFS로 타겟 단어까지 가는 최단 경로를 찾는 문제로 치환하여 푼다.

from collections import defaultdict, deque
import sys

def solution(begin, target, words):
    graph = defaultdict(list)
    queue = deque()
    answer = []
    words.append(begin)

    # 그래프 맵 만들기
    for i in words:
        for j in words:
            if i != j:
                for idx in range(len(i)):
                    if i[:idx] + i[idx + 1:] == j[:idx] + j[idx + 1:]:
                        graph[i].append(j)

    # BFS 구현
    def bfs(w):
        min_step = sys.maxsize
        traced = []
        queue.append((0, w))
        while queue:
            step, temp = queue.popleft()
            if temp == target:
                # step 수를 세어 최소 step인지 확인
                min_step = min(step, min_step)

            for word in graph[temp]:
                # 최단경로를 알아내야하므로 이미 방문한 노드는 방문 하지 않음
                if word not in traced:
                    traced.append(word)
                    queue.append((step + 1, word))

        return min_step

    answer = bfs(begin)

    # 최소 step이 나오지 않았으면 0 리턴
    if answer == sys.maxsize:
        return 0
    else:
        return answer

여행경로

• 사전 순서로 방문해야하므로 공항 이름을 정렬하여 그래프 맵으로 만들고, DFS로 그래프에서 해당 공항을 pop해가면서 모든 노드를 순회하는 루트를 찾는다.

def solution(tickets):
    from collections import defaultdict
    graph = defaultdict(list)

    # 그래프 맵 만들기(알파벳 순서로 방문하기 위해 sorted)
    for a, b in sorted(tickets, reverse=True):
        graph[a].append(b)

    route = []

    # dfs 구현
    def dfs(a):
        while graph[a]:
            # 알파벳 순서로 방문하기 위해 pop
            dfs(graph[a].pop())
        route.append(a)


    dfs('ICN')

    # 나중에 방문한 곳이 배열의 앞에 위치하게 되므로 뒤집기
    return route[::-1]