자료구조/알고리즘
1.[자료구조] 선형 배열(Linear Array)
오늘은 자료구조 중 배열에 대해 알아보려고 한다! 배열과 리스트 배열(Array): 동일한 자료형의 데이터를 여러개 저장하기 위해 한 번에 많은 기억 공간을 만들어 두고 사용하는 기본 자료구조. 행렬 문제나 탐색, 정렬 등에서 사용 차례대로 접근하는 순차처리 접근 방식 새 데이터 삽입이나 삭제 시 많은 시간 소요 파이썬에는 배열이 없고 대신 리스트(li...
2.[알고리즘] 배열-정렬과 탐색(Sort&Search)
오늘은 배열의 정렬과 탐색에 대해서 알아봅시다!! 정렬 알고리즘 정렬: 배열안에 들어있는 원소들을 정해진 기준, 규칙에 따라서 나열 python 리스트의 정렬 1. sorted(L) 내장 함수 (built-in function) 정렬된 새로운 리스트 반환 2. L.sort() 리스트의 메서드 (method) 해당 리스트 정렬 순서를 반대로 정렬(역순...
3.[알고리즘] 재귀 알고리즘(Recursive Algorithms)
이번에는 재귀 알고리즘에 대해서 알아보려고 합니다 :-) 재귀 알고리즘 재귀 알고리즘: 일반적으로 재귀 함수에 의해서 구현 재귀함수(recursive functions): 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것 생각보다 많은 종류의 문제가 재귀적으로 해결 가능 예시 이진트리 (binary trees) 왼쪽 서브트리의 원소들은 모두...
4.[알고리즘] 재귀 알고리즘 응용
지난번에 간단하게 재귀 알고리즘에 대해서 알아보았는데 이번에는 조금 더 자세히 알아보려고 한다! 재귀 알고리즘 응용 재귀함수(recursive function): 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 함수 재귀 알고리즘의 효율성 (조합의 수 계산) 조합의 수 계산 예시를 통해 재귀 알고리즘의 효율성에 대해 알아볼 것이다. 문제: n개의...
5.[알고리즘] 알고리즘의 복잡도(Complexity of Algorithms)
알고리즘의 복잡도 복잡도 시간 복잡도(Time Complexity) 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계 공간 복잡도(Space Complexity) 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계 시간 복잡도 평균 시간 복잡도(Average Time Complexity) 임의의 입력 패턴을 가정했을 때 소...
6.[자료구조] 연결 리스트(Linked Lists) (1)
연결 리스트(Linked Lists) 추상적 자료구조(Abstract Data Structures) 자료구조의 내부구현은 숨겨두고 밖에서 보이는 두가지(Data, A set of operations)를 제공하는 자료구조 Data ex. 정수, 문자열, 레코드, .
7.[자료구조] 연결 리스트(Linked List) (2)
지난번에 연결리스트의 getAt 메소드까지 구현을 해보았다. 이번에는 더 다양한 연산을 구현해보려고 한다! 연결 리스트(Linked List) (2) 연결 리스트 연산 특정 원소 참조 (k번째) 리스트 순회 길이 얻어내기 원소 삽입 원소 삭제 두 리스트 합치기 원소의 삽입 def insertAt(self, pos, newNode): pos가 가리키는 위...
8.[자료구조] 연결 리스트(Linked Lists) (3)
이번에는 연결리스트의 마지막 포스팅을 하도록 하겠습니다!! 연결 리스트(Linked Lists) (3) 연결 리스트가 힘을 발휘할 때 아이폰 실행중인 어플 화면 삽입과 삭제가 유연하다는 것이 가장 큰 장점 빠른 연결 리스트 연결 리스트를 조금 더 빠르게 사용하기 위한 새로운 메서드 insertAfter(prev, newNode) popAfter(prev)...
9.[자료구조] 양방향 연결 리스트(Doubly Linked Lists)
오늘은 연결 리스트에 이어 양방향 연결 리스트에 대해 포스팅 하겠습니다! 양방향 연결 리스트(Doubly Linked Lists) 연결 리스트의 단점 한쪽 방향으로만 이동 가능 반대쪽 방향으로는 이동 불가능 양방향 연결 리스트 한 쪽으로만 Link를 연결하지 말고, 양쪽으로 연결! (next / prev) 앞으로도 (next node) 뒤로도 (p...
10.[자료구조] 스택(Stacks)
이번에는 자료구조 중 특정한 문제를 풀기위한 스택(Stacks)에 대해서 알아보도록 하겠습니다! 스택(Stacks) 자료 (data element)를 보관할 수 있는 (선형) 구조 일렬로 늘어나는 구조 단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고, 푸시 (push) 연산 꺼낼 때에는 같은 쪽에서 뽑아 꺼내야하는 제약 존재 팝 (pop) 연산 ...
11.[자료구조] 스택의 응용 - 수식의 후위 표기법
지난번에 포스팅한 스택 자료구조를 활용하여 수식의 후위 표기법을 구현해보도록 하겠습니다! 스택의 응용 - 수식의 후위 표기법 중위 표기법 (infix notation): 연산자가 피연산자들의 사이에 위치 (A + B) * (C + D) 후위 표기법 (postfix notation): 연산자가 피연산자들의 뒤에 위치 AB+CD+* 괄호가 사라지고 ...
12.[자료구조] 스택의 응용 - 후위 표기 수식 계산
이번에는 후위 표현식으로 되어있는 수식을 계산하는 것을 스택을 활용하여 구현해보도록 하겠습니다! 스택의 응용 - 후위 표기 수식 계산 중위 표기법 (infix notation): 연산자가 피연산자들의 사이에 위치 (A + B) * (C + D) 후위 표기법 (postfix notation): 연산자가 피연산자들의 뒤에 위치 AB+CD+* 괄...
13.[자료구조] 큐(Queues)
스택과 비슷한 자료구조 큐에 대해서 알아보겠습니다! 큐(Quesues) 자료 (data element)를 보관할 수 있는 (선형) 구조 단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 한다. 인큐(enqueue) 연산 꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 하는 제약 존재 디큐(dequeue) 연산 선입선출 (FIFO-First-In First-Out)...
14.[자료구조] 환형 큐 (Circular Queues)
환형 큐 (Circular Queues) 큐(Queue)의 활용 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 (asynchronously) 일어나는 경우 producer가 물건을 만들고 consumer가 처음 만들어 진 것부터 사용하는 경우 자료를 생성하는 작업이 여러 곳에서 일어나는 경우 producer 여러명이 각각 물건을 만...
15.[자료구조] 트리(Trees)
스택, 큐: 1차원 자료구조트리: 2차원 자료구조정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조뿌리(root)&이파리(leaf) (거꾸로된 나무 모양 )루트(Root) 노드: 맨 위의 노드리프(Leaf) 노드: 더 이상의 가지가 없
16.[자료구조] 이진 트리(Binary Trees)
이진트리 (Binary Trees) 이진 트리의 추상적 자료구조 연산의 정의 size(): 현재 트리에 포함되어 있는 노드의 수를 구함 depth(): 현재 트리의 깊이 (또는 높이: height)를 구함 traversal: 순회 이진 트리의 구현 노드 (Node) data/left/right를 가지고 있음 Node Data Left Child ...
17.[자료구조] 이진 탐색 트리
이진 탐색 트리 모든 노드에 대해서, 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진트리 (중복 되는 데이터 원소는 없는 것으로 가정) (정렬된) 배열을 이용한 이진 탐색과 비교 장점: 데이터 원소의 추가, 삭제가 용이 단점: 공간 소요가 큼 이진 탐색 트리의...
18.[자료구조] 이진 탐색 트리 (2)
이진 탐색 트리에서 원소 삭제 키(key)를 이용해서 노드를 찾는다. 해당 키의 노드가 없으면, 삭제할 것도 없음 찾은 노드의 부모 노드도 알고 있어야 함 (아래 2번 때문) 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리한다. 인터페이스의 설계 입력: 키 (Key) 출력: 삭제한 경우 True / 해당 키의 노드가 ...
19.[자료구조] 힙 (Heaps) (1)
힙 (Heap) 이진 트리의 한 종류 (이진 힙 - binary heap) 루트 (root) 노드가 언제나 최댓값 또는 최솟값을 가짐 최대 힙 (max heap), 최소 힙 (min heap) 완전 이진 트리여야한다. 재귀 적으로도 정의 가능 (어느 노드를 루트로 하는 서브트리도 모두 최대/최소 힙) 이진 탐색 트리와의 비교 원소들은 완전히 크기 순...
20.[자료구조] 힙 (Heaps) (2)
힙 (Heap) 힙에서 원소의 삭제 루트 노드의 제거 - 이것이 원소들 중 최댓값 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치 자식 노드들과의 값 비교와 아래로, 아래로 이동 -> 식은 둘 있을 수도 있는데, 어느 쪽으로 이동? 더 큰 키 값을 가지는 쪽으로 이동 힙으로부터 원소 삭제 - 복잡도 원소의 개수가 n인 최대 힙에서 최대...