2/3 (Fri): 파이썬 프로그래밍 FAQ, 코테 알고리즘 공부

Minsang Kang·2023년 2월 3일
0

Python

목록 보기
3/6

Python 프로그래밍 FAQ

parameters & arguments

  • 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 & int 복사

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, 16진수

8진수: 0o + 8진수 숫자
16진수: 0x + 16진수 숫자

프로그래밍 FAQ

Python Lambda 함수

이름없는 함수 및 간략함 함수
lambda 매개변수: 표현식

map(함수, 리스트)

>>> list(map(lambda x: x ** 2, range(5), range(5)))
[0, 1, 4, 9, 16]

reduce(함수, 시퀀스)

from functools import reduce 필요

>>> from functools import reduce
>>> recude(lambda x, y: x+y, [0, 1, 2, 3, 4])
10

filter(함수, 리스트)

>>> list(filter(lambda x: x<5, range(10)))
[0, 1, 2, 3, 4]

Python Lambda 함수 정리 블로그

Python 라이브러리

functools

reduce: 한 값으로 줄이기

>>> from functools import reduce
>>> recude(lambda x, y: x+y, [0, 1, 2, 3, 4])
10

Python Lambda 함수 정리 블로그

itertools

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

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/BFS

스택, 큐

재귀: 스택구조, 종료 조건이 필요

DFS: 스택(재귀)

  • 방문하지 않은 경우 재귀를 통해 새로운 노드 방문
def dfs(graph, v, visited):
    visited[v] = True
    
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

BFS: 큐

  • 방문하지 않은 경우 queue 에 추가, queue 순서에 맞게 노드 방문
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
profile
 iOS Developer

0개의 댓글