손가락놀이터

Why Pythonic code?

남 코드에 대한 이해도 : 많은 개발자들이 python 스타일로 코딩한다.

효율 : 단순 for loop append 보다 list가 조금 더 빠르다. 익숙해지면 코드가 짧아진다.

Split

type의 값을 "기준값"으로 나눠서 List 형태로 변환

a = "   EXTRA   SPACE   "

b = a.split().lower()
c = a.split(' ')

print(b)    # ['EXTRA', 'SPACE']
print(c)    # ['', '', '', 'EXTRA', '', '', 'SPACE', '', '', '']

list comprehension

• 기존 List 사용하여 간단히 다른 List를 만드는 기법
• 다른 List를 포함해서 새로운 List를 만드는 것.
• 파이썬에서 가장 많이 사용되는 기법 중 하나
• 일반적으로 for + append 보다 속도가 빠름

result = []
for i in range(10):
	result.append(i)
	# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

result = [i for i in range(10)]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
result = [i for i in range(10) if i % 2 == 0]
# [0, 2, 4, 6, 8]
result = [i if i % 2 == 0 else -1 for i in range(10)]
# [0, -1, 2, -1, 4, -1, 6, -1, 8, -1]

word_1 = "Hello"
word_2 = "World"
result = [i + j for i in word_1 for j in word_2]
# ['HW', 'Ho', 'Hr', 'Hl', 'Hd', 'eW', 'eo', 'er', 'el', 'ed', 'lW', 'lo', 'lr', 'll', 'ld', 'lW', 'lo', 'lr', 'll', 'ld', 'oW', 'oo', 'or', 'ol', 'od']

case_1 = ["a","b","c"]
case_2 = ["d","e","a"]
result = [i+j for i in case_1 for j in case_2] # case_1부터
# ['ad', 'ae', 'aa', 'bd', 'be', 'ba', 'cd', 'ce', 'ca']
result = [[i+j for i in case_1] for j in case_2] # case_2부터
# [['ad', 'bd', 'cd'], ['ae', 'be', 'ce'], ['aa', 'ba', 'ca']]

result = []
for i in range(10):
	result.append(i)
	# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

result = [i for i in range(10)]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
result = [i for i in range(10) if i % 2 == 0]
# [0, 2, 4, 6, 8]
result = [i if i % 2 == 0 else -1 for i in range(10)]
# [0, -1, 2, -1, 4, -1, 6, -1, 8, -1]

word_1 = "Hello"
word_2 = "World"
result = [i + j for i in word_1 for j in word_2]
# ['HW', 'Ho', 'Hr', 'Hl', 'Hd', 'eW', 'eo', 'er', 'el', 'ed', 'lW', 'lo', 'lr', 'll', 'ld', 'lW', 'lo', 'lr', 'll', 'ld', 'oW', 'oo', 'or', 'ol', 'od']

case_1 = ["a","b","c"]
case_2 = ["d","e","a"]
result = [i+j for i in case_1 for j in case_2] # case_1부터
# ['ad', 'ae', 'aa', 'bd', 'be', 'ba', 'cd', 'ce', 'ca']
result = [[i+j for i in case_1] for j in case_2] # case_2부터
# [['ad', 'bd', 'cd'], ['ae', 'be', 'ce'], ['aa', 'ba', 'ca']]

여담으로 pprint.pprint를 쓰면 이쁘게 나온다!

enumerate & zip

enumerate : list의 element를 추출할 때 번호를 붙여서 추출

• 나오는 형태는 Tuple

for i, v in enumerate('abc'):
	print("{0}  {1}".format(i,v))
	# 0  a
	# 1  b
	# 2  c

for i, v in enumerate(['a','b','c']):
	print("{0}  {1}".format(i,v))
	# 0  a
	# 1  b
	# 2  c

zip : 두 개의 list의 값을 병렬적으로 추출함

alist = ['a1','a2','a3']
blist = ['b1','b2','b3']

