넘치게 채우기

C++ 순열: next_permutation()을 이용한다. 주로 do~while문화 함께 쓰인다. #include #include #include int main() { std::vector vec = {1, 2, 3}; std::sort(vec.begin(), vec.end()); do { for (int i : vec) { std::cout

입출력 import sys sys.stdin.readline() # 한줄 전체 입력받기. input()보다 빠르게 입력받을 수 있다. 개행문자 \n도 딸려오니 주의. a, b, c = map(int, sys.stdin.readline().split()) # a, b, c에 각각 넣기 형변환 int(x) # int로 변환 str(x) # 문자열로 변환 float(x) # 실수 타입 변환 chr(x) # 문자로 변환 bool(x) # 참/거짓값으며 변환(0이나 null이 아닌경우 모두 True) 수학 1e9 = 10^9 2e9 = 2 * 1e9 (INT_MAX에 거의 근접한 값이다) 1e9 + 7 # 보통 온라인 저지 사이트나 알고리즘 대회에서 값이 너무 커질 때, 오버플로우를 막기 위해서 1e9 + 7로 ..

BFS BFS(Breadth First Search)는 너비 우선 탐색으로, 가까운 노드부터 탐색하는 알고리즘이다. BFS에서는 큐 자료구조를 이용하여 구현한다. 인접한 노드들 중 방문하지 않은 노드를 큐에 추가하면 가까운 노드부터 탐색하는 것이다. 동작 방식은 다음과 같다: 1. 탐색 시작 노드를 큐에 넣고, 방문처리한다. 2. 큐에서 노드를 꺼내 큐의 인접 노드들 중 방문하지 않은 모든 노드들을 큐에 삽입하고, 순서대로 방문처리한다. 3. 2번의 과정을 계속해서 반복한다. 노드 '1'부터 시작해서 '1'을 큐에 넣고 방문처리한다. 노드 '1'을 큐에서 꺼내고, '1'의 인접 노드들 중 방문하지 않은 노드들을 모두 큐에 넣고 방문처리한다. 노드 '2'를 큐에서 꺼내고, 2에 인접한 노드들 중 방문하지 ..

재귀 함수란 자기 자신을 다시 호출하는 함수를 의미한다. 자기 자신을 계속해서 호출하다가, 일정한 조건이 만족되면 함수를 반환하여 결과를 도출한다. 컴퓨터 내에서 재귀 함수는 스택 자료구조와 동일하다. 함수를 계속 호출했을 때, 마지막으로 호출된 함수가 먼저 종료되어야 첫 함수가 종료된다. 아래는 재귀 함수의 대표적인 예시인 팩토리얼이다. def factorial(n): if n == 0 or n == 1: return 1 else: return n * factorial(n-1) 재귀 함수의 장점은 수학의 점화식을 표현한 코드여서 매우 간결한 표현이 가능하단 것이다. 단, 끝없이 재귀 함수가 반복되지 않도록 함수를 끝낼 수 있도록 조건을 만들어놓아야 한다.

