문제 링크: https://leetcode.com/problems/sum-of-distances-in-tree/

문제

문제를 요약하자면 tree가 주어질 때 모든 정점으로부터의 거리가 최소가 되는 정점에서의 모든 정점으로까지의 길이의 합을 출력하는 문제가 되겠습니다.

직관

tree기 때문에 Cycle이 없습니다. 따라서 한 edge를 제거했을 때,  그래프로 나눠집니다.

A와 B를 잇는 edge가 있다고 가정해봅시다. 그리고, A쪽 그래프에있는 모든 노드로부터 A까지의 거리를 알 수 있다고 가정해봅시다.

그럼 B쪽 노드의 관점에서 봤을 때는 우리는 모든 A쪽 그래프의 노드로부터 B까지의 거리의 총합을 다음 수식으로 구할 수 있습니다. 

$$TotalDist_{A side} + NodeCnt_{A side}$$

왜냐하면 A쪽 노드로부터 B쪽 노드로 오는 모든 길은 edge A->B를 지날 수 밖이 없기 때문이죠.

접근법

그러므로 우리는 DP를 계산할 수 있습니다. 

노드 N과 S가 있을 때, edge (N,S)에 의해서 N쪽 graph와 S쪽 graph 로 나뉘게됩니다.

그리고
$cnt[n][s] = $ $n$ 쪽 그래프에 있는 노드의 수
$dist[n][s] =$ N쪽 그래프에서 S로 가는 총 거리의 합

라고 정의할 때 우리는 이 두 배열을 다음과 같은 방식으로 업데이트할 수 있습니다.

$G[n]$ 을 노드 N과 이어진 모든 이웃 노드들을 포함하고 있을 때

$$ dp[n][s] = sum_{i \in G[n], i \neq s}(dp[n][i] + cnt[n][i])$$
$$ cnt[n][s] = sum_{i \in G[n], i \neq s}(cnt[n][i])$$

로 계산되게 됩니다. 

복잡도

이 풀이는 시간복잡도와 공간복잡도가 오직 edge의 개수의 영향받으며, edge는 총 N-1개 존재합니다.

시간 복잡도: $O(N)$

공간 복잡도:  $O(N)$

코드

class Solution:
    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
        self.G = [[] for i in range(n)]
        
        for e in edges:
            self.G[e[0]].append(e[1])
            self.G[e[1]].append(e[0])
        
        ans = []
        for i in range(n):
            ans.append(self.dp(i, -1)[0])
        return ans
    
    @cache
    def dp(self, pnode, source):
        dist = 0
        cnt = 0
        for n in self.G[pnode]:
            if n == source:
                continue
            n_dist, n_cnt = self.dp(n, pnode)
            dist += n_dist + n_cnt
            cnt += n_cnt
        cnt += 1
        return dist, cnt

영문 솔루션

https://leetcode.com/problems/sum-of-distances-in-tree/discuss/2939374/Python-Super-Simple-O(N)-DP-Solution 

Codejam 문제 풀이

sub Title: (1) Round1

구글 code jam은 일반적으로 난이도 순으로 나오기때문에 순서대로 풀면된다.

순위

2000등 밖으로 밀려나서, 1A 라운드 통과는 못했다.

거의 4년만에 제대로된 대회에 참가하는것 같은데 그래서 그런지 정말 머리가 안돌아간다.

1B는 통과할만한 것같은데, 간만에 문제를 풀어서 그런가 문제 푸는속도도 코드도 영 맘에들지 않는다.

무엇보다 아이디어 떠오르는 속도가 정말 너무 많은 trial-and-error을 필요로한다.

Append Sort

문제는 아래에서 자세히 읽을 수 있다.

문제 설명

정수가 N개가 주어진다.

정수 N개를 정렬하고 싶은데, 정수끼리의 순서를 바꿀수 없다.

우리가수행할 수 있는 연산은 각 정수에다가 숫자들을 더하는 건데 예를 들면 123이 있다면 여기다가 4를 더해서 1234로만드는 이런연산이가능하다.

123 → 1234

이런 연산을 최소한으로 수행해서 strictly increasing order로 만들어라.

sample Input

Sample Output

설명:

첫번째는 아래처럼 추가하면 100, 700, 1000 으로 오름차순으로 만들수 있다.

100

7 → 700

10 → 1000

총 0을 4번 추가했고, 이거보다 적게 추가해서 오름차순으로 만들 수 없기 때문에 답은 4다 

솔루션 코드

