Parameters(매개변수)
are defined by the names that appear in a function definition (함수 내)Arguments(인자)
are the values actually passed to a function when calling it (함수 사용시)list 와 같은 가변객체를 복사: 사본생성이 아닌 같은 객체를 참조.
>>> x = []
>>> y = x
>>> y.append(10)
>>> y
[10]
>>> x
[10]
int 와 같은 불변객체를 복사: 새로운 객체가 생성되어 반환.
>>> x = 5 # ints are immutable
>>> y = x
>>> x = x + 1 # 5 can't be mutated, we are creating a new object here
>>> x
6
>>> y
5
리스트 y를 변경할 때 리스트 x도 변경되는 이유는 무엇입니까?
가변객체를 인자로 전달 후 함수내에서 값 변경시 외부값도 같이 변경된다. (참조)
가변객체: list, dictionary 등등
>>> def func2(a):
... a[0] = 'new-value' # 'a' references a mutable list
... a[1] = a[1] + 1 # changes a shared object
>>> args = ['old-value', 99]
>>> func2(args)
>>> args
['new-value', 100]
>>> def func3(args):
... args['a'] = 'new-value' # args is a mutable dictionary
... args['b'] = args['b'] + 1 # change it in-place
>>> args = {'a': 'old-value', 'b': 99}
>>> func3(args)
>>> args
{'a': 'new-value', 'b': 100}
출력 매개변수가 있는 함수를 작성하려면 어떻게 해야합니까
8진수: 0o
+ 8진수 숫자
16진수: 0x
+ 16진수 숫자
이름없는 함수 및 간략함 함수
lambda 매개변수: 표현식
>>> list(map(lambda x: x ** 2, range(5), range(5)))
[0, 1, 4, 9, 16]
from functools import reduce
필요
>>> from functools import reduce
>>> recude(lambda x, y: x+y, [0, 1, 2, 3, 4])
10
>>> list(filter(lambda x: x<5, range(10)))
[0, 1, 2, 3, 4]
reduce: 한 값으로 줄이기
>>> from functools import reduce
>>> recude(lambda x, y: x+y, [0, 1, 2, 3, 4])
10
permutations: 순열
>>> from itertools import permutations
>>> list(permutations([1, 2, 3], 2))
[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
Python purmutation, combination 정리 블로그
combinations: 조합
>>> from itertools import combinations
>>> list(combinations([1, 2, 3], 2))
[(1, 2), (1, 3), (2, 3)]
Python purmutation, combination 정리 블로그
heapq: PriorityQueue(우선순위큐)
>>> import heapq
>>> q = []
>>> heapq.heappush(q, (0, 1))
# min값 반환
>>> a, b = heapq.heappop(q)
0, 1
# min값 접근
>>> a, b = q[0]
# list -> heap 으로 변환
>>> x = [4, 3, 1, 2, 5, 6]
>>> heapq.heapify(x)
>>> x
[1, 2, 3, 4, 5, 6]
노드와 노드 사이에 연결된 간선 정보를 가지고 있는 자료구조
인접행렬
n, m = map(int, input().split())
graph = []
for row in range(n):
line = [int(x) for x in list(input())]
graph.append(line)
인접 리스트
n, m = map(int, input().split())
graph = [[] for i in range(n)]
graph[0].append((1, 7)) #노드 1, cost 7
graph[1].append((0, 7)) #노드 0, cost 7
스택, 큐
재귀: 스택구조, 종료 조건이 필요
DFS: 스택(재귀)
def dfs(graph, v, visited):
visited[v] = True
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
BFS: 큐
def bfs(graph, start, visited):
queue = dequeue([start])
visited[start] = True
while queue:
v = queue.popleft()
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
O(n^2)
def sort(array):
for i in range(len(array)):
min_index = i;
for j in range(i+1, len(array)):
if array[min_index] > array[j]:
min_index = j;
array[i], array[min_index] = array[min_index], array[i]
return array
O(n^2)
but 데이터가 거의 정렬되어 있을 때 효율적
정렬된 상태 + 적절한 위치 찾아 삽입하여 정렬
def sort(array):
for i in range(1, len(array)):
for j in range(i, 0, -1): # i to 1 까지 -1씩 감소
if array[j] < array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
else:
break
return array
O(n log n)
but 데이터가 거의 정렬되어 있을 때 비효율적
pivot 을 기준으로 작은, 큰 데이터 좌우 분리, 분리된 좌, 우 역시 동일 방식으로 정렬
좌 → 우: pivot 보다 큰 데이터, 좌 ← 우: pivot 보다 작은 데이터를 찾아 위치를 서로 변경
작은 데이터 위치가 큰 데이터 위치보다 작은 경우: pivot, 작은 데이터 switch, 종료
재귀 종료조건: 리스트가 1개인 경우 정렬된 상태이므로 반환
pivot 선택기준: 첫번째 데이터 (호어 분할 방식)
def sort(array):
quick_sort(array, 0, len(array)-1)
def quick_sort(array, start, end):
if start >= end: # 원소가 1개인 경우 종료
return
pivot = start
left = start+1
right = end
while left <= right:
while left <= end and array[left] <= array[pivot]:
left += 1 # find 큰값 index
while right > start and array[right] >= aray[pivot]:
right -= 1 # find 작은값 index
if left > right: # 엇갈린 경우: pivot, 작은값 switch
array[right], array[pivot] = array[pivot], array[right]
pivot = right
else: # 큰값, 작은값 switch, 이후 while 통해 다음 switch 진행
array[left], array[right] = array[right], array[left]
# pivot 보다 작은 값들 | pivot | pivot 보다 큰 값들
quick_sort(array, start, pivot-1)
quick_sort(array, pivot+1, end)
def sort(array):
if len(array) <= 1:
return array
pivot = array[0]
tail = array[1:]
left_side = [x for x in tail if x <= pivot]
right_side = [x for x in tail if x > pivot]
return sort(left_side) + [pivot] + sort(right_side)
O(n + k)
(k: 가장큰 수)
범위가 정해진 정수, 중복이 많은 경우 효율적
위치변경 X, 리스트 정보를 통한 정렬
def sort(array):
counts = [0]*(max(array)+1)
for i in range(len(array)):
counts[array[i]] += 1
sorted = []
for i in range(len(counts)):
sorted += [i] * counts[i]
return sorted
O(n log n)
퀵정렬보다는 느리지만 최악의 경우도 보장
O(n)
앞에서부터 차례로 확인
def search(array, target):
for i in range(len(array)):
if array[i] == target:
return i
return -1