[[a,b] for a, b in zip(alist, blist)]
# [['a1', 'b1'], ['a2', 'b2'], ['a3', 'b3']]
[c for c in zip(alist, blist)]
# [c for c in zip(alist, blist)]

list(enumerate(zip(alist, blist)))
# [(0, ('a1', 'b1')), (1, ('a2', 'b2')), (2, ('a3', 'b3'))]

lambda & map & reduce

lambda

함수 이름 없이, 함수처럼 쓸 수 있는 익명함수

수학의 람다 대수에서 유래함

def f(x, y):
	return x + y

f = lambda x, y : x + y

PEP 8에서는 lambda의 사용을 권장하지 않음

• 어려운 문법
• 테스트의 어려움
• 문서화 docstring 지원 미비
• 코드 해석의 어려움
• 이름이 존재하지 않는 함수의 출현
• 그래도 쓰는..

Map

두 개 이상의 list에도 적용 가능함, if filter도 사용가능

굳이 map을 사용하기 보다는 list comprehension을 사용하도록

ex = [1,2,3,4,5]
f = lambda x: x ** 2

list(map(f, ex))
# [1, 4, 9, 16, 25]
[f(value) for value in ex]

reduce

map function과 달리 list에 똑같은 함수를 적용해서 통합

대용량 데이터를 핸들링할 때, 주로 사용.

from functools import reduce

ex = [1,2,3,4,5]
f = lambda x, y: x + y

print(reduce(f,ex))
# 15

generator

Iterable data

• Sequence형 자료형에서 데이터를 순서대로 추출하는 object
• 내용이 아닌 위치정보(주소값)에 대한 정보가 저장됨.
• next를 하면 다음 메모리 주소에 있는 값을 불러옴.
• cities_주소 → seoul_주소 → busan_주소 → jeju_주소 → 없으므로 에러

cities = ["seoul", "busan", "jeju"]

memory_address = iter(cities)
# <list_iterator at 0x1ec8cbc6788>
next(memory_address) # seoul
next(memory_address) # busan
next(memory_address) # jeju

generator

• iterable object를 특수한 형태로 사용해주는 함수
• element가 사용되는 시점에 값을 메모리에 반환
• yield를 사용해 한번에 하나의 element만 반환함.
• 용량을 줄일 수 있기 때문에 대용량인 경우 사용하는 것이 효율적임.

import sys

def general_list(value):
	result = []
	for i in range(value):
		result.append(i)
	return result

result = general_list(50)
sys.getsizeof(result)
# 528

import sys

def generator_list(value):
	result = []
	for i in range(value):
		yield i