for tc in range(int(input())):
    N = int(input())
    X = list(map(int, input().split(" ")))

    ans = 0
    for i in range(1, N):
        if X[i] > X[i-1]:
            continue
        s_b = list(str(X[i-1]))
        s_p_max = list(str(X[i]))
        s_p_min = list(str(X[i]))
        count = 0
        ori_len = len(s_p_max)
        while int("".join(s_b)) >= int("".join(s_p_max)):
            s_p_max += "9"
            s_p_min += "0"
            count += 1
        ans += count
        if int("".join(s_b)) < int("".join(s_p_min)):
            X[i] = int("".join(s_p_min))
        else:
            # same
            X[i] = X[i-1]+1

    print(f"Case #{tc+1}: {ans}")

그지처럼 풀었다.

첫번째 원소는 건드리지 않아도 되니까 range(1, N) 으로 시작한다. 시작부터 크다면 신경쓸필요없으니까 그리고 뒤를 9로 일단 채워나가면서(그 자리수에서 체울 수 있는 가장 큰 수) 될때까지 자리수를 늘려나간다.

그리고 늘려나간 최종 값중에서 가장 작은 값 (예를들자면, 10에서 2개의 digit을 추가했다면, 1099이 최대값, 1000이 최솟값이 된다.)이 배열의 이전 값 (s_b, X[i-1]) 보다 크다면 그게 답이 되기 때문에 X[i]에 그 값 자체를 넣어준다. int("".join(s_p_min))

만약 최솟값이 같다면, X[i-1]의 값에 +1해주면 된다. 이부분은 +1해줌으로서 다른자리까지 전부 변화시켜주려면 9여야하는데, 모두 9로 되어있는 경우는 14번 째 줄의

while int("".join(s_b)) >= int("".join(s_p_max))

에서 컷팅당한다. 즉 +1만해줘도된다. 

이해가 안가시면 질문주세요. 대충 설명드립니다.

Prime Time

문제는 아래에서 자세히 읽을 수 있다.

소수가 주어진다. (중복된 소수들도 주어진다.)

소수를 두 그룹으로 만들 것인데, 한 그룹은 덧셈으로, 한 그룹은 곱셈으로 모든 연산을 수행할것이다. 이 때 합을 한 그룹과 곱을 한 그룹의 계산 값이 같아야 한다.

예를 들자면

2 - 2개

3 - 1개

5 - 2개

7 - 1개

11 - 1개

가 주어졌을 때,

2+ 2 + 3 + 7 + 11 == 5 * 5

가 되고 두 그룹의 합은 25로 같다. 이렇게 만들 수 있는 가장 큰 값을 구하라.

중요한 인풋 설명

소수는 499 이하의 것들로만 주어진다.

소수는 서로다른 소수 95개 까지 주어질 수있으며, 각 소수는 여러개 존재할 수 있다.

Sample Input

Sample Output

설명:

첫번째 input은 2가 2개, 3이 1개, 5가 2개, 7이 1개 11이 1개다.

이 때, 더하기 그룹은 2, 2, 3, 7, 11을 선택하고, 나머지 곱하기 그룹은 5 5를 선택하면 최대값 25가 뽑인다. 그래서 답은 25

Test Set 1 솔루션 소스코드

$2≤N_1+N_2+⋯+N_M≤10$. (소수의 총 개수가 10개 이하)

from functools import reduce
for tc in range(int(input())):
    N = int(input())
    P = []
    for i in range(N):
        p_i, n_i = map(int, input().split())
        P += [p_i for j in range(n_i)]
    ans = 0
    for i in range(1 << len(P)):
        arr = list(enumerate([1 if i & (1 << j) else 0 for j in range(len(P))]))
        arr_mul = reduce(lambda x, y: x * y, [P[i] if v == 0 else 1 for i, v in arr])
        arr_sum = sum([P[i] if v == 1 else 0 for i, v in arr])
        if arr_mul == arr_sum:
            ans = max(ans, arr_mul)
    print(f"Case #{tc+1}: {ans}")

소수의 총 개수가 10개 이하다.

잘모를 땐 다해보자. 모든 소수를 분해한다. 0번그룹 1번그룹

그래서 두개의 곱과 합을 구한 후 두개가 같다면 ans로 출력한다.

Test Set 2 솔루션 소스코드

$2≤N_1+N_2+⋯+N_M≤100$. (소수의 총 개수가 100개 이하)

from functools import reduce

