이 블로그를 참고하여 작성하였습니다 ! 수학에서 거듭제곱은 같은 수를 거듭하여 곱한 것으로, 주어진 수를 주어진 횟수만큼 여러 번 곱하는 연산입니다. 이는 코드를 통해 쉽게 구현이 가능하지만, 여러 코딩 테스트를 문제를 풀기위해선 효율적으로 구성할 필요가 있습니다. 1. 반복문 사용 def power(a, b): answer = 1 for _ in range(b): answer *= a return answer 2. 재귀함수 사용 \(a^n = a_1 \times a_2 \times a_3 \times \cdots \times a_n\) 는 점화식 \(a^n = a^{n-1} * a\)로 표현할 수 있습니다. def power(a, b): if b == 1: return a return power(a, ..

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) : C..

해쉬 테이블 (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를 활용 ..

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