Algorithm 공부자료
-
알고리즘 기초 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:09
문제와 관련한 모든 저작권은 프로그래머스 측에 있음을 명시합니다. 문제 설명 구현 아이디어 트럭이 다리 위를 지나가는 흐름에 대해서 생각해보면, FIFO 구조를 사용하는 것이 자연스러우므로, queue 자료구조를 사용하여 구현하였다. 파이썬에서 제공하는 deque를 사용할까 하다가, 많이 복잡한 문제가 아닌 것 같아서 list를 사용해서 구현하였다. truck_weights 리스트에 트럭이 남아있는 동안에, 시간을 하나 씩 늘려 가면서, 1) 현재 다리 위에 있는 트럭을 빼내거나 2) 현재 다리 위에 있는 트럭을 한 칸씩 밀어준다. 동시에 새로 유입되는 트럭에 대해서 생각해야하는데, 1) 현재 다리 위의 트럭 무게에 신규 트럭 무게를 추가해도 괜찮다면, 트럭을 한 대 더 올리고 2) 추가하면 인자로 받은..
-
프로그래머스) 코딩테스트 연습 : 스택/큐 - 탑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 명령이 자칫 헷갈릴 수 있으나,..
-
알고리즘 기초 02) 큐 (Queue) 자료 구조Algorithm 공부자료/기본 알고리즘 정리 2020. 3. 10. 02:07
개념 First In First Out (FIFO) 구조를 따르는 자료구조. 즉, 삽입하는 쪽과 삭제하는 쪽이 서로 반대에 위치 해 있다. 삽입하는 쪽 : rear 삭제하는 쪽 : front 라고 표현함. 삽입 연산을 enqueue, 삭제 연산을 dequeue라고 부름. overflow : queue의 용량이 다 차서 더 이상 enqueue할 수 없는 상태 underflow : queue에 data가 없어서 dequeue할 data가 없는 상태 대표적인 사용처 : CPU scheduling, data buffer, 대기 행렬 정리, 인쇄 작업 대기 목록, 자원을 공유하는 대부분의 경우 등 단점 : 데이터 삽입 후 계속 항목을 삭제 하다보면, 어느 순간 rear pointer와 front pointer가 ..
-
백준 #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..
-
알고리즘 기초 01) 스택 (Stack) 자료 구조Algorithm 공부자료/기본 알고리즘 정리 2020. 3. 10. 01:46
개념Last In First Out (LIFO) 형식을 따르는 자료구조. 즉, 가장 최근에 추가된 항목이 가장 먼저 제거될 항목일시적으로 data를 저장하기 위해서 사용한다. 대표적인 사용처 : 인터럽트의 처리, 수식의 계산, 서브 루틴의 복귀 번지 저장, 부트 프로그램 호출, 지역 변수 저장, 임시 데이터 백업 등 단점 : LIFO로 인한 우선순위 문제가 발생할 수 있다. 새로운 입력이 들어오면, botton에 있는 데이터는 계속 bottom에 있게된다. 연산pop : stack 가장 위의 항목을 제거한다.push : 인자를 stack 가장 위에 추가한다.peek : 제거하지는 않으면서, stack 가장 위의 항목을 출력한다.indexOf : 인자가 stack에 존재 하는지, 존재 한다면 stack의 ..