for tc in range(int(input())):
    N = int(input())
    P = []
    UP = {}
    for i in range(N):
        p_i, n_i = map(int, input().split())
        UP[p_i] = n_i
        P += [p_i for j in range(n_i)]
    all_sum = sum(P)
    ans = 0
    unique_p = UP.keys()
    for t in range(all_sum, 0, -1):
        is_fail = False
        may_ans = t
        tot = 0
        for p in unique_p:
            p_count = UP[p]
            while t % p == 0:
                t //= p
                p_count -= 1
                tot += p
                if p_count < 0:
                    is_fail = True
                if is_fail:
                    break
            if is_fail:
                break
        if t != 1:
            is_fail = True
        if not is_fail and all_sum - tot == may_ans:
            ans = may_ans
            break
    print(f"Case #{tc+1}: {ans}")

소스코드가 개판이다.

자 이제 어떻게 줄일 수 있을 지 생각해보자. 100개니까 모두를 해보는 건 불가능하다. ($2^{100}$ 은 안봐도 TLE)

합과 곱중 하나를 고정시켜야하는데, 생각해보면 모든 수의 합은 매우 작다. 그러니까 곱하는걸 선택할 때 많은 수를 곱할 수 없다.

100개를 다합쳐보면 최대 얼마가나올까?

$499 * 100 = 49900$ 밖에 안나온다.

그럼 모든 소수를 다더하고, 1씩 빼가면서 그 수를 만들 수 있는지 확인한다. 만약 만드는 것을 실패하면, 불가능하다는 것이고, 만드는 것을 성공하면 만드는데 든 소수의 합을 뺀 것이 지금의 수인지 체크하면 된다. 그 코드는 아래와 같다.

        if not is_fail and all_sum - tot == may_ans:
            ans = may_ans
            break

시간복잡도는 대충 49900 * len(unique_p) * log (49900) 정도 될껀데, 뒤에껀 대충 빼고, 계산해도 49,90,000 정도다. 매우적으니까 당연히 통과다. 문제는 테스트 셋 3인데...

Test Set 3 솔루션 소스코드

$2≤N_1+N_2+⋯+N_M≤10^{15}$. (소수의 총 개수가 $10^{15}$개 이하)

이거 보고 솔직히 아 당연히 수학문제겠지 하고 제꼈다. 구글 수학문제좋아하니까 그럴꺼라고 생각했다.

그런데 멍청했다.

from functools import reduce
for tc in range(int(input())):
    N = int(input())
    P = []
    UP = {}
    all_sum = 0
    for i in range(N):
        p_i, n_i = map(int, input().split())
        UP[p_i] = n_i
        all_sum += p_i * n_i
    ans = 0
    unique_p = UP.keys()
    for t in range(all_sum, max(0, all_sum-8982), -1):
        is_fail = False
        may_ans = t
        tot = 0
        for p in unique_p:
            p_count = UP[p]
            while t % p == 0:
                t //= p
                p_count -= 1
                tot += p
                if p_count < 0:
                    is_fail = True
                if is_fail:
                    break
            if is_fail:
                break
        if t != 1:
            is_fail = True
        if not is_fail and all_sum - tot == may_ans:
            ans = may_ans
            break
    print(f"Case #{tc+1}: {ans}")

거의 메인 로직은 똑같고 중요하게 추가된게 아래 이거 하나다.

for t in range(all_sum, max(0, all_sum-8982), -1):

생각해보면, 곱셈으로 아무리 빼고싶어도 소수를 빼는데 한계가 있다. 곱셈이 너무 커지니까. 그러니까 곱셈측에도 컷팅같은 느낌을 줄 수 있다.

잘 생각해보면 499를 $10^{15}$ 더해봤자 $499*10^{15}$ 이다. 아니 엄청 큰 숫자아니냐고? 곱셈의 세계에서는 매우 작은 숫자다.

그럼 소수 최대 몇개를 뺄 수 있을까. 를 계산해보면

$$\text{log}_2(499*10^{15})=17.xx$$

이긴한데, 사실 계산하기 귀찮으니까 아무리그래도 $499^{18}$ 보다는 작을거라고 생각할 수 있다. 그러니까 아무리 빼고싶어도 499를 18번보다 많이 뺄수없으며, 어떤 소수든 18개이상 빼면 전체합을 넘어가게된다.

즉 뺄수있는 것의 범위가 $499*18=8982$보다는 작게된다는 것이다.

그래서 정말 뺄수있는최소값을 range(all_sum-8982, all_sum) 로 잡으면 되는데, all_sum-8982 가 0보다 작을수있으니까 max를 씌워준것일 뿐이다.

