알고리즘
-
알고리즘 기초 04) 힙 (Heap) 자료 구조Algorithm 공부자료/기본 알고리즘 정리 2020. 3. 12. 01:14
사전 개념 : 우선순위 큐 (Priority Queue) 자료 구조 우선 순위의 개념을 queue에 도입한 자료 구조이다. 데이터들이 우선 순위를 갖고 있으며, 우선 순위가 높은 데이터가 먼저 빠져나간다. 대표적인 사용처 : 시뮬레이션 시스템, 네트워크 트래픽 제어, CPU scheduling, 수치 해석적인 계산 등 구현 : list (array), linked list, heap 등으로 구현이 가능하며, 이 중 heap으로 구현하는 것이 가장 효율적이다. 개념 complete binary tree의 일종으로 우선순위 큐의 구현을 위해서 만들어진 자료 구조이다. 시간 복잡도 : O(logN) 여러 개의 값들 중에서 max 혹은 min value를 빠르게 탐색하기 위해서 만들어졌다. 중복된 값을 허용하지..
-
알고리즘 기초 03) 트리 (tree) 자료 구조Algorithm 공부자료/기본 알고리즘 정리 2020. 3. 12. 00:56
개념 node와 node를 연결하는 edge로 구성된 자료구조이다. 비선형 자료구조의 일종으로 계층 구조를 이룬다. tree 표현에 사용되는 용어 degree : 차수, 특정 노드의 자식 노드 수 height : 높이, root node에서 최하위 노드까지의 길이 level : 레벨, 각 층의 번호 - root node : level 1 tree vs graph : tree는 graph의 한 종류로써, cycle이 없는 일종의 connected graph이다. 대표적인 사용처 : 각종 탐색 Binary Tree (이진 트리) 최대 2개의 자식 노드를 갖는 트리 종류 1) Complete binary tree (완전 이진 트리) 2) Full binary tree (포화 이진 트리) 3) Skewed bi..
-
프로그래머스) 코딩테스트 연습 : 스택/큐 - 탑Algorithm 공부자료/알고리즘 문제풀이 2020. 3. 11. 15:01
문제와 관련한 모든 저작권은 프로그래머스 측에 있음을 명시합니다. 문제 설명 구현 아이디어 stack 자료 구조를 사용해서 구현하였다. 원래는 맨 앞에 위치한 탑에서 보내는 신호 처리를 먼저 하려고 계획 했으나, 왼쪽으로 신호를 보내는 상황이라 마지막 탑부터 처리하는 것이 자연스러워 보였고, 이에 따라서 LIFO 구조를 사용하기로 했다. 현재 처리해야하는 탑을 제외한 나머지 탑만 남겨두는 임시 stack을 하나 만들어 두고, 임시 스택의 맨 마지막 탑의 길이와 현재 처리해야하는 탑의 길이를 비교하며 처리했다. 신호를 받을 수 있는 탑이 아예 없는 경우를 처리하기 위해서 flag라는 변수를 추가하였다. 문제 풀이와 관련한 모든 저작권은 작성자에게있음을 명시합니다. 소스 코드
-
백준 #10845 큐 파이썬으로 구현하기Algorithm 공부자료/알고리즘 문제풀이 2020. 3. 10. 02:16
문제 설명 기본 개념'기본개념'을 클릭하면, queue 자료구조에 관한 간략한 개념을 알아볼 수 있다. 구현 아이디어파이썬에서 제공하는 다른 자료구조 (collection 등)을 사용해볼까 했는데, 그냥 list를 이용해서 간단히 구현하였다.sys.stdin.readline() 이 아닌 input() 함수를 이용 시, 시간 초과 에러가 뜬다. 입력받은 명령어에 따라서 if-elif 문을 이용하여 해당 명령을 처리한다.파이썬에서 기본적으로 제공하는 insert, pop, len 함수만으로 구현이 충분히 가능하다. stack을 구현할 때와 다르게, push 작업을 하면 list의 0번째 자리에 새로운 요소가 추가되야 하므로, insert 함수를 사용하였다.front와 back 명령이 자칫 헷갈릴 수 있으나,..
-
백준 #10828 스택 파이썬으로 구현하기Algorithm 공부자료/알고리즘 문제풀이 2020. 3. 10. 01:52
문제 설명 기본 개념 '기본개념'을 클릭하면, stack 자료구조에 관한 간략한 개념을 알아볼 수 있다. 구현 아이디어 파이썬의 리스트가 기본적으로 stack 구조를 따른다. sys.stdin.readline() 이 아닌 input() 함수를 이용 시, 시간 초과 에러가 뜬다. 입력받은 명령어에 따라서 if-elif 문을 이용하여 해당 명령을 처리한다. 파이썬에서 기본적으로 제공하는 append, pop, len 함수만으로 구현이 충분히 가능하다. 소스 코드 import sys N = int(sys.stdin.readline()) stack = list() for i in range(N): cmd = sys.stdin.readline().split() if cmd[0] == "push": stack.ap..