Pythonic way
import this결과
The Zen of Python, by Tim Peters
Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!
input()함수 대신, sys.stdin.readline() 로만 바꿔도 시간 줄일 수 있다.
N = int(input())=>
import sys
N = int(sys.stdin.readline())target = 10
lst = [1, 4, 6, 8, 10, 13, 15, 16, 17, 20]
low = 0
high = len(lst)
lst.sort()
while low <= high:
mid = (low+high) // 2
if lst[mid] == target:
break
elif lst[mid] < target:
low = mid + 1
else:
high = mid - 1
print(mid)
print(lst[mid])target = 10
lst = [1, 4, 6, 8, 10, 13, 15, 16, 17, 20]
low = 0
high = len(lst)
lst.sort()
def binary_search(data, target, low, high):
mid = (low+high) // 2
if data[mid] == target:
pass
elif data[mid] < target:
binary_search(data, target, mid+1, high)
elif data[mid] > target:
binary_search(data, target, low, mid-1)
return mid
idx = binary_search(lst, target, low, high)
print(idx)
print(lst[idx])target = 9
lst = [1, 4, 6, 8, 10, 13, 15, 16, 17, 20]
low = 0
high = len(lst)
lst.sort()
while low<=high:
mid = (low+high) // 2
if lst[mid] == target:
break
elif lst[mid] < target:
low = mid + 1
else:
high = mid - 1
idx = 0
if lst[mid] < target:
idx = mid
else:
idx = mid - 1
print(idx)
print(lst[idx])def era(N):
ck = [False for _ in range(N+1)]
ret = []
for i in range(2, len(ck)):
if ck[i]:
continue
ret.append(i)
for j in range(i**2, len(ck), i):
ck[j] = True
return ret
print(era(10))def era(N):
ck = [False for _ in range(N+1)]
ret = [False for _ in range(N+1)]
for i in range(2, len(ck)):
if ck[i]:
continue
ret[i] = True
for j in range(i*2, len(ck), i):
ck[j] = True
return ret
print(era(10))from bisect import bisect_left as bl, bisect_right as br
nums = [-1,30,22,13,-4,5,-6,7,8,9]
# 2 ~ 10 사이의 element 구하기
nums.sort() # O(nlogn) => [-6, -4, -1, 5, 7, 8, 9, 13, 22, 30]
l = bl(nums, 2) # 2 왼쪽 인덱스
r = br(nums, 10) # 10 오른쪽 인덱스
for i in range(l, r):
print(nums[i], end=' ') # 5 7 8 9 participant은 n개의 string으로 이루어진 리스트, completion은 n-1개의 string으로 이루어진 리스트이다. participant - completion의 string을 구하시오.
해시를 활용하는 문제로, 파이썬의 딕셔너리를 적극 활용하였다.
- par_dic : 딕셔너리, key=participant의 string, value=string의 index
- ck : 리스트, participant의 길이만큼의 길이를 가지며, completion에 있는 string이면 True, 아니면, False
def solution(participant, completion):
ck = [False for _ in range(len(participant))]
par_dic = {}
participant.sort()
completion.sort()
for i in range(len(participant)): # par_dic을 만들 때, key에 여러 value가 들어갈 수 있도록 조치
if participant[i] in par_dic:
new.append(i)
else:
new = [i]
par_dic[participant[i]]=new
for i in range(len(completion)): # completion을 하나하나 보면서, ck를 완성하고, False인 element 반환
ck[par_dic.get(completion[i]).pop(0)] = True
idx = ck.index(False)
return participant[idx]import math
print(round(math.pi, 6)) # 3.141593 (6번 째까지 '반올림'을 통해 보여지게)print("{:1.3f}".format(a)) # {인덱스(생략가능):최소숫자길이(생략가능).소수점몇개까지f}
그러면 생각할 때, 어떤 회사가 최대, 최소에 민감할지를 생각해봐야겠다. (내비게이션 관련 회사라면 그래프가 중요한 것처럼)
Max Heap 기준으로 특징 2가지
- 부모 노드가 자식 노드보다 크다.
- 자식 노드의 left, right는 어느 쪽이 크더라도 상관없다.
완전 이진트리라서, 파이썬에서는 리스트로 구현한다. class를 만들고 안에 function을 구현해서 사용하자.
일단, 완전 이진 트리 구조로 넣고, heap 구조를 만족하도록 swap한다.
heap에서의 pop은 root노드를 pop하는 것이다. pop 후에, 맨 마지막에 채워진 노드를 root노드로 올리고, 자식 노드 중 큰 자식 노드와 비교해서 swap해간다.
- 부모 노드 index : 자식 노드 index // 2
- 왼쪽 자식 노드 index : 부모 노드 index * 2
- 오른쪽 자식 노드 index : 부모 노드 index * 2 + 1
기본적으로 파이썬에서의 heap은 min heap입니다. 넣고 빼는 함수는 heapq를 이용하되, 함수의 인자가 되는 대상은 항상 리스트입니다.
min heap
import heapq as hq
hq.heapify(리스트) # 리스트 -> 힙, return 없음, O(N)
hq.heappush(리스트, 원소) # 원소 추가, return 없음, O(logN)
hq.heappop(리스트) # 원소 삭제, return 원소, O(logN)max heap
우선순위 heap처럼 heap을 구성합니다.
a = [(2, 3), (1, 5), (3, 2)]
a.sort()
print(a)
# 결과 : [(1, 5), (2, 3), (3, 2)]위의 정렬을 생각해보면,
import heapq as hq
a = [3, 5, 2]
for i in range(len(a)):
a[i] = (a[i]*(-1), a[i])
hq.heapify(a)
print(a)
# 결과 : [(-5, 5), (-3, 3), (-2, 2)]일반 deque를 사용법을 먼저 이해합시다. deque는 double ended queue로, 양단에서 pop, push가 됩니다.
from collections import deque
a = [2, 4, 3]
de = deque(a) # 기존의 리스트로 deque를 생성
de.append(1) # 오른쪽에 값 추가
de.appendleft(5) # 왼쪽에 값 추가
b = [7, 8]
de.extend(b) # 오른쪽에 리스트 추가
de.extendleft(b) # 왼쪽에 리스트 추가
de.pop() # 오른쪽에 값 제거
de.popleft() # 왼쪽에 값 제거
de.rotate(3) # 오른쪽으로 3만큼 회전
de.rotate(-1) # 왼쪽으로 1만큼 회전그리고, 우선순위 queue를 봅시다.
from queue import PriorityQueue
queue = PriorityQueue() # 생성
queue.put((1, 'love')) # 원소 추가 '(우선순위, 값)꼴', O(logN)
queue.put((2, 'faith'))
queue.put((3, 'hope'))
queue.get() # 그 중에 제일은 사랑이라 (고린도전서 13:13)
queue.qsize() # queue의 사이즈를 반환
queue.empty() # 비었는지 T or F
from itertools import combinations
from itertools import permutations
a = [1, 4, 65, 7, 2]
print(list(combinations(a,3 )))BFS : 가중치가 1일 때의 최단거리 구하는 알고리즘
(가중치가 1이 아니면, Dijkstra로 해야댐.)
graph = dict()
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']
def DFS(graph, start_node):
need, visited = list(), list()
need.append(start_node)
while need:
now = need.pop()
if now not in visited:
visited.append(now)
need.extend(reversed(graph[now]))
return visited
from collections import deque
def BFS(graph, start_node):
need, visited = deque(), list()
need.append(start_node)
while need:
now = need.popleft()
if now not in visited:
visited.append(now)
need.extend(graph[now])
return visited
print(DFS(graph, "A"))
print(BFS(graph, "A"))import sys
sys.setrecursionlimit(1000000)대게 DFS는 재귀 or 스택 / BFS는 큐로 푼다고 합니다. 그런데, 특별한 경우가 아니면, DFS로 풀리는 것은 BFS로 풀리고, BFS로 풀리는 것은 DFS로 풀리니 일단, DFS를 재귀로 푸는 법을 연습합니다. (경우의 수 문제처럼 느껴지는 것은 이 접근법으로)
예제는 knapsack problem이고, 재귀 로 풀도록 하겠습니다.
먼저 fast_max 라고 하는 재귀 함수를 만들 건데요. 이 함수는 영역과 남은 가방 용량을 받아서, 해당 영역에서 가장 가치가 높은 아이템 조합과 가치 총합을 반환해주는 함수입니다.
- 파라미터 : (아이템들, 남은 수용양)
- 리턴 : (아이템 조합, 가치 총합)
def fast_max(sub_lst, avail) :
# 후보군이 될 수 있는 아이템이 없거나, 가방에 더 넣은 공간이 없다면, (아이템 조합은 없고, 가치 총합은 0)을 반환해야 합니다.
if sub_lst == [] or avail == 0 :
return (), 0
# 아이템들 중에 처음 아이템을 일단 하나 선택합니다.
nextitem = sub_lst[0]
# 방금 꺼낸 아이템(nextitem)을 넣었을 때, 가방이 넘치치 않는 경우
if nextitem[2] <= avail :
# 이제부터 전략은, 전체 sub_lst에서 방금 꺼낸 아이템(nextitem)을 포함했을 때의 조합을 chosen1이라 두고,
# 방금 꺼낸 아이템(nextitem)을 포함하지 않고의 조합을 chosen2라 두어,
# 가치를 비교하게 됩니다.
chosen1, val1 = fast_max(sub_lst[1:], avail-nextitem[2])
val1 += nextitem[1]
chosen1 = chosen1 + (nextitem,)
chosen2, val2 = fast_max(sub_lst[1:], avail)
if val1 > val2 :
result = chosen1, val1
else :
result = chosen2, val2
# 방금 꺼낸 아이템(nextitem)을 넣었을 때, 가방이 넘치는 경우
else :
# nextitem을 제외하고 나머지 영역에 대해 조합을 찾습니다.
result = fast_max(sub_lst[1:], avail)
return result
items = [('1', 3, 5), ('2', 5, 2), ('3', 10, 10), ('4', 3, 2), ('5', 4, 3), ('6', 1, 1), ('7', 3, 10)]
taken, val = fast_max(items, 20)
for item in taken :
print(item)
print("Total value of items taken =", val)-
fast_max의 반환 값은, 남은 수용량에 대해 인자로 넘겨준 영역에서 가장 높은 가치를 내는 아이템 조합입니다.
(fast_max를 재귀적으로 사용하기 위해서는 아이템을 선택해서 새로운 영역과 그로 인한 새로운 수용양을 준비해야합니다.)
-
가장 높은 가치를 내는 조합이 되기 위해, 아이템은 다음 두 후보 중에 하나를 선택합니다.
-
아이템 리스트 중 첫번째 아이템 + 첫번째를 제외한 영역에서의 fast_max함수 값 의 조합
-
인자로 받은 모든 영역에서의 fast_max함수 값 의 조합
cf) 첫 번째 아이템으로 가방이 넘치는 경우, 첫 번째 아이템을 제외한 영역에서 fast_max를 다시 적용합니다.
-
이를 Dynamic programming으로 문제를 심화할 수 있습니다. memo라고 하는 딕셔너리를 하나 만들고, 특정 남은 수용양에 대해 특정 아이템 갯수로 이전에 계산한 적이 있다면, 이전에 계산했던 값을 반환합니다.
def fast_max(sub_lst, avail, memo={}) :
if (len(sub_lst), avail) in memo :
return memo[(len(sub_lst), avail)]
if sub_lst == [] or avail == 0 :
return (), 0
nextitem = sub_lst[0]
if nextitem[2] <= avail :
chosen1, val1 = fast_max(sub_lst[1:], avail-nextitem[2], memo)
val1 += nextitem[1]
chosen1 = chosen1 + (nextitem,)
chosen2, val2 = fast_max(sub_lst[1:], avail, memo)
if val1 > val2 :
result = chosen1, val1
else :
result = chosen2, val2
else :
result = fast_max(sub_lst[1:], avail, memo)
memo[(len(sub_lst), avail)] = result
return result이렇게 복사하면, 서로 영향을 받지 않습니다. (단, nested 리스트인 경우에는 복사본 수정으로 원본이 변하게 됩니다.)
# 1. 슬라이싱 복사
a = [1, 2]
b = a[:]
# 2. 모듈로 복사
import copy
a = [1, 2]
b = copy.copy(a)# 1. 모듈로 복사
import copy
a = [1, 2]
b = copy.deepcopy(a)a = 0b100 # 출력하면, 4
b = 0x15A # 출력하면, 346print(0b0101 & 0b0011) # 출력하면, 1
print(bin(0b0101 & 0b0011)) # 출력하면, 0b1
print(5 & 3) # 출력하면, 1
print(bin(5 & 3)) # 출력하면, 0b1print(0b0101 | 0b0011) # 출력하면, 7
print(bin(0b0101 | 0b0011)) # 출력하면, 0b111
print(5 | 3) # 출력하면, 7
print(bin(5 | 3)) # 출력하면, 0b111print(0b0101 ^ 0b0011) # 출력하면, 6
print(bin(0b0101 ^ 0b0011)) # 출력하면, 0b110
print(5 ^ 3) # 출력하면, 6
print(bin(5 ^ 3)) # 출력하면, 0b110print(~0b0011) # 출력하면, -4
print(bin(~0b0011)) # 출력하면, -0b100
print(~3) # 출력하면, -4
print(bin(~3)) # 출력하면, -0b100print(0b0011 << 2) # 출력하면, 12
print(bin(0b0011 << 2)) # 출력하면, 0b1100
print(3 << 2) # 출력하면, 12
print(bin(3 << 2)) # 출력하면, 0b1100간혹 파이썬 코드를 보면 다음과 같이 사용하는 것을 볼 수 있다. 파라미터와 리턴 타입을 정해주는 것이다.
def fn(a: int) -> int: # 파라미터는 int 타입이며, 리턴되는 값도 int 타입이다.
print("Something")
return a^x # x로 시작하는 문자열
x$ # x로 끝나는 문자열
. # 임의의 문자
\d # 숫자
\D # \d가 아닌 것
\w # 문자(알파벳, 숫자, _)
\W # \w가 아닌 것
\s # 공백 문자
\S # \s가 아닌 것
[] # [] 중에 하나
[xy] # x or y 하나
[^xy] # x or y 제외한 하나
[0-5] # 0~5 중에 하나
{} # {}개
x{3} # x 3개
x{2,5} # x 2개 이상 5개 이하
x+ # x 한번 이상
x* # x 0번 이상
x? # x 있어도 되고, 없어도 되고
() # () 추출할 수 있음
(x|y) # x문자열 or y문자열 중에 하나
r"x" # x를 raw string으로 봄 ex) r"\n"은 \, n이 각각 문자열로 취급됨일단, 큰 틀!
모듈 가져오고,
import re그리고 찾을 문자열에 대한 정규표현식을 정의
p = re.complie(정규표현식)
x_lst = re.findall(p, "적용할 문자열")적용 문자열에서 특정 부분을 추출하고 싶을 때는, ()를 사용한다.
txt = "number: 15, number: 22"
p = re.compile("number:\s(\d+)")
x = re.findall(p, txt)
print(x) # 결과 : ['15', '22']-
특정 단어(h)로 시작하는 단어 추출
import re txt = "Hanst of handong is holy." p = re.compile("\b*([Hh]\w+)") x = re.findall(p, txt) print(x)
['Hanst', 'handong', 'holy']
-
로그 데이터에서 날짜 추출해서 Dataframe으로 만들기
import re import pandas as pd date_lst = list() file = './input.txt' with open(file, 'r') as fp: while True: f = fp.readline() if f == '':break p = re.compile(".*\"\$date\":\"(\d{4})-(\d{2})-(\d{2}).*") date_lst.append(list(re.findall(p, f)[0])) df = pd.DataFrame(date_lst,columns=['Year', 'Month', 'Day']) print(df)
Year Month Day 0 2020 05 12 1 2020 05 21 2 2020 06 01 3 2020 06 02 4 2020 06 02 5 2020 06 02 6 2020 06 05 7 2020 06 09 8 2020 06 10 9 2020 06 12
cf) input.txt
1 {"t":{"$date":"2020-05-12T17:20:34.747+09:00"},"s":"I", "c":"CONTROL", "id":23285, "ctx":"main","msg":"Automatically disabling TLS 1.0, to force-enable TLS 1.0 specify --sslDisabledProtocols 'none'"} 2 {"t":{"$date":"2020-05-21T17:20:34.750+09:00"},"s":"W", "c":"ASIO", "id":22601, "ctx":"main","msg":"No TransportLayer configured during NetworkInterface startup"} 3 {"t":{"$date":"2020-06-01T17:20:34.750+09:00"},"s":"I", "c":"NETWORK", "id":4648602, "ctx":"main","msg":"Implicit TCP FastOpen in use."} 4 {"t":{"$date":"2020-06-02T17:20:34.750+09:00"},"s":"I", "c":"STORAGE", "id":4615611, "ctx":"initandlisten","msg":"MongoDB starting","attr":{"pid":10338,"port":27017,"dbPath":"/usr/local/var/mongodb","architecture":"64-bit", "host":"osangjin-ui-MacBook-Pro.local"}} 5 {"t":{"$date":"2020-06-02T17:20:34.750+09:00"},"s":"I", "c":"CONTROL", "id":23403, "ctx":"initandlisten","msg":"Build Info","attr":{"buildInfo":{"version":"4.4.0","gitVersion":"563487e100c4215e2dce98d0af2a6a5a2d67c5cf", "modules":[],"allocator":"system","environment":{"distarch":"x86_64","target_arch":"x86_64"}}}} 6 {"t":{"$date":"2020-06-02T17:20:34.750+09:00"},"s":"I", "c":"CONTROL", "id":51765, "ctx":"initandlisten","msg":"Operating System","attr":{"os":{"name":"Mac OS X","version":"19.6.0"}}} 7 {"t":{"$date":"2020-06-05T17:20:34.750+09:00"},"s":"I", "c":"CONTROL", "id":21951, "ctx":"initandlisten","msg":"Options set by command line","attr":{"options":{"config":"/usr/local/etc/mongod.conf","net":{"bindIp":"127.0.0.1"}, "storage":{"dbPath":"/usr/local/var/mongodb"},"systemLog":{"destination":"file","logAppend":true,"path":"/usr/local/var/log/mongodb/mongo.log"}}}} 8 {"t":{"$date":"2020-06-09T17:20:34.751+09:00"},"s":"I", "c":"STORAGE", "id":22315, "ctx":"initandlisten","msg":"Opening WiredTiger","attr":{"config":"create,cache_size=3584M,session_max=33000,eviction=(threads_min=4, threads_max=4),config_base=false,statistics=(fast),log=(enabled=true,archive=true,path=journal,compressor=snappy),file_manager=(close_idle_time=100000,close_scan_interval=10,close_handle_minimum=250),statistics_log=(wait=0), verbose=[recovery_progress,checkpoint_progress,compact_progress],"}} 9 {"t":{"$date":"2020-06-10T17:20:35.346+09:00"},"s":"I", "c":"STORAGE", "id":22430, "ctx":"initandlisten","msg":"WiredTiger message","attr":{"message":"[1597998035:346926][10338:0x10f05bdc0], txn-recover: [WT_VERB_RECOVERY | WT_VERB_RECOVERY_PROGRESS] Set global recovery timestamp: (0, 0)"}} 10 {"t":{"$date":"2020-06-12T17:20:35.404+09:00"},"s":"I", "c":"STORAGE", "id":4795906, "ctx":"initandlisten","msg":"WiredTiger opened","attr":{"durationMillis":653}} -
String => String (특정 패턴 기반해서 바꾸기)
re.sub를 이용한다.
import re a = "((3))(2)" # 이걸 (3)2 로 바꿀 예정. p = re.compile('\(\d\)') print(re.findall(p, a)) print(re.sub(p, lambda x: str(x.group())[1], a)) # x.group()에 (3)이 있고, 2번째 원소인 3만.
프로그래머스 JOIN1.sql
SELECT ANIMAL_ID, NAME FROM ANIMAL_OUTS
WHERE ANIMAL_ID NOT IN
(SELECT DISTINCT ANIMAL_ID
FROM ANIMAL_INS);SET 함수로 할당할 때는 = 와 := 가 같다.
SELECT 함수에서는, =는 비교이고, :=는 할당이다.
할당의 의미로 사용할 때는, 되도록 :=를 사용하자.
class Node:
def __init__(self, x, y, prev_lst):
self.x=x
self.y=y
self.prev_lst=prev_lst
def get_xy(self):
return self.x, self.y
def add_lst(self, ele):
self.prev_lst.append(ele)
board=['...','#.#','...']
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
from collections import deque
route = deque()
N, M = 3, 3
srcX, srcY, destX, destY = 0, 0, 2, 0
visited = list()
route.append(Node(srcX, srcY, [(srcX, srcY)]))
breakFlag=False
while route:
node = route.popleft()
i, j = node.get_xy()
prev_lst = node.prev_lst
print("{}, {}노드를 할꺼구, 지나온 길은 {}야.".format(i, j, node.prev_lst))
for p in range(4):
x = i+dx[p]
y = j+dy[p]
if x >= M or x < 0 or y >= N or y < 0 or ((x, y) in node.prev_lst): continue
if board[x][y]=='.':
if (x, y) == (destX, destY):
node.add_lst((x, y))
breakFlag = True; break
print(" 지금 {}, {}에서 {}리스트가 추가될거야.".format(x, y, prev_lst+[(x,y)]))
route.append(Node(x, y, prev_lst+[(x,y)]))
if breakFlag: break
print(node.prev_lst)백준 1806
N, S = map(int, input().split())
num_lst = list(map(int, input().split()))
def solution(N, S, num_lst):
MIN = float('inf')
s, e, total = 0, 0, num_lst[0]
cnt = 1
while s <= e:
if total >= S:
cnt = e - s + 1
if MIN > cnt: MIN = cnt
total -= num_lst[s]
s += 1
else:
e += 1
if e >= N: break
total += num_lst[e]
if MIN == float('inf'): MIN = 0
return MIN
print(solution(N, S, num_lst))print('abc'[::-1])# NPM 이라고 했을 때
N = 4
M = 3
# 순열 구현하기 (재귀)
c = [False]*(N+1)
A = [0]*(N+1)
# m개의 수를 결정하되
# 1~n 까지의 수 중에서
# idx번째 수를 결정하고 있고,
# 다음 idx+1번째 수를 결정해달라고 하면서 끝나는 함수
# 참고로 이렇게 구현하면, 순열 한개를 다 만들고, 그 다음 순열을 만드는 식이다.
def go(idx, n, m):
# 인덱스가 m-1 일 때까지만 결정하면 되는데,
# 결정하려는 수의 인덱스가 m이라면, 함수 종료
if idx==m:
for i in range(m): # A에 1~n까지의 수 중에, m개를 고른게 들어있음.
print(A[i], end=' ')
print(); return
# 수를 결정할 때, 항상 1~n까지 모두 돌린다.
for i in range(1, n+1):
if c[i]: continue # 이미 선택한 적이 있다면 넘어간다.
c[i] = True # i를 선택한다고 말한다.
A[idx] = i # 수열에 추가한다.
go(idx+1, n, m) # idx+1번째 자리의 수를 결정해달라고 한다.
c[i] = False # 순열 완성본 1개당 1개의 c[]가 쓰이기 때문에, 이렇게 하는게 맞음.
go(0, N, M) # 4P3 라고 하면, 인덱스 '0'~2을 채우는 것이고, 'N'=4, 'M'=3- 1024B = 1KB
- 1024KB = 1MB
- 1024KB = 1GB
그냥 무난하게 길이가 100만인 int형 배열 하나는 4MB정도라고 보면됨.