이건 대회중에 떠올리지 못한 아이디어다. 답안지보고 아 수학아니었는데... 하고 너무 아쉬워서 딱 저 아이디어 추가하고 메모리문제좀개선해서 제출했떠니 바로 답이 뜨더라.

아쉽다아쉬워...

Hacked Exam

문제 해석을 잘못하고있다가 10분전에 해석을 완료했다;

테스트셋 1번은 그냥 긁을만했는데 긁었으면 비벼볼만했을텐데 아쉽다.

마무리

아쉽네. 다음번엔 더잘해야징. 1B에는 다음라운드갈수있지않을까.

자 오늘을 마지막으로... 하려고 했는데 생각보다 길어져서 다시 나누게 되었습니다.

생각 날때마다, 여러가지 잡기술들을 모아서 알려드리도록 할께요.

오늘은 python에서 기본적으로 제공해주는 정렬을 활용해서 조금이라도 코드를 편하고, 가독성있게 (나에게만 일지도...) 짤 수 있는 비법들을 알려드리도록 하겠습니다.

오늘 배울 내용들을 간단히 나열해드리자면,

• sort, sorted 함수
• enumerate 함수
• for문에서 이름으로 원소 꺼내오기
• 이들을 활용한 정렬처리 잡기 술

입니다.

정렬 트릭

정렬은 문제를 풀때 굉장히 자주 사용하게 되는 라이브러리입니다.

단순히 오름차순으로 정렬할 때 python에서 제공하는 sorted 라이브러리나 sort라이브러리를 사용합니다. 간단한 정렬 문제를 해보도록 할께요.

정렬 기초

이번에 풀어볼 문제는 수 정렬하기 입니다.

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력

예제 출력

문제가 간단해서 좋군요. 뭐가 문제겠어요? 정렬을 알아보는 가벼운 예제니까 빠르게 후딱처리하고 넘어갑시다.

사실 이 문제는 2가지 해법이 있어요. 크게 어려운 해법은 아니고, 원본 배열을 건드리냐 안건드리냐에 따라서 달라지게 되죠. 일단 먼저 보실까요?

답 코드1 - sorted

N = int(input())
D = [int(input()) for i in range(N)]
sorted_D = sorted(D)
for num in sorted_D:
    print(num)

답 코드2 - sort

N = int(input())
D = [int(input()) for i in range(N)]
D.sort()
for num in D:
    print(num)

sorted는 D를 건드리지 않고 새롭게 정렬된 배열을 return합니다.

그에 비해서 sort는 D의 배열 자체를 정렬된 상태로 바꿔버리죠.

이정도면 기본은 되었습니다. 이제 트릭을 알아보러 가시죠.

복잡한 정렬 수행하기

기본적으로 제공되는 함수는 여러가지 조건으로 복잡한 정렬을 수행하기위해서는 비교하기 위한 함수를 넘겨줘야하는 불편한 점이 있죠.

특히 많은 문제에서 여러가지 조건에 따라 비교를 수행해야하는 경우가 왕왕있습니다.

알고리즘은 정확하게 짜는 것도 중요하지만, 빠르게 짜는게 중요한 역할을 합니다. 그때 복잡한 비교구문을 일일이 작성해서 정렬하는 것은 시간낭비입니다.

빠르게 정렬하기 위한 꿀팁을 알려드릴께요. 바로 python 내장 정렬을 이용하는 방법입니다.

python 내장정렬은 다음과 같은 특징을 가지고 있습니다.

1. 정렬은 오름차순으로 수행한다. (위의 예제에서 보여드렸죠?)
2. 만약 정렬의 내용물이 tuple이라면 tuple의 낮은 인덱스에 있는 원소를 기준으로 정렬한다.

2번 항목이 잘 이해가지 않으실꺼에요. 간단한 예제를 드릴께요.

a = [
    (2, 4),
    (2, 3),
    (1, 4),
    (1, 3),
]
a.sort()

print(a)

이 코드의 출력은 무엇일까요? 바로

[(1, 3), (1, 4), (2, 3), (2, 4)]

가 됩니다.

첫번 째 원소 1과 2를 비교해서 오름차순으로 정렬을 수행하죠.

만약 첫번째 원소가 같다면 두번째 원소 3과 4를 비교해서 오름차순으로 정렬을 수행합니다.

직관적으로 당연히 그렇게 되어야 맞겠죠?

바로 이 트릭을 이용해서 복잡한 정렬을 추가적인 함수를 작성하지 않고 수행할 수 있습니다.

