코르시카's Blog

■ 이진 탐색 1) 정의 : 배열 전체의 중간값을 target 값과 비교 중간값이 target 값보다 크면 왼쪽 부분만 선택 왼쪽부분의 중간값을 다시 target 과 비교 ■ 코드 구현 > plain 절차지향 def binary_search(m_list, target): m_list.sort() left = 0 right = len(m_list)-1 while left target: right = mid - 1 else: left = mid + 1 return False target = 25 m_list = [30, 94, 27, 92, 21, 37, 25, 47, 25, 53, 98, 19, 32, 32, 7] print(binary_search(m_list, target)) > 재귀 def binar..

■ 이진 탐색트리 1) 정의 : > Linked list - O(1) 삽입 / 삭제 - O(N) 탐색 복잡도 > Binary Search - 자료구조가 sorting되어있는 상태에서 시행 - O(logN) 탐색 복잡도 ※ 위 두개의 장점을 합친 방식으로 자료구조를 짠 것이 '이진 탐색 트리' 2) 이진탐색 트리 특징 (a) 각 노드의 자식이 2개 이하 (b) 완전이진트리 구조는 아님!! - 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 같거나 큼 (c) 중복노드 많은 경우 - 다른 자료구조 사용하는 것이 효율적 (d) 평균시간복잡도 O(log(N)) 편향 트리인 경우 O(N)에 가까워 짐 → 트리가 왼쪽 / 오른쪽으로 쏠려있는 경우 3) 트리 변경의 3가지 case 자식이 없는 leaf ..

■ 절차지향 1) 정의 : > 순차적인 처리가 중요한 프로그래밍 방식 - 컴퓨터 작업 방식과 비슷 - 데이터 위주의 thinkig 2) 장단점 : > 장점 - 컴퓨터의 처리구조 방식과 비슷해 실행속도가 빠름 > 단점 - 유지보수 어려움 - 실행순 변화에 따른 동일 결과 보장이 어려움 - 디버깅이 어려움 ■ 객체지향 1) 정의 : > 실제 세계를 모델링하여 소프트웨어를 개발하는 방식. - "작동 방식"을 고려하여 전체를 개발하는 방법 - 데이터 + 절차를 한 동작의 덩어리로 묶어서 생각 2) 장단점 : > 장점 - 코드 재활용성 - 코딩이 절차지향보다 쉬움 - 디버깅 용이 > 단점 - 처리속도 느림 - 설계에 많은 시간 소요 3) 객체지향 3대 요소 1. 캡슐화 캡슐화란 관련된 데이터와 알고리즘(코드)이 ..

■ 데이터베이스의 본질 > 어떻게 입력하고 출력 하는가? - 가 본질이 된다 > CRUD 가 본질 1) 입력 - Create - Update - Delete 2) 출력 - Read ■ File vs Spread-sheet vs Database > File로 무언가를 관리하기에 index가 없기 때문에... 검색이 매우 어려움 > Spread-sheet로 table화하여 데이터 관리 가능 but 수많은 데이터에 대해서 작업하기 어려움 ( 데이터 숨김 기능, filtering 등이 있음 ) ■ index란? 추가 참조 : mangkyu.tistory.com/96 [Database] 인덱스(index)란? 1. 인덱스(Index)란? [ 인덱스(index)란? ] 인덱스란 추가적인 쓰기 작업과 저장 공간을 활..

velog.io/@devmin/database-sql-basic-command 데이터베이스의 기본 의미와 MySQL 기본 명령어 사용법 데이터베이스의 기본 의미와 MySQL 기본 명령어 알아보기 velog.io opentutorials.org/course/3161 DATABASE2 - MySQL - 생활코딩 수업소개 무료이면서, 오픈소스이고, 3대 데이터베이스 중에 하나인 MySQL의 입문 수업입니다. 수업대상 정보기술의 심장인 데이터베이스가 어떻게 동작하는지 궁금하신 분 데이터를 보다 전 opentutorials.org opentutorials.org/course/195/1410 그룹핑 (group by) - 생활코딩 GROUP BY 특정 칼럼을 기준으로 데이터를 그룹핑함 문법 SELECT * FROM..

■ Heap 1) 정의 : 연관된 데이터에서 최대값 / 최소값을 빠르게 찾기 위해 고안된 "완전 이진 트리" ※ 완전이진트리 : 노드 삽입시 최하단 왼쪽 노드부터 차례로 삽입하는 트리 2) 사용 이유 : - array( and python list)에서 배열 길이만큼 index searching시간 소요 O(N) - heap에 데이터를 넣으면 O(log N) 평균시간이 걸림 - 최대 최소를 빠르게 찾아야 하는 경우 유용 ( PS 문제에 최소/최대 이용하여 문제 빠르게 해결하는 경우 있었음 ) 3) 종류 (1) min heap - 정의 : (a) 각 노드의 값은 해당 노드의 자식 값보다 작음 (b) 완전 이진트리 형태를 가짐 - python 기본 heapq library 경우 min heap으로 구성 ■ ..

■ Queue 1) 정의 : First In First Out - FIFO 구조 > 들어가는 곳과 자료가 나오는 부분이 다른 구조 > array( 파이썬에서는 deque library써서 입출력 속도 높여서 사용 ) > queue는 mmutable이라 access 가능하면 변경시 다른 곳에서 참조해도 변경사항이 반영 추가 참조 : ledgku.tistory.com/54 [Python 변수] mutable과 immutable의 차이 [Python 변수] mutable과 immutable의 차이 변수 변수는 객체를 가리킨다. $$ num = 10 $$ 컴퓨터 메모리에 10이라는 값이 저장되고 num은 10이 저장된 메모리의 위치를 가리킨다. 10이라는 정수형 객체를 num이 ledgku.tistory.com..

■ Stack 1) 정의 : First In Last Out - FIFO 구조 > 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 > array로 이루어진 자료구조 사용 2) 대표 활용 : > 컴퓨터 내부 프로세스 , 함수 콜 스택 등에 사용 > PS 중에 동적계획법에 사용되는 경우도 있음 3) 코드 > 재귀함수 stack # 재귀 함수 # 재귀 깊이 설정 import sys sys.setrecursionlimit(10000) # -> 공간 미리 확보해둔 것임!, in the system # 재귀함수는 stack으로 process가 진행된다 def recursive(data): if data < 0: print ("ended") else: print(data) recursive(data - 1) print..