result = generator_list(50)
sys.getsizeof(result)
# 120
sys.getsizeof(list(generator_list(50)
# 472

When generator

• list 타입의 데이터를 반환해주는 함수는 generator로!

→ 특히 사용하면 읽기 쉽고, 중간 과정에서 loop가 중단될 수 있을때

• 큰 데이터를 처리할 때는 generator expression을 고려

→ 데이터가 커도 처리의 어려움이 없음.

• 파일 데이터를 처리할 때도 generator를 사용하자

asterisk

함수에 입력되는 parameter의 변수명을 사용하여 argument를 넘김.

# Keyword arguments
def print_name_keyword(name, you_name):
	print("Hello {}, my name is {}".format(you_name, name))

print_name_keyword(name="aaa",you_name="bbb")

# default arguments
def print_name_default(name, you_name="NAVER"):
	print("Hello {}, my name is {}".format(you_name, name))

print_name_default("hwan")
# Hello NAVER, my name is hwan
print_name_default("hwan", "AA")
# Hello AA, my name is hwan

가변인자(variable-length)

• 개수가 정해지지 않은 변수를 함수의 parameter로 사용하는 법
• Keyword arguments와 함계, argument 추가가 가능
• Asterisk(*) 기호를 사용하여 함수의 parameter를 표시함
• 입력된 값은 tuple type으로 사용할 수 있음
• 가변인자는 오직 한 개만 맨 마지막 parameter 위치에 사용가능

def asterisk_test(a, b, *args):
	print(a)
	print(b)
	print(args)
	print(type(args))

asterisk_test(1,2,3,4,5)
# 1
# 2
# (3, 4, 5)
# <class 'tuple'>

키워드 가변인자(Keyword variable-length)

• Parameter 이름을 따로 지정하지 않고 입력하는 방법
• asterisk(*) 두개를 사용하여 함수의 parameter를 표시함
• 입력된 값은 dict type으로 사용할 수 있음
• 가변인자는 오직 한 개만 기존 가변인자 다음에 사용

def kwargs_test(**kwargs):
	print(kwargs)
	print(type(kwargs))

kwargs_test(first=3, second=4, third=5)
# {'first': 3, 'second': 4, 'third': 5}
# <class 'dict'>

결론으로는 argument는 그냥 파라미터, 키워드 파라미터, 가변인자, 키워드 가변인자 순으로 작성해야함.

def test_3(one, two=3, *args, **kwargs):
	print(one,two, args, kwargs)

test_3(1,2,3,4,5,6,6,a=100,b=200)
# 1 2 (3, 4, 5, 6, 6) {'a': 100, 'b': 200}

asterisk(*)

• 흔히 알고 있는 *를 의미함.
• tuple, dict 등 자료형에 들어가 있는 값을 unpacking
• 함수의 입력값, zip 등에 유용하게 사용가능

def asterisk_test(a, *args):
	print(a, args)
	print(type(args))

def asterisk_test2(a, args):
	print(a, *args)
	print(type(args))

asterisk_test(1,*(2,3,4,5,6)) # (1,2,3,4,5,6)과 같음
# 1 (2, 3, 4, 5, 6)
# <class 'tuple'>
asterisk_test(1,(2,3,4,5,6))
# 1 2 3 4 5 6
# <class 'tuple'>

data = ([1,2,],[3,4,],[5,6,])
print(*data)
# [1, 2] [3, 4] [5, 6]
for i in zip(*data):
    print(i)
# (1, 3, 5)
# (2, 4, 6)

def asterisk_test(a,b,c,d):
    print(a,b,c,d)
    
data = {"b":1,"c":2,"d":3}
asterisk_test(10, **data)
# 10 1 2 3

문제 리뷰

1. DFS와 BFS를 매트릭스를 통해 구현되는 방식이다.
2. DFS와 BFS의 정석으로 기초인 문제같다.

문제 링크

import sys
from collections import deque

n, m, v = map(int, sys.stdin.readline().split())
matrix = [[0] * (n+1) for _ in range(n+1)]

for _ in range(m):
    # 입력값 매트릭스로 구현
    line = list(map(int,sys.stdin.readline().split()))
    matrix[line[0]][line[1]] = 1
    matrix[line[1]][line[0]] = 1

# DFS 구현
def dfs(start, visited):
    # stack 활용
    visited += [start]
    for c in range(len(matrix[start])):
        # start에서 c로 갈 수 있으면서 아직 방문하지 않은 경우에 방문.
        if matrix[start][c] == 1 and c not in visited:
            dfs(c,visited)
    return visited

# BFS 구현
def bfs(start):
    # Queue로 구현
    visited = [start]
    queue = deque([start])

    while queue:
        # popleft로 0에 값 뽑기
        n = queue.popleft()
        for c in range(len(matrix[start])):
            # n에서 c로 갈 수 있으면서 아직 방문하지 않은 경우에 방문.
            if matrix[n][c] == 1 and c not in visited:

                visited.append(c)   # 방문처리
                queue.append(c)     # Queue에 추가
    return visited

Python의 시작

• 1991년 귀도 반 로섬이 발표한 언어
• 플랫폼 독립적
• 인터프리터 언어
• 객체 지향 언어
• 동적 타이핑 언어
• 처음 C언어로 구현됨

이름의 유래

귀도 반 로섬이 Monpy Python's Flying circus라는 코미디프로를 좋아하여 해당 프로그램에서 이름을 따서 Python이라고 지었다고 합니다.

혹은 그리스 신화 속에서 델포이 신탁소를 지키던 뱀인 피톤에서 유래했다고도 합니다. 정확한 것은 아니지만 이러한 이유 때문에 아나콘다라는 이름이 나왔다고 생각(?)할 수 있습니다ㅎㅎ

Python의 특징

플랫폼 독립적인 인터프리터 언어

• 플랫폼(OS) : 윈도우, 리눅스, 안드로이드, Mac os, ios 등 프로그램이 실행하는 운영체제를 플랫폼이라고 합니다.
• 독립적인(관계없는, 상관없는) : OS에 상관없이 한번 프로그램을 작성하면 사용가능.
• 인터프리터(통역기를 사용하는 언어) : 소스코드를 바로 실행할 수 있게 지원하는 프로그램 실행 방법.

결론적으로 파이썬은 파이썬 문법에 따라서 적으면 되지만 운영체제에서 작동을 하기 위해선 각각의 운영체제에 맞는 인터프리터 프로그램을 설치해서 번역해주는, 해석해주는 것이라고 생각하면 됩니다.

컴파일러와 인터프리터 언어의 차이점

객체 지향 언어

실행 순서가 아니라 단위 모듈(객체) 중심으로 프로그램을 작성합니다.

하나의 객체는 어떤 목적을 달성하기 위한 행동(method)와 속성(attribute)을 가지고 있습니다.

객체 지향 특징

1. 캡슐화(Encapsulation)
   • 데이터(속성)와 데이터를 처리하는 함수를 하나로 묶는 것.
   • 캡슐화된 객체의 세부 내용이 외부에 은폐(정보 은닉)되어, 변경이 발생할 때 오류의 파급효과가 낮아짐.
   • 재사용 용이
2. 정보은닉(Information Hiding)
   • 캡슐화에서 가장 중요
   • 다른 객체에게 자신의 정보를 숨기고 자신의 연산만을 통하여 접근 허용.
3. 추상화(Abstractions)
   • 불필요한 부분을 생략하고 객체의 속성 중 가장 중요한 것에만 중점을 두어 개략화한 것.
   • 모델화 하는 것.
4. 상속성(Inheritance)
   • 이미 정의된 상위 클래스(부모 클래스)의 모든 속성과 연산을 하위 클래스가 물려 받는 것.
   • 상속성을 이용하면 하위 클래스는 상위 클래스의 모든 속성과 연산을 자신의 클래스 내에서 다시 정의하지 않고서도 즉시 자신의 속성으로 사용가능.
5. 다형성(Polymorphism)
   • 메시지에 의해 개체(클래스)가 연산을 수행하게 될 때 하나의 메시지에 대해 각 객체(클래스)가 가지고 있는 고유한 방법(특성)으로 응답할 수 있는 능력을 의미.
   • 객체(클래스)들은 동일한 메소드명을 사용하며 같은 의미의 응답을 함.

동적 타이핑 언어

프로그램이 실행하는 시점에 프로그램이 사용해야할 데이터에 대한 타입을 결정합니다.

간단하게 프로그램이 실행하는 시점이란 것이 동적이라는 것으로 생각하면 됩니다.

Why Python?!

• 쉽고 간단하며 다양합니다.
• 이해하기 쉬운 문법 -> 사람의 시간이 줄어든다.(사람의 시간이 기계의 시간보다 중요함)
• 다양한 라이브러리 : 파이썬 대부분의 라이브러리가 다른 사용자에 의해서 구현되어 있습니다.

처음 들었지만 너무나 맘에 들었던 말로 마무리하겠습니다.😀

Life is short. You need Python!

문제후기

1. 문제를 보고 이해하는데 오래걸렸습니다. 문제는 R, G, B 값이 하나씩 주어지는데 이때 앞뒤의 집과 달라야한다는 것과 R, G, B를 그리는데 사용되는 페인트의 양이 최소가 되도록 하는 것입니다. 문제를 보고 DP를 보고 풀면 되겠다고 생각했고 이전에 프로그래머스에서 푼 땅따먹기와 같다고 판단했습니다.
2. R, G, B값과 이전까지 더해진 값의 합을 다시 저장합니다. 이때 이전 위치와 같은 경우는 제외합니다.
3. 마지막 줄에서 가장 최소의 값을 찾습니다.

예시 풀이

문제 예시를 DP를 이용하면 최종적으로 아래의 값이 나온다.

프로그래머스에서 비슷한 문제

문제링크

from sys import stdin

# N 개의 줄
N = int(stdin.readline())

# 배열 RGB값 n개
arr = [list(map(int, stdin.readline().split())) for _ in range(N)]

# 초기 설정값
answer = 1e9

# 1번쨰 줄부터 시작
for n in range(1,N):
    for i in range(3):
        # 미니멈 초기값
        minimum = 1e9
        for j in range(3):
            # 이전과 같은 색인 경우 제외
            # 가장 작은 값 찾기
            if i != j and arr[n][i] + arr[n-1][j] < minimum:
                minimum = arr[n][i] + arr[n-1][j]
        # 가장 작은 값 기록
        arr[n][i] = minimum

print(min(arr[-1]))

문제후기

1. 우선순위 큐를 활용한 문제로 Python은 우선순위 큐를 heap을 활용해서 해결합니다.
2. 절대값이 기준이고 그 다음 기준이 숫자이므로 (절대값, 숫자) 형식으로 heap에 push합니다.
3. 0이 나올 경우 heap에서 pop을 해서 출력합니다.

문제링크

from sys import stdin
import heapq

N = int(stdin.readline())
# 우선순위 큐
heap = []

for n in range(N):
    num = int(stdin.readline())
    if num != 0:
        # 0이 아닌 경우 우선순위 큐에 (절대값, 숫자) 삽입
        heapq.heappush(heap,(abs(num), num))
    # 0인경우
    else:
        # 큐가 비어있으면 0 출력
        if len(heap) == 0:
            print(0)
        else:
            # 큐에 값이 있으면 pop
            print(heapq.heappop(heap)[1])

문제후기

1. 해당 문제는 1부터 시작해서 g와 h를 거친 이후 최종 목적지로 가는 것을 확인하는 문제로 다익스트라를 활용해야겠다고 생각을 했습니다. 시간초과를 피하기 위해서 우선순위 큐도 적용했습니다.
2. 최종 목적지 후보로 도착하기 전에 g와 h 사이의 직선을 거쳐야하므로 1 -> g -> h -> 최종 or 1 -> h -> g -> 최종입니다.
3. 처음 문제를 풀고 제출을 했을때 틀렸는데 문제에서 2번에서 가는 것이 1-> 최종보다 작야한다는 것을 파악하지 못했습니다.

문제링크

from sys import stdin
import heapq

# 방문여부 확인용 초기값
INF = 1e9

# 다익스트라 알고리즘
def dijkstra(start, last):
    # 방문여부
    dp = [INF] * (n+1)
    # 시작 값 0부터 시작
    dp[start] = 0
    heap = []
    # 힙에 (거리값, 정점) push, 우선순위 큐
    heapq.heappush(heap, (dp[start], start))

    # 힙이 있을때까지
    while heap:
        
        weight, now = heapq.heappop(heap)
        for end, dis in node_dict[now]:
            # 조건을 만족하는 값 heap정렬
            if dp[end] > weight + dis:
                dp[end] = weight + dis
                heapq.heappush(heap, (dp[end], end))
    return dp[last]


T = int(stdin.readline())
for _ in range(T):
    n, m, t = map(int, stdin.readline().split())
    s, g, h = map(int, stdin.readline().split())


    # 노드 hash화
    node_dict = {}

    for _ in range(m):
        a, b, d = map(int, stdin.readline().split())
        node_dict[a] = node_dict.get(a,[]) + [(b,d)]
        node_dict[b] = node_dict.get(b, []) + [(a, d)]
    
    # 1번 시작 -> g -> h -> 최종
    # 2번 시작 -> h -> g -> 최종
    answer1, answer2 = 0, 0

    answer1 = dijkstra(s, g) + dijkstra(g, h)
    answer2 = dijkstra(s, h) + dijkstra(h, g)

    candidate = []
    minimum = INF
    for _ in range(t):
        node = int(stdin.readline())
        answer = min(answer1 + dijkstra(h, node), answer2 + dijkstra(g, node))
        chk_answer = dijkstra(s, node)

        if chk_answer >= answer:
            heapq.heappush(candidate, node)


    while candidate:
        print(heapq.heappop(candidate), end="")
        if candidate:
            print(" ", end="")
        else:
            print("")

문제후기

1. 문제를 보고 DP를 활용하는 문제라고 판단했습니다.
2. 계산을 편하게 하기 위해서 좌표와 메트릭스의 크기를 동일하게 하고 계산했습니다.
3. 물 웅덩이가 없는 경우 해당 위치까지 똑같은 크기만큼 이동했기 때문에 비교할 필요 없이 더하면 됩니다.
4. 물 웅덩이가 있는 경우 값을 0으로 만들어 제외했습니다.

문제링크

def solution(m, n, puddles):

    # 매트릭스 제작.
    matrix = [[0] * (m + 1) for _ in range(n + 1)]

    # 출발, 집 좌표
    matrix[1][1] = 1

    # DP 시작
    for y in range(1, n + 1):
        for x in range(1, m + 1):
            # 출발 값
            if y == 1 and x == 1:
                continue
            # 웅덩이가 있는 경우 패쓰
            if [x, y] in puddles:
                matrix[y][x] = 0
            else:
                # 해당 위치 값은 이전값 2개의 합.
                matrix[y][x] = matrix[y - 1][x] + matrix[y][x - 1]

    return matrix[n][m] % 1000000007

문제후기

1. 문제에서 n이 1이상 100이하인 것과 경기 결과가 1개 이상 4,500개 이하인 것을 보고 완전탐색이 가능하다고 판단했습니다.
2. 입출력 예시에서처럼 5번 선수는 다른 선수와 경기를 하지 않아도 2번 선수를 통해서 결과를 유추할 수 있다는 것을 확인할 수 있습니다.
3. A선수가 B선수를 이기고 B 선수가 C선수를 이긴다면 A가 C를 이긴다는 조건이 성립합니다.( A>B이고 B > C이면 A>C)
4. 유추를 통해 이길 수 있는 선수와 지는 선수를 set 집합을 통해 저장 후 결과를 추출했습니다.

문제링크

def solution(n, results):
    # 선수 경기 결과 hash로 저장
    matrix = dict()

    # 이기는 사람 집합과 지는 사람 집합
    for i in range(1, n + 1):
        matrix[i] = [set(), set()]

    # 경기 결과 입력
    for i in results:
        matrix[i[0]][0].add(i[1])
        matrix[i[1]][1].add(i[0])

    # 만약 A > B 이고 B > C 인경우 A>C인 관계(>는 이긴다)
    # 모든 선수를 통해 경기하지 않아도 결과를 아는 경우 저장.
    for num, match in matrix.items():
        if match[0] and match[1]:
            for win in match[0]:
                matrix[win][1].update(match[1])
            for lose in match[1]:
                matrix[lose][0].update(match[0])

    # 만약 이기는 경우, 지는 경우, 자기 자신의 합이 모든 선수의 수인 경우 +1
    answer = 0
    for num, match in matrix.items():
        if len(match[0]) + len(match[1]) + 1 == n:
            answer += 1
    return answer