DailyStudyNote

Stack1 Stack 자료구조 ✔ 스택 구현 시 고려 사항: 리스트를 사용하여 스택을 구현하는 경우 - 장점: 구현이 용이 - 단점: 리스트의 크기를 변경하는 작업은 내부적으로 큰 오버헤드가 발생하는 작업으로 많은 시간을 소요 ✔ 해결 방법 1) 리스트의 크기가 변동되지 않도록 배열처럼 크기를 미리 정해 놓고 사용하는 방법 2) 동적 연결리스트를 이용하여 저장소를 동적으로 할당하여 스택을 구현하는 방법 - 장점: 구현이 용이 - 단점: 리스트로 구현하는 것보다 구현이 복잡함 괄호 검사 1) 괄호의 종류: 대괄호('[', ']'), 중괄호('{', '}'), 소괄호('(', ')') 2) 조건: (1) 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다. (2) 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보..

List 2 - 정렬(Sort) 정렬(Sort) [셀렉션 알고리즘] 1) 저장되어 있는 자료로 부터 K 번째로 큰 혹은 작은 원소를 찾는 방법이다. (최소 값, 최대 값 혹은 중간 값을 찾는 알고리즘) 2) 셀렉션 선택과정 - 정렬 알고리즘을 이용하여 자료를 정렬 - 원하는 순서에 있는 원소를 가져오기 EX) k 번째로 작은 원소 찾는 알고리즘 1 번부터 k 번까지 작은 원소들을 찾아 List 앞쪽으로 이동시키고, List의 k번째를 반환한다. k가 비교적 작을 때 유용하며 O(kn)의 수행시간을 필요로 한다. def select(list, k): for i in range(0,k): min_index = i for j in range(i+1, len(list)): if list[min_index] > ..

List 2 - 2차원 리스트 2차원 리스트 1) 1차원 리스트를 묶어 놓은 리스트이다. 2) 2차원 이상의 다차원 리스트는 차원에 따라 인덱스를 선언한다. 3) 2차원 리스트의 선언: 세로길이(행의 개수), 가로길이(열의 개수) 를 필요로 한다. 4) 파이썬에서는 데이터 초기화를 통하여 변수 선언과 초기화가 가능하다. 리스트 초기화 # 1차원 리스트 초기화 #1) arr = [0,0,0,0,0] #2) arr = [0] * 5 # res = [0,0,0,0,0] #3) arr = [i for i in range(2,9) if i%2 == 0 ] # res = [2,4,6,8] # 2차원 리스트 초기화 #1) brr = [[1,2,3], [1,2,3], [1,2,3]] #2) brr =[[1,2,3]] ..

List 1 - Brute force, Greedy, 순열, Sort(정렬) 강의 정리(필요하다고 생각되어지는 부분) 문제풀이 정리 Exhaustive Search 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열하고 확인하는 기법을 의미한다. → Brute-force 혹은 Generate-and-Test 기법이라고도 부른다. → 모든 경우의 수를 테스트 한 후 최종 해법을 도출 하므로 수행 속도는 느릴 수 있어도 해답을 찾아내지 못할 확률이 적다. → 주어진 문제를 풀 때, 우선 완전 탐색으로 해답을 도출한 후 성능 개선을 위하여 다른 알고리즘을 사용하여 해답을 확인하는 것이 이상적인 접근 방법이다. 예시 문) Baby Gin 6개의 숫자를 입력 받아 선택된 3개의 숫자가 연속된 숫자(run) 혹..

List 1 강의 정리(필요하다고 생각되어지는 부분) 문제풀이 정리 리스트(List) 1. 시퀀스 자료형(Sequence types) 파이썬(Python)에서는 리스트(List), 튜플(Tuple), range, 문자열(String) 처럼 값이 연속적으로 이어지는 자료형을 시퀀스 자료형(Sequence types)라고 한다. [시퀀스 자료형의 특징] 데이터를 순서대로 하나씩 나열하여 나타낸 데이터 구조이므로 특정 위치의 데이터를 가리킬 수 있다. 시퀀스 자료형으로 만든 객체를 시퀀스 객체라고 하며 시퀀스 객체에 들어있는 각 값을 요소(Element)라고 한다. [시퀀스 자료형의 활용] (1) 특정 값이 있는지 확인 하기 → (값) in (시퀀스 객체) → (값) not in (시퀀스 객체) >>> a =..

힙(Heaps) 힙(Heap) 이란 ? 완전 이진 트리(Complete Binary Tree)로 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(Max Heap), 작아야(Min Heap) 한다. 힙은 우선순위 큐를 구현하거나, 힙 정렬을 하는 데 사용된다. 루트 노드에 있는 값이 최대값, 혹은 최소값이며, 자식 노드들의 값의 위치는 기본적인 조건만 맞추면 된다. 최대 힙(Max heap) 원소 삭제 1. 루트 노드 제거: → Max heap의 경우 최대 값 제거 → Min heap의 경우 최소 값 제거 2. 트리의 마지막 자리 노드를 임시로 루트 노드 자리에 배치 3. 자식 노드들 과의 값 비교 하며 아래로 이동 → 자식 노드들 중 더 큰 값 기준으로 이동 최대 힙(Max heap) 원소 삭제 - ..

힙(Heaps) 힙(Heap)이란? 이진 트리의 한 종류 (이진 힙-binary heap)이다. 1. 루트(root) 노드가 언제나 최댓값 또는 최솟값을 가진다. 최대 힙(max heap) 최소 힙(min heap) 2. 완전 이진 트리 완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조 로서 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다. 최하단 레벨의 노드는 좌측만 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 한다. 노드를 삽입할 때는 최하단 좌측 노드부터 차례대로 삽입해야 한다. 최대 힙(max heap)의 추상적 자료 구조 재귀적으로도 정의된다. 즉, 어느 노드를 루트로 하는 서브 트리도 모두 최대 힙 이다. 연산의 정의 __init__(): 빈..

이진탐색트리(Binary Search Tree) 이진탐색 트리에서 원소 삭제 1. 키(Key)를 이용해서 노드를 찾는다. 해당 키의 노드가 없으면, 삭제할 것도 없다. 찾은 노드의 부모 노드도 알고 있어야 한다. 2. 찾은 노드를 제거하고도 이진탐색 트리 성질을 만족하도록 트리의 구조를 정리한다. 인터페이스의 설계 ✔ 입력 : 키(Key) ✔ 출력: 삭제한 경우 True, 해당 키의 노드가 없는 경우 False class BinarySearchTree: def remove(self, key): node, parent = self.lookup(key) if node: ... return True else: return False 이진탐색 트리 구조의 유지 삭제되는 노드가, 1. 말단(leaf) 노드인 경우..