바로 문제로 가실께요.

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

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

예제 입력

예제 출력

자 다소 복잡하죠? 하지만 코드는 문제보다 짧고, 쉽습니다.

바로 보시면서 이해하시죠.

정답 코드

N = int(input())
D = [input() for i in range(N)]
D = set(D)
D = [(len(s), s) for s in D]
D.sort()

for l, s in D:
    print(s)

1~2: 첫 두줄은 늘상 같은 인풋받는 방식입니다.

3~3: 중복을 없애주기 위해서 set 함수를 사용합니다.

4~5: 이게 바로 제가 말하고자하는 정렬트릭입니다.

python의 정렬은 첫번째 것을 먼저 정렬하고, 그다음 우선순위를 두번째 원소로 둡니다.

따라서 정렬의 첫번째 조건을 첫번째 원소에 두번째 조건을 두번째 원소에 넣는 방식으로 넣어두고 정렬을 할 수 있습니다.

만약 길이가 긴 것순으로 정렬하라고 했다면 어떻게 하면 될까요?

N = int(input())
D = [input() for i in range(N)]
D = set(D)
D = [(-len(s), s) for s in D]
D.sort()

for l, s in D:
    print(s)

라고 하시면 됩니다.

이처럼 오름차순, 내림차순도 안에 넣는 원소를 바꾸기만 해서 구현해낼 수 있습니다.

기본정렬에서 추가적인 함수를 호출하지 않고도 처리할 수있어요.

자잘한 꿀팁

사실 이보다 간단하게 처리할 수 있어요.

list뿐 아니라 set도 list처럼 입력을 받으면서 초기화할 수 있습니다.

N = int(input())
D = {input() for i in range(N)}
D = sorted([(len(s), s) for s in D])

for l, s in D:
    print(s)

당연히 더 줄일수도 있죠.

하지만 이 이상부터는 숏코딩의 영역입니다.

착한 어른이들은 따라하지 마세요!

정렬 트릭의 활용

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

눈에 보이는 조건들만이 조건이 아닙니다. 들어온 순서나, 길이, 입력받은 상수값 같은 것들도 이에 활용할 수 있습니다. 위 문제에도 이를 활용할 수 있습니다.

문제 설명은 지면이 길어져서 생략하도록 할게요.

입력 예제 1

정답 코드

N = int(input())
D = [input().split(" ") for i in range(N)]
D = sorted([(int(age), order, name) for order, (age, name) in enumerate(D)])

for age, order, name in D:
    print(age, name)

이 코드에도 몇가지 보여드릴께 있습니다. 이 코드에서 배울 것은 크게 3가지입니다.

1. enumerate
2. for문의 unpack 트릭
3. order를 정렬의 조건으로 넣기

enumerate

enumerate는 반복문을 돌 때, 배열의 인덱스, 배열의 원소 두가지를 활용할 수 있게 해줍니다.

3개라구요? 아닙니다 잘 보세요! 2개입니다.

order, (age, name) 2개라구요.

for문에서 이름 붙여서 가져오기

이것이 바로 python에서 for문에서 container를 unpack할 시에 제공하는 문법입니다.

아마 컨테이너 안에 있는 tuple에서 몇가지 원소를 이름을 붙여서 가져올 때 사용해보셨을 텐데, 컨테이너 안에 컨테이너에서 이름을 붙여서 가져올 수 있다는 사실은 사람들이 잘 모르시는 경우가 많았습니다.

이 경우에는 괄호를 생략하실수 없습니다! 바로 container에서 가져옴과 동시에 이름을 붙일 수 있기 때문에 코드의 가독성이 더 올라가게 되죠.

순서를 정렬의 기준으로 만들기

enumerate에서 가져온 배열의 인덱스는 곧 input을 받은 순서입니다. 문제의 조건에서

1. 나이
2. 들어온 순서 (가입한 순서)

라고 했기 때문에 (int(age), order) 순으로 만든 것이죠.

엇 그런데 name이 추가로 들어가 있네요?

맞습니다. 실제로 출력을 할 때에는 이름 정보가 필요합니다.

정렬시에 사용하기위해서가 아니라 그 데이터 자체를 보존하기 위해서 넣어 준거에요.

연습 문제

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

마무리

사실 오늘로 끝내려고 했는데, 정렬처리 잡기술이 조금 주저리 주저리가 길어졌네요.

다음에 시간이되면 다른 잡기술들도 소개하도록 하겠습니다.

