Develop/Python

1. DP (Dynamic Programming) 란?복잡한 문제를 여러 개의 작은 부분 문제 (Sub-Problem)로 나누어 해결하는 방법 !(작은 문제에서 구한 답을 다시 그것을 포함하는 큰 문제에서 사용)한번 계산한 문제는 다시 계산하지 않도록 하는 방법 ! 대표적인 예시로 피보나치 수열이 있습니다.피보나치 수열은 N번째의 값 = N-1 번째의 값 + N-2 번째의 값을 계산하는 수열입니다.위 그림처럼 분할하여 답을 구하는데, 중간에 중복 호출이 발생하기 떄문에 Memoization 기법을 사용합니다. Memoization 이란?프로그래밍 할 때, 반복되는 결과를 메모리에 저장하여 중복호출 되었을 때, 한 번 더 계산하지 않고 메모리에 저장되어 있는 것을 가져와서 재활용 하는 기법 입니다.장점으로..

1. 다익스트라 (Dijkstra) ?최단 경로를 구하는데 사용되는 알고리즘 중 하나입니다.즉, 한 지점에서 다른 한 지점까지의 최단 경로한 지점에서 다른 모든 지점까지의 최단 경로모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘입니다.자료구조로는 Graph를 사용하며, 노드(vertex)와 경로 또는 거리 는 간선(edge)을 사용하여 실제 거리를 표현합니다. 2. 다익스트라 알고리즘의 과정다익스트라 알고리즘은 매번 가장 거리가 짧은 노드를 선택해서 정해진 경로에 따라 과정을 계속적으로 반복하게 됩니다.출발 노드를 지정최단 거리 리스트 초기화 (매번 최단 기록 갱신)방문하지 않은 노드 중 가장 거리가 짧은 노드 선택해당 노드 방문 후 다른 노드로 가는 거리를 계산 후 최단 거리 갱신위 과..

힙 (Heap) 자료구조 힙 (Heap) 이란?완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.여러 개의 값들 중에서 최대값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다.$\rightarrow$ 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다.$\rightarrow$ 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 작은 이진 트리이다.힙에서는 중복된 값을 허용한다. 힙 (Heap) 의 종류최대 힙(max heap)부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리부모 노드 $\geq$ 자식 노드최소 힙(min heap)부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같..

트리 (Tree) 1. 트리 (Tree) 구조트리 : Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조$\rightarrow$ 트리 중 이진 트리(Binary Tree) 형태의 구조로 탐색 알고리즘 구현을 위해 많이 사용됨 2. 알아둘 용어Node : 트리에서 데이터를 저장하는 기본 요소, 데이터와 다른 연결된 노드에 대한 Branch 정보 포함Root Node : 트리 맨 위에 있는 노드Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 길이를 나타냄Parent Node : 어떤 노드의 다음 레벨에 연결된 노드Child Node : 어떤 노드의 상위 레벨에 연결된 노드Leaf Node(Terminal Node) : Child Nod..

해쉬 테이블 (Hash Table) 1. 해쉬 구조Hash Table : 키(Key)에 데이터(Value)를 저장하는 데이터 구조Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라진다.파이썬 딕셔너리(Dictionaray) 타입이 해쉬 테이블의 예이다.2. 알아둘 용어해쉬(Hash) : 임의의 값을 고정 길이로 변환하는 것해쉬 테이블(Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조해싱 함수(Hashing Function) : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address) : Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 ..

링크드 리스트 (Linked List) 1. 링크드 리스트 (Linked List) 구조: 연결 리스트라고도 함: 배열을 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조: 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조: 본래 C언어에서는 주요한  데이터 구조이다. 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원한다.: 링크드 리스트의 기본 구조와 용어노드(Node) : 데이터 저장 단위 (데이터 값, 포인터)로 구성포인터(Pointer) : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간2. 간단한 링크드 리스트 예Node 구현$\rightarrow$ 파이썬에서는 링크드 리스트 구현 시 class를 활용# 1class N..

스택 (Stack)스택은 박스 쌓기에 비유할 수 있습니다. 흔히 박스는 아래에서부터 위로 차곡차곡 쌓습니다.그리고 아래에 있는 박스를 치우기 위해서는 위에 있는 박스를 먼저 내려야 합니다. : 데이터를 제한적으로 접근할 수 있는 구조$\rightarrow$ 한쪽 끝에서만 자료를 넣거나 뺼 수 있는 구조: 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조$\rightarrow$ LIFO(Last-In-First-Out) 구조 1. 스택 구조스택은 LIFO 또는 FILO 데이터 관리 방식을 따른다.LIFO : 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책FILO : 처음에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책$\rightarrow$ 대표적으로 컴퓨터 내부..

큐 (Queue) 1. 큐 구조가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조FIFO(First-In-First_Out) 또는 LIFO(Last-In-Last-Out) 방식으로 스택과 꺼내는 순서가 반대이다. 2. 알아둘 용어Enqueue : 큐에 데이터를 넣는 기능Dequeue : 큐에서 데이터를 꺼내는 기능 3. Python의 queue 라이브러리 활용하여 큐 자료 구조 사용하기Queue 라이브러리에서는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 제공Queue() : 가장 일반적인 큐 자료 구조LifoQueue() : 나중에 입력된 데이터가 먼저 출력되는 구조(스택 구조)PriorityQueue() : 데이터마다 우선순위를 넣어, 우선순위가 높은 순으..