Jamie's CodeSprout

보호되어 있는 글입니다.

힙 & 힙 정렬 (heap sort) 힙 heap 현재 개발된 가장 작은 자료구조들 중 하나 이진 트리의 일종으로 이진 트리에 어떤 특성을 부여한 것 (아래에서 이진 트리 binary tree 검색) 힙을 통해 '힙 정렬’과 '우선순위 큐priority queue’를 구현 이진 힙 구조의 정의 배열(array) 구조이면서, 완전 이진 트리로 시각화 가능 인덱스 0이 루트 왼쪽부터 다음 인덱스의 노드를 채워감 (완전 트리) 트리의 사이즈를 n이라고 했을 때, n/2+1부터 n까지의 노드는 모두 단말 노드(leaf) 특정 노드의 인덱스 i에 대해서 root of tree는 first element (i = 1) parent(i) = i/2 left(i) = 2i right(i) = 2i + 1 특정 노드로 ..

2022-11-09 중위 표기식과 후위 표기식의 개념, 스택으로 계산기 구현하기 출처: https://www.youtube.com/watch?v=G9ujrSGEB4A&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=10 https://www.youtube.com/watch?v=MYk4autDAJ0&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=10 무엇? 연산자 operator 피연산자 operand 토큰 token : 코드 상에서 연산자와 피연산자를 의미 이항연산자 binary operator: 2+3, 2*5처럼 두 수를 필요로 하는 연산자 단항연산자 unary operator: +3 같은 경우 infix 수식: 연산자가 피연산자 ..

참고: https://www.boostcourse.org/ai100/lecture/739169?isDesc=false https://www.boostcourse.org/cs112/lecture/119044?isDesc=false 스택과 큐 자료구조는 예전에 인공지능 강좌 들을때 정리해둔 것, 정글 들어오기 전에 부스트코스에서 CS50 모두의 컴퓨터 과학 강좌를 들으며 정리한 내용이다. (CS50 강좌는 진짜 모두에게 추천이다. 너무 너무 재밌고 퀄리티가 아주 좋다. 이런 강의를 지구 반대편에서 무료로 들을 수 있어서 감사했다.) 자료 구조 데이터를 저장하는 형태와 집합 효율적인 문제 해결을 위해 올바른 자료 구조를 택해야 함! 스택 stack 나중에 넣은 데이터를 먼저 반환하는 메모리 구조 (Last I..

참고: 부스트코스 CS50 모두를 위한 컴퓨터과학 에드위드 파이썬으로 배우는 알고리즘 기초 검색 알고리즘 검색 알고리즘이란? 선형 검색linear serach 이진 검색binary search 배열이 정렬되어 있음을 가정(미리 정렬해야함) 중간 인덱스부터 시작 → 찾고자 하는 값과 비교하며 오른쪽, 왼쪽으로 갈지 결정 → 오른쪽 중간, 왼쪽 중간에서 똑같은 과정 반복 슈도코드 If no items Return false If middle item is 50 Return true Else if 50 middle item Search right half 분할정복 알고리즘 설계 알고리즘 설계 종류 Brute-force (단순무식) ..

참고: 부스트코스 CS50 모두를 위한 컴퓨터과학 에드위드 파이썬으로 배우는 알고리즘 기초 알고리즘 1. 알고리즘 표기법 빅O와 빅Ω 빅O 알고리즘 실행 시간의 상한 최악의 경우! (즉, 자료가 맨 마지막 경우에 발견되거나, 리스트 안에 없는 경우) O는 "on the order of"의 약자 → "~만큼의 정도로 커지는" 알고리즘별 일반적인 빅O O(n²) - 버블 정렬, 선택 정렬, 삽입 정렬(정렬이 하나도 안 된 경우) O(n log n) O(n) - 선형 검색 O(log n) - 이진 검색 O(1) 빅Ω 알고리즘 실행 시간의 하한 운이 좋은 경우! 알고리즘별 일반적인 빅Ω Ω(n²) - 버블 정렬, 선택 정렬 Ω(n log n) Ω(n) - 배열 안에 존재하는 값의 개수 세기, 버블정렬(이미 정렬..