생각보다 제가 사용하는 잡기술들이 많네요...

graph 알고리즘에서 사용하는 것들도 많고, 슬라이싱을 이용한 잡기술들도 굉장히 많은데

흠... 언제 다쓰지 이거

맥주를 먹고 그만 월요일이 되어버렸어요.

자 (1)에서 배웠던 테크닉으로 여러 형태의 입력을 받아볼거에요.

이번 시간에는 배열을 인풋으로 받는 방법에 관해서 종류별로 가볍게 설명드리고 넘어가려고 해요.

C, C++, Java 사용자들은 배열을 인풋으로 받기전에 먼저 배열은 선언해두는 것이 익숙합니다.

하지만 python의 경우 배열 선언이 매우 귀찮을 뿐아니라, 고정된 크기로 메모리를 잡아두는 것이 상당히 어렵습니다.

따라서, 그냥 input을 받으면서 동시에 input을 받은 값으로 초기화하는 코드를 자주 사용하게 됩니다.

이것도 마찬가지로 손쉽게 map으로 해결할 수 있는데, 각 예제로 설명 드릴께요.

1차원 배열을 인풋으로 받기

1차원 배열을 선언할 수 있는 문제를 먼저 하나 가져와볼께요.

X보다 작은 수라고하는 문제입니다.

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

X보다 작은 수

입력 서술

첫째 줄에 N과 X가 주어진다. (1 ≤ N, X ≤ 10,000)
둘째 줄에 수열 A를 이루는 정수 N개가 주어진다. 주어지는 정수는 모두 1보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

입력 예제1

10 5
1 10 4 9 2 3 8 5 7 6

입력 받는 코드

N, X = map(int, input().split(" "))
ARR = list(map(int, input().split(" ")))

이 코드를 실행했을 때, 위의 예제1을 받으면 아래처럼 저장됩니다.

사족 - 왜 굳이 map함수 이후 list형으로 변환을?

왜 굳이 map함수를 사용한 후에 다시 list 형으로 변환을 해줬을까요?

사실 map 함수의 결과물인 map object는 iteration을 돌 수 있지만,

임의의 인덱스로 접근이 불가능합니다. map함수의 리턴형은 list가 아닙니다!

즉, [0] [1] [2] 와같은 인덱스로 접근하는 것이 불가능해요.

따라서 list 함수로 형을 변환해줘야만 접근이 가능하다는 것이죠!

아래 코드를 실행하면 에러가 발생할 거에요 한번 테스트 해보세요!

test_var = map(int, "1234")
print(test_var[1])

그렇기 때문에 map으로 생성한 것을 리스트와 같이 사용하려면 list로 캐스팅해줘야 합니다.

하지만 1번째 줄처럼 map에서 나온 오브젝트를 각 변수에 바로 나눠서 담는 경우는 굳이 map을 list로 캐스팅해주실 필요는 없습니다.

2차원 배열을 인풋으로 받기

입력 사이에 구분자가 있는 경우 - 종이의 개수

종이의 개수라는 문제로 예제를 들어볼까해요.

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

입력 서술

첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

입력 예제 1

9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1

입력 받는 코드

N = int(input())
PAPER = [list(map(int, input().split(" "))) for i in range(N)]

이 코드를 실행했을 때, 위의 입력 예제1을 받으면 아래처럼 저장됩니다.

저번 포스팅에서 한줄로 들어온 데이터를 입력 받는 법을 배웠었죠.

이를 활용하면 위와 같은 코드 한줄로 2차원 배열의 입력을 받을 수 있습니다.

구분자가 space bar이고, 이 구분자를 배열을 생성하면서 N번 동시에 받은 거죠.

다른 언어에 비해서 이런 부분은 확실히 편하게 입력을 받을 수 있는 것 같습니다.

입력 사이에 스페이스가 없는 경우 - 알고스팟

이러한 형태의 문제들이 많지는 않습니다. 하지만 분명이 존재하고 가끔 생각이 안돌아갈때 어떻게 입력을 받아야하지... 라는 고민을 하게되곤 해요.

알고스팟으로 그 예제를 들어볼까해요.

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

입력 서술

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.
(1, 1)과 (N, M)은 항상 뚫려있다.

입력 예제 1

3 3
011
111
110

자 이 문제의 입력은 기존에 배웠던 원리로 매우 간단하게 처리 할 수 있어요.

입력 받는 코드

N, M = map(int, input().split(" "))
MIRO = [list(map(int, input())) for i in range(N)]

