한 줄에 여러 개 입력받기Python 문제를 해결하다 보면, 한 줄에 여러 개의 입력을 받아야 하는 경우가 생긴다. 그러나 Python은 개행('\n')을 하나의 입력으로 인식하기 때문에 '5 4 1 3 2', '7 3'과 같이 인식한다. 이때, map 함수와 split 함수를 활용하면 각각의 정수로 분리하여 여러 개의 변수에 저장할 수 있다.한 줄에 여러 개 입력받기한 줄에 여러 개 입력을 받는 형태를 살펴본 후에 map과 split 함수에 대해 알아본다. 관련 자료를 찾다가 사용 예시가 있어서 가져왔다.예시 출처# 1. 값 두 개를 입력받아 변수 a와 b에 저장 (띄어쓰기 구분)a, b = input().split() # 문자열a, b = map(int, input().split()) # 정수형a, ..
데크(Deque)란?큐(queue)는 선입선출(FIFO) 방식으로 작동하며, 스택(Stack)은 후입선출(LIFO) 방식으로 작동한다. 큐와 스택이 합쳐져 양방향에서 Push와 Pop을 할 수 있는 자료구조가 데크(Deque)이다. 앞, 뒤 방향에서 요소(element)를 추가하거나 제거할 수 있다. 큐와 스택은 반대쪽에 존재하는 요소를 Pop 하려면 O(n)의 시간이 필요하지만, 데크를 사용하면 어느 방향이든 O(1)의 시간으로 연산을 수행할 수 있다.파이썬 라이브러리 deque파이썬에서는 데크를 라이브러리로 사용할 수 있다. 아래의 공식문서에서 자세한 설명과 예시를 확인해 볼 수 있다. 여기에는 알고리즘 문제를 해결할 때 필요한 연산을 정리하려고 한다. collections — Container da..
동적 계획법(Dynamic Programming, DP)이란?동적 계획법이란 하나의 큰 문제를 여러 개의 작은 부문제로 나누고, 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 기법이다.동적 계획법 vs 재귀적 호출재귀적 호출일반적인 재귀 방식은 동적 계획법과 매우 유사하다. 단, 재귀를 사용 시 동일한 작은 문제가 여러 번 반복되어 비효율적인 계산이 이루어진다는 것이다. 예를 들어 피보나치 수열을 살펴보자. 각 항을 구하기 위해 f(1), f(0)이 등장할 때까지 계속해서 반환하고, 더하는 작업을 진행한다. 또한 값을 따로 저장해두지 않기 때문에 이전에 구했던 값을 다시 처음부터 계산한다. 이러한 계산 방식 때문에 구하는 항이 증가함에 따라 계산 횟수가 기하급수적으로 늘어난다. 1, 1, 2..
힙(Heap)이란?힙(Heap)이란 최댓값/최솟값을 빠르게 찾기 위해 고안되었으며, 루트 노드가 언제나 최댓값(최대 힙) 또는 최솟값(최소 힙)을 가지는 완전 이진트리(Complete Binary Tree)이다. 일반적인 리스트를 활용하여 최댓값/최솟값을 찾기 위한 max()/min() 함수의 시간 복잡도는 O(n)이다. 그러나 힙을 사용하면 O(log n)으로 수행이 가능하며, 정렬도 O(n log n)의 빠른 속도로 가능하다. 연산에 대한 자세한 이해보다는 힙에 대한 개념과 파이썬에서 활용할 수 있는 방법을 이해하는 것을 목표로 한다. 완전 이진 트리(Complete Binary Tree)마지막 레벨(Level)을 제외한 모든 레벨은 완전히 채워져 있는 이진트리이다. 삽입 연산을 수행할 경우 마지막 ..
