먹고 기도하고 코딩하라

졸업 전시회가 1개월 남은 데다가 새로운 스터디를 2개 시작해서 몸이 2개라면 얼마나 좋을까 공상의 나래를 펼치는 요즘이다. 오늘은 오랜만에 저번에 정리를 못 끝낸 자료구조 이론을 정리할까 한다. 사실 힙은 트리를 설명할 때 함께 설명하는 것이 좋다는 생각이 들지만, 적어도 파이썬에서는 힙을 직접 구현하기보다는 내장된 heapq를 사용하는 것이 훨씬 낫다는 생각에 이 글에 쓴다. 6. 우선순위 큐 (Priority Queue) 우선순위 큐는 큐의 심화판이다. 큐는 FIFO, 선입선출 자료구조이다. 우선순위 큐 역시 큐와 비슷한 자료구조이기는 하지만, 일반적인 큐에서는 우선권을 따지지 않는 반면 우선순위 큐에서는 큐에 들어오는 자료마다 우선순위가 있어 우선순위가 높은 것은 나중에 들어왔더라도 더 먼저 나가..

저번 포스팅에 이어 이번에는 스택과 큐, 데크 자료구조에 대해 알아보자. 3. 스택 스택은 LIFO, Last In First Out, 후입선출 자료구조이다. 설거지하기, 돈돈 초코볼 등 다양한 비유가 있다. 설거지할 때를 생각해보면, 다 먹고 난 접시를 아래서부터 위로 차곡차곡 쌓는다. 그리고 접시를 닦을 때는 맨 위에 있는 접시부터 꺼내서 닦는다. 이것이 바로 후입선출, 가장 마지막에 들어간 데이터가 가장 처음 나오는 자료구조다. 스택의 연산에는 다음과 같은 것들이 있다. push : 스택의 맨 위(뒤)에 데이터를 삽입하는 연산. 시간복잡도 O(1) pop : 스택의 맨 위(뒤)에서 데이터를 꺼내는 연산. 시간복잡도 O(1) peek : 스택의 맨 위의 데이터를 보는 연산. 꺼내지 않는다. 시간복잡도..

파이썬은 비교적 자유도가 높은 언어이다. (확실히 C나 Java에 비해서는) 동적 타이핑이 가능하고, 언제든 변수의 타입을 바꿀 수도 있다. 그래서인지 리스트 하나의 내장 메소드를 사용해 배열, 큐, 스택을 쉽게 만들 수 있는 등 장점이 많다. 이번 포스팅에서는 배열과 연결 리스트, 스택과 큐, 덱까지 살펴보겠다. 먼저 ADT의 개념부터... ADT(Abstract Data Type)란 유사 동작을 하는 자료구조 클래스에 대한 모델을 가리킨다. 어떤 프로그래밍 언어로 구현된 것이 아니고 단지 이 자료구조가 어떤 동작을 하며 어떤 프로퍼티를 갖는지... 뭐 그런 것들을 기술한 것이다. 추상 데이터 타입이라고도 부른다. 1. 배열 배열(Array)은 가장 익숙한 자료구조일 것이다. 요소들이 연속된 메모리에 ..

1. 선택 정렬 선택 정렬(selection sort)는 이중 for 루프를 이용해 자료구조를 정렬하는 정렬 방식이다. 바깥 루프는 0에서 자료 개수 n - 1까지, 안쪽 루프는 바깥 루프의 인덱스 i + 1부터 자료 개수 n까지 루프를 돌린다. 일반화하면 시간복잡도는 O(n^2)이다. 매 바깥 루프가 시작할 때마다 min_idx는 i로 정해진다. i 이전 인덱스까지는 이미 정렬이 됐다고 보고(실제로 그렇다), 매 시작 시마다 정렬이 안 된 것들 중에서 가장 작은 값을 가리키는 인덱스는 임의로 i로 설정하겠다 이 말씀이다. 오름차순 정렬일 경우 바깥 for 루프가 한 번 끝나면, i 인덱스는 남은 값들 중 가장 작은 값을 담는 인덱스가 된다. 왜냐하면, 안쪽 for 루프에서 나온 min_idx가 남은 데..

1. 1부터 n까지의 합 공식 : n * (n + 1) / 2 1-1. n부터 m까지의 합 공식 : ((m - n + 1) * (n + m)) / 2 2. 1부터 n까지의 제곱의 합 공식 : (n * (n + 1) * (2n + 1)) / 6 3. 팩토리얼 구하기 (1) 반복문 # 입력 : 팩토리얼을 구하고 싶은 정수 n # 출력 : n! (정수) def solution(n): res = 1 for i in range(1, n+1): res *= i return res print(solution(5))# 120 (2) 재귀함수 # 입력 : 팩토리얼을 구하고 싶은 정수 n # 출력 : n! (정수) def solution(n): if n dest로 깔려 있던 n-1개의 고리를 옮긴다. 고리를 옮기는 것은 ..