이 코드를 실행했을 때, 위의 입력 예제 1을 받으면 아래처럼 저장됩니다!

이 코드를 보시면

MIRO = [list(map(int, input())) for i in range(N)]

이번에는 input()에 split이 없어요. str 자료형은 그 자체로 list처럼 생각하셔도 무방해요. 

사실상 "011" 이면 ["0", "1", "1"] 과 같다고 할 수 있죠.

스페이스바가 없는 입력을 분리하고 싶다면, split 없이 위와 같은 코드로 입력을 받아서 처리할 수 있어요.

배열 선언하기

거의 대부분의 언어들에서 배열을 선언하는 것에 많은 코드를 필요로 하지 않습니다.

하지만 이 나쁜 python은 배열 선언하기를 더럽게 복잡하게 만들어 뒀습니다.

numpy라도 쓸수 있게 해준다면 정말 행복할 텐데, 어림도 없습니다.

대부분의 코딩 테스트에서는 numpy를 지원하지 않습니다.

배열 선언 코드

INIT = -1
# ML러들이 좋아하는 변수명
W = row     # 행
H = column  # 렬
C = channel # 3차원!
B = batch   # 4차원! 

D1 = [INIT for j in range(W)]
D2 = [[INIT for i in range(W)] for j in range(H)]
D3 = [[[INIT for k in range(W)] for i in range(H)] for j in range(C)]
D4 = [[[[INIT for l in range(W)] for k in range(H)] for i in range(C)] for j in range(B)]

맞아요. 왕도가 없습니다... 여러분이 알고 있는 이 방법이 최적입니다.

이건 죄송할 따름이네요. 순수 파이썬으로는 이 방법말고 좋은 방법을 찾지 못했습니다.

손에 익으시면 호다닥 작성 할 수 있을 겁니다.

마무리

python은 멋진 언어입니다. 배열 빼고는요.

배열은 numpy가 없으면 정말 사용하기 귀찮기 그지없습니다.

python 4쯤에는 배열을 미리 할당할 수 있는 좋은 방법이 제안되었으면 하네요.

아

다음 글로 마무리를 지을 예정이에요.

다음 글에서는 python의 내장함수를 이용한 여러 잡기술들을 포스팅하고자 합니다.

라떼는 말이야... 다 C언어 부터 배웠어...

그런데 요즘은 다 python으로 문제풀고 말이야...

Python으로 문제를 풀어?

그렇습니다. 이제는 python으로도 문제를 풀수 있는 시대가 도래했습니다.

C나 C++로 문제를 풀던 많은 사람들이 python으로 문제푸는 것을 두려워합니다.

python의 입출력 방식이 C나 C++과 매우 사맛디 아니하기 때문이죠.

하지만 과연 그럴까요? 익숙해지면 C나 C++보다도 손쉽게 input을 받을 수 있습니다.

머신러닝을 전공하시던 분들은 취직시장에 나와보니 아뿔사 코딩테스트는 봐야하는데, 익숙한 언어가 python 뿐입니다.

알고리즘을 하시는 분들에게 문의를 해보니,

본디 알고리즘은 C++이 짱이다!

python이 세상에서 제일 편한 언어가 되어버렸는데, C++이라뇨...

코딩 테스트 때문에 새로운 언어를 익혀야 하는 불상사를 막고자 이번 글을 작성했습니다.

본 게시글은 맛보기인데, 제가 python으로 문제풀 때 주로 사용하는 테크닉들을 알려드리도록 하겠습니다.

제가 심심할 때 푸는 문제의 솔루션이나, 핫한 코딩테스트 문제들도 여기에 솔루션을 올리도록 할께요.

여러분들의 시간은 소중하니까.

인풋 받기

정수 하나 받기

코드

인풋을 받는 여러가지 방법들이 있습니다. 간단하게 정수 하나를 입력으로 받아 볼까요?

# "10"
N = int(input())
print(N)

이건 솔직히 새로울게 없습니다. input함수를 받고, 그 결과를 int로 캐스팅한 후, 변수 N에 넣어주는 것입니다.

input란?

input()은 입력을 받는 함수라고 알고 있습니다.

그리고 input()의 return형은 항상 str 형입니다.

그렇기 때문에, 들어온 입력을 적절히 가공해 주어야 합니다.

int()

지금으로서는 정수로 변환해주는 캐스팅 같은 역할을 한다고 생각하시면 좋을 것 같습니다.

계속 넘어가도록 하죠. 더 자세히 알 필요가 있다면 더 깊게 설명하도록 하겠습니다.