이진 탐색 트리? 이진 탐색 트리는 다음과 같은 조건이 있다: 같은 key값을 가지는 노드는 없다. 루트노드의 왼쪽 서브트리는 루트노드보다 작은 값들만 있어야 한다. 루트노드의 오른쪽 서브트리는 루트노드보다 큰 값들만 있어야 한다. 루트노드의 서브트리들 모두 이진 탐색 트리여야 한다. 이 조건들로, 이진 탐색 트리를 순회할 때 에는 보통 중위 순회를 이용한다. 이진 탐색 트리에는 세 가지 연산이 있다. 탐색(Search) 삽입(Insert) 삭제(Delete) 탐색 만약, 루트와 같은 값을 가진다면, 탐색을 멈춘다. 루트가 없는 경우 역시 탐색을 멈춘다. 만약, 루트보다 작은 값을 가진다면 왼쪽 서브트리에서, 더 큰 값을 가지면 오른쪽 서브트리에서 재귀한다. 구현 def _search(self, root..

해시 테이블(Hash Table)은 해시 함수를 통해서 얻은 인덱스에 key 와 value값을 저장하는 자료 구조이다. 해시 함수는 같은 key값을 받으면 같은 인덱스값으로 반환시킨다. 해시 함수 해싱을 하는 해시 함수에는 다음과 같은 것들이 있다: 1. Division Method: 가장 쉽고 간단한 방법이다. key값을 해시 테이블의 크기로 나눈 나머지를 인덱스로 정하는 것이다. h(k) = k mod m (k = key, m = size of hash table) m값은 소수이고, 2의 제곱수와 먼 값을 사용해야 효율적이라고 한다. 2. Multiplication Method: key값과 A(0 < A < 1)의 곱의 소수 부분에 테이블의 크기 m을 곱한 값의 정수값을 인덱스로 한다. h(k) = ..

덱 덱(deque)는 double - ended - queue의 줄임말로, 앞뒤로 빼고, 넣는 것이 가능한 자료구조이다. 큐와 스택을 합친 자료구조라고 볼 수도 있다. 파이썬에서는 collections 라는 모듈에서 쉽게 사용할 수 있다. 리스트와 비슷해보이는 연산들이 있지만, 들여다보면 차이가 존재한다. 리스트는 맨 앞 데이터를 빼면, 뒤에 있는 데이터들이 다 앞으로 당겨져서 시간복잡도가 O(n)이 된다. 덱은 이중 연결리스트 기반으로 구현되어, 맨 앞 데이터를 빼더라도 시간복잡도가 O(1)이다. 덱의 연산 appendleft(): 앞쪽으로 데이터 enqueue popleft(): 앞쪽에서 데이터 dequeue append(data): 뒤쪽으로 데이터 enqueue pop(): 뒤쪽에서 데이터 dequ..

큐(Queue) 큐 자료구조는 우리가 평소에 줄을 서듯, 먼저 들어온 사람이 먼저 나가는, 선입선출(先入先出, First in First out)의 형식을 따른다. 큐의 연산 큐의 연산은 다음 5가지가 있다: isEmpty(): 큐가 비어있는지를 판단한다. True 또는 False값으로 반환된다. enqueue(data): 큐에 값을 입력시킨다. dequeue(): 큐의 제일 먼저온 값을 내보낸다. rear(): 큐의 맨 뒤에 있는 값을 반환한다. front(): 큐의 제일 반저온 값을 반환한다(큐에서 pop하지는 않는다) 큐의 구현 - 배열을 이용한 구현(Python) class queue(): #큐 선언 def __init__(self): self.arr = [] def isEmpty(self): #..

스택(Stack) 스택 자료구조는 탄창에 총알을 넣고 빼듯, 먼저 넣은 데이터를 늦게 꺼내는 선입후출(先入後出, FILO(First in Last out)), 후입선출(後入先出, LIFO(Last in First Out))을 따른다. 스택의 연산 스택의 연산은 다음 4가지가 있다: isEmpty() : 스택이 비어있는지를 판단한다. push(data) : 스택의 맨 위에 데이터를 쌓는다 pop() : 스택의 맨 위 데이터를 스택에서 뺀다. top() : 스택의 맨 위의 값을 확인한다. 스택의 구현 - 배열을 이용한 구현(Python) class stack(): #스택 선언 def __init__(self): self.arr = [] def _len_(self): return len(self.arr) de..

연결 리스트(Python) - 전체 class Node(): #노드 선언 def __init__(self, data, next = None): self.data = data self.next = next class SimplyLinkedList(): def __init__(self): self.head = None def link(self, node, next): #노드 연결 node.next = next def getTail(self): #꼬리 노드 불러오기 currentNode = self.head while currentNode.next: currentNode = currentNode.next return currentNode def getIndex(self, data): #data의 인덱스 반환 ..