본문 바로가기

엘리스AI트랙56

[12주차] 분할정복법과 탐욕적기법 4월 9일 자 학습 내용 정리입니다. ✅ 분할정복법 분할정복법은 아래와 같다. 문제를 소문제로 분할한다. 각각의 소문제를 해결한다. 소문제의 해결 결과를 이용해 전체 문제를 해결한다. 분할정복법의 대표적인 예로는 합병정렬과 이분탐색이 있다. ✔️ 합병정렬 합병정렬(Merge Sort)은 흔히 하향식 2-way 방법으로 쓰이는데 이는 다음과 같이 작동한다. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 아래 과정을 거친다. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로.. 2022. 4. 9.
[12주차] 재귀호출 4월 8일 자 학습 내용 정리입니다. ✅ 재귀호출 재귀호출(recursive call)은 함수가 자기 자신을 호출하는 것이다. 이러한 재귀 호출은 자기가 자신을 계속해서 호출하므로, 끝없이 반복되게 된다. 따라서 함수 내에 재귀 호출을 중단하도록 조건이 변경될 명령문을 반드시 포함해야 한다. 재귀호출의 예로는 팩토리얼이 있다. 팩토리얼(factorial)은 n이 하나의 자연수일 때, 1에서 n까지의 모든 자연수의 곱을 n에 상대하여 이르는 말이다. 이를 코드로 구현하면 다음과 같다. def Factorial(n): if n == 0: return 1 else: return n * Factorial(n-1) Factorial 함수의 구현에는 재귀호출이 포함되어있다. n = 5 일 때, Factorial 함.. 2022. 4. 9.
[12주차] 우선순위 큐와 힙 4월 6일 자 학습 내용 정리입니다. ✅ 우선순위 큐 우선순위 큐는 우선순위가 높은 원소가 먼저 출력되는 추상적 자료형이다. 우선순위 큐를 단순히 배열로 구현할 경우 입력은 O(1)이지만 출력은 O(n)이다. 우선순위가 가장 높은 원소를 찾는 과정과 그 원소를 제거하는 과정이 비효율적이라고 할 수 있다. ✅ 힙 힙(Heap)은 최솟값 또는 최댓값을 빠르게 찾기 위해 고안된 완전 이진 트리이다. 힙은 최대 힙과 최소 힙의 두 가지 종류로 나뉜다. 최대 힙(Max Heap)은 부모 노드가 항상 자식 노드보다 큰 값을 가지고 있다는 특징이 있다. 반대로 최소 힙(Min Heap)은 부모 노드가 항상 자식 노드보다 작은 값을 가지고 있다는 특징이 있다. 파이썬에서는 heapq 모듈로 최소 힙을 사용할 수 있다... 2022. 4. 7.
[12주차] 트리의 표현과 트리 순회 4월 6일 자 학습 내용 정리입니다. ✅ 트리의 표현 방법 이진 트리의 각 노드는 왼쪽 또는 오른쪽 자식을 갖고 있으므로 다음 코드와 같이 표현할 수 있다. class TreeNode : def __init__(self) : self.left = None self.right = None 완전 이진 트리는 배열을 이용해 간단하게 구현할 수 있다. 루트 노드부터 깊이를 더해가며 각 정점에 번호를 붙였을 때 어쩐 정점의 번호가 n이라면 왼쪽 자식은 2n, 오른쪽 자식은 2n+1의 인덱스를 가진다. 따라서 이를 배열로 표현하면 아래와 같다. ✅ 트리 순회 트리 순회란 트리의 모든 노드를 방문하는 순서이다. 트리는 비선형 구조로 자료 사이에 정해진 순서가 없기 때문에 각 노드를 방문하고 값을 가져오기 위해 트리 .. 2022. 4. 7.
[12주차] 트리의 개념 4월 6일 자 학습 내용 정리입니다. ✅ 비선형 구조 앞서 포스팅에서 스택과 큐를 배우며 선형 구조와 비선형 구조에 대해 언급했었다. 선형 구조는 자료들이 순서를 가지고 연속된 자료구조를 의미하며 비선형 구조는 자료를 일렬로 나열하기 힘들고 자료의 순서가 불규칙해 연결 관계가 복잡한 구조를 의미한다. 바로 이 비선형 구조의 대표적인 예가 트리(Tree)와 그래프(Graph)이다. ✅ 그래프 트리는 사실 그래프의 특수한 형태 중 하나이다. 따라서 트리를 이해하기 위해서는 그래프의 정의부터 알 필요가 있다. 그래프(Graph)는 정점(vertex)과 간선(edge)으로 이루어져 있는 자료구조이다. 정점(vertex)은 자료, 상태 등 값을 담고있는 것을 의미하며 노드라고 부르기도 한다. 간선(edge)은 정.. 2022. 4. 7.
[11주차] 스택과 큐 4월 2일 자 학습 내용 정리입니다. ✅ 선형 구조와 비선형 구조 자료구조는 선형 구조와 비선형 구조로 나눌 수 있다. 선형 구조는 자료들이 순서를 가지고 연속된 자료구조를 의미한다. 반대로 비선형 구조는 일렬로 나열하기 힘들고 자료의 순서가 불규칙해서 연결 관계가 복잡한 구조를 말한다. 선형 구조에는 스택(Stack), 큐(Queue) 등이 존재하고 비선형 구조에는 트리(Tree), 그래프(Graph) 등이 존재한다. ✅ 스택 스택(Stack)은 한쪽 끝에서만 자료를 넣고 뺄 수 있는, Last-In First-Out(LIFO, 후입선출)의 특징을 가진 자료구조이다. 스택이 지원하는 연산 목록은 아래와 같다. push : 자료 삽입 pop : 자료 제거 top : 스택의 가장 위에 있는 자료 반환(마지.. 2022. 4. 5.
[11주차] 자료구조의 의미와 배열, 연결리스트 4월 2일 자 학습 내용 정리입니다. ✅ 자료구조 자료구조는 말 그대로 자료를 저장하는 구조이다. 자료구조에는 배열, 트리 등 여러 종류가 있으며 저장된 자료에 대해 접근하는 방법이 약간씩 다르다. ✅ 추상적 자료형 자료형이란 어떤 자료가 식별되는 방법을 정의하고 그 자료에 대한 여러가지 연산(동작)을 제공한다. 여기서 연산이란 그 자료에 어떻게 접근할 것인지, 그 자료를 어떻게 사용할 것인지 등 다양한 동작을 말한다. 추상적 자료형은 어떤 자료와 그 자료에 대한 연산(동작)들의 수학적인 정의를 의미한다. 하지만 이 정의를 구현하는 방법은 명시되어 있지 않다. 따라서 추상적 자료형은 자료들과 그 자료들에 대한 연산들을 개념적으로 정의만 한 것을 말하며 자료구조는 추상적 자료형을 구체적으로 구현해 자료를 .. 2022. 4. 5.
[8주차] 상태 관리에 사용되는 Hook 3월 11일 자 학습 내용 정리입니다. ✅ 상태 관리에 사용되는 Hook 외부 라이브러리 없이 React가 제공하는 Hook 만으로도 상태 관리를 구현할 수 있는데, 함수형 컴포넌트에 상태를 두고 여러 컴포넌트 간 데이터와 데이터 변경 함수를 공유하는 방식으로 상태를 관리한다. ✔️ useState useState는 단순하게 하나의 상태를 관리하기 적합하다. state가 바뀌면 state를 사용하는 컴포넌트를 재렌더링하며 useEffect와 함께 state에 반응하는 Hook을 구축한다. const [state, setState] = useState(initValue | initFn) ✔️ useRef useRef는 상태가 바뀌어도 재렌더링하지 않는 상태를 정의한다. 즉, setTimeout의 timer.. 2022. 3. 11.
[8주차] 상태 관리와 Flux Pattern 3월 11일 자 학습 내용 정리입니다. ✅ 상태 관리 상태 관리란 앱 상에서의 데이터를 메모리 등에 저장하고 하나 이상의 컴포넌트에서 데이터를 공유하는 것을 의미한다. 상태 관리는 한 컴포넌트 안에서의 상태, 여러 컴포넌트 간의 상태, 전체 앱의 상태 관리를 모두 포함한다. 상태 관리 기술은 높은 품질의 코드 작성, 성능 최적화, 네트워크 최적화 등에 유리하다. localStorage 활용한 persist state와 같은 데이터 관리의 고도화를 이룰 수 있다. 상태 관리 기술의 단점도 물론 존재한다. 파악해야 할 로직과 레이어가 많아질 수 있으며 잘못 사용할 경우 앱의 복잡도만을 높이거나 성능을 악화시킬 수 있다. 이러한 예에는 global state를 잘못 활용했을 시 앱 전체에 리렌더링을 발생시켜 .. 2022. 3. 11.