정수 두개 받기

코드

# 10 20
N, M = map(int, input().split(" "))
print(N+M) # 30

input이 한줄에 2개가 들어온다면 매우 귀찮아 집니다.

2개부터는 각각 인풋을 받아서 나누고 거기에 int로 형까지 변환해줘야합니다.

매우매우 귀찮은 일이 아닐 수 없죠.

위의 코드로 입력을 손쉽게 받을 수 있습니다.

이 코드는 아래 코드와 동일한 방식으로 작동하게 됩니다.

# 10 20
inp = input()
sp_inp = inp.split(" ")
N = int(sp_inp[0])
M = int(sp_inp[1])

int의 정체

N, M = map(int , input().split(" "))

아실지 모르겠지만 python에서 캐스팅하드시 사용하는 int, float와 같은 자료형처럼 보이는 모든 것들이 모두 함수의 형태로 사용합니다.

엄연히 말하자면 class의 형태를 가지고, int로 변환해주는 캐스팅 작업을 해줍니다.

python의 정확한 구조를 모르신다면 함수라고 생각하셔도 무방합니다! 단지 int라는 이름을 가진 함수다 라고 생각하셔도 괜찮습니다.

input 함수가 하는 일

N, M = map(int , input().split(" "))

위에서 설명했듯이 input은 입력을 받는 함수이며, 동시에 str 를 return 합니다.

그리고 더 정확히는 한 라인을 통째로 받는 함수입니다.

이 부분의 기존의 Problem Solving (PS) 계열에 있던 사람들이 고통 받는 이유중 하나입니다.

PS러들은 문자열을 스페이스 단위로 받아서 처리하고 싶어하기 때문이죠...

입력이 뭐가 들어왔던 간에 str로 한 라인을 통째로 받기 때문에 이를 필요에 따라 여러가지 형태로 가공해줘야하는 것이 매우 거슬릴 것입니다.

str의 내장 함수 split

N, M = map(int, input().split(" "))

str에는 다양한 내장 함수들이 있습니다. 이를 통해서 손쉽게 string을 가공할 수 있습니다.

ps러라면 #include <string.h> 나 #include 을 하고 고통받아 보신 분이 있을 겁니다.

python에서는 훨씬 더 쉬운 형태의 인터페이스를 제공 합니다!

pycharm같은 훌륭한 ide를 쓰신다면 "abc". 하고 컨트롤 탭을 하시면 다양한 함수들을 구경하실 수 있을 겁니다.

오늘 알아볼 함수는 split입니다.

이름부터 직관적이게 해당 문자열을 나눠주는 함수입니다.

아래 코드를 확인하시면 어떤 짓을 할 수 있는 녀석인지 직관적으로 깨달으실 수 있을 겁니다.

"10 20 30".split(" ") # ["10", "20", "30"]
"10,20,30".split(",") # ["10", "20", "30"]
"10,20,30,".split(",") # ["10", "20", "30", ""]
"10 20 30 ".split(" ") # ["10", "20", "30", ""]

다만 마지막 두 예제를 조심하세요!

마지막에도 delimiter (구분자?)가 있다면 비어 있는 string을 return할 거에요!

위와 같은 예제를 피하기 위해서는 아래와 같이 strip 함수를 사용해주면 됩니다.

"10 20 30 ".strip().split(" ") # ["10", "20", "30"]

map 함수

이제 마지막으로, map함수를 알아봅시다.

map 함수는 첫번째 인자로 함수를, 두번째 인자로 배열을 받습니다. 그래서 각 배열의 원소에 해당 함수를 적용해주는 함수입니다.

• (사족1) 사실 함수가 아니라 callable 한 모든 것들이 여기에 올 수 있습니다.
• (사족2) 사실 배열이 아니라 iterator를 받습니다. 대충 반복할수 있는거라고 생각하시면 될것 같습니다.

말로는 잘 이해가지 않을 것이라고 생각해요. 예제로 이해하는 편이 좋을 겁니다.

arr = ["10", "20", "30"]
map(int, arr) 
# == [int(arr[0]), int(arr[1]), int(arr[2])]
# == [10, 20, 30]

이제 https://www.acmicpc.net/problem/1000 를 풀어볼까요?

마치며

아니 벌써 마치다니요? 사실 맥주 먹으러 가야해서 시간이 없네요.

다 먹고 살자고 하는 건데 맥주한잔하고 오겠습니다.

2탄에서 계속 하도록 할게요!