Breath everything

이것 저것

IT/자료구조 & 알고리즘

1. 시간 복잡도(Time Complexity) -> 알고리즘 실행 속도 -> 가장 영향을 많이 미치는 요소는 반복문 -> 상수는 큰 영향을 주지 못함 (Big O 표기법) 가장 일반적으로 사용 알고리즘의 최악의 실행 시간을 나타냄 입력 n에 따라 몇 번 실행되는지를 계산 O(1): 데이터가 증가함에 따라 성능에 변화가 없을 때 ex) 조건문 O(n): n에 따라 n번, n+50번 등 실행 ex) 반복문 1개 O(n^2): n에 따라 n^2번, n^2+3n+1번 등 실행 ex) 반복문 2개 O(logn): 한번 처리가 진행될 때마다 검색해야 하는 데이터 양이 절반씩 줄어듦 ex) binary search O(nlogn): 여러 작은 부분으로 쪼개서 각각 해결한 후 마지막에 각각의 부분들을 모으는 경우 e..

2021. 7. 30.

IT/자료구조 & 알고리즘

1. 기본 원리 데이터를 왼쪽부터 오른쪽에 있는 값을 하나씩 추가하면서 확장해나간다. 확장할 때마다 오른쪽에서 들어온 값들을 사이사이에 넣어보면서 정렬을 맞춰나간다. ex) a = [5,1,2,3]이면 1. [5,1] 범위에서 1을 5와 비교하여 [1,5]로 정렬 2. [1,5,2] 범위에서 2를 5,1과 비교하여 [1,2,5]로 정렬 3. [1,2,5,3] 범위에서 3을 5,2,1과 비교하여 [1,2,3,5]로 정렬 2. 코드 구현 전 생각정리 어느 범위까지 정렬 처리가 완료되었는지를 나타내는 좌표를 변수에 저장해야 하나? 왼쪽에서부터 점점 확장해나가는 범위? 는 이미 정렬이 되어있음을 명심 3. 코드 구현 def insertion(input): for i in range(len(input)-1): i..

2021. 7. 29.

IT/자료구조 & 알고리즘

1. 기본 원리 전부를 한번 훑을 때마다 최솟값을 구한 뒤, 맨 앞의 데이터와 swap 해주는 방식 2. 코드 구현 전 생각정리 n번 훑을 때마다 n개의 데이터들이 앞에서부터 fix되네? 반복문을 짤 때 이 부분을 생각하며 짜야겠네? 3. 코드 구현 def selection(input): for i in range(len(input)): min_idx = i for j in range(i,len(input)): if input[j]

2021. 7. 29.

IT/자료구조 & 알고리즘

1. 기본 원리 두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, swap 해주는 원리 결국 처음부터 끝까지 한번 훑으면 맨 마지막에 가장 큰 값이 위치하게 됨 2. 코드 구현 전 생각정리 그럼 한번 훑을 때 마다 정렬된 데이터가 끝부터 하나씩 쌓이게 되네? 반복문을 짜되, 이미 정렬이 된 부분은 이후에 훑지 않아도 되네? 3. 코드 구현 def bubble(input): for i in range(len(input)-1): for j in range(0,len(input)-1-i): if input[j]>=input[j+1]: input[j],input[j+1] = input[j+1],input[j] return input 4. 시간 복잡도 이중 for문이 있으므로 O(n^2)

2021. 7. 29.

IT/자료구조 & 알고리즘

1. 정의 -최댓값과 최솟값을 빠르게 찾기 위해 만들어진 완전 이진트리(complete Binary Tree) #완전 이진트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 -종류에는 최대 힙과 최소 힙이 있음 2. 사용하는 이유 -최댓값과 최솟값을 빠르게 찾기 위해서 -최댓값 최솟값을 찾을 때 배열을 사용하면 -> 시간 복잡도 O(n) 힙을 사용하면 -> 시간 복잡도 O(logn) 3. 구조 -완전 이진 트리 형태 -각 노드의 값이 해당 노드의 자식 노드의 값보다 크거나 같다(최대 힙) -> 최댓값이 rootnode에 담김 -각 노드의 값이 해당 노드의 자식 노드의 값보다 작거나 같다(최소 힙) -> 최솟값이 rootnode에 담김 4. Pyhon 모듈 #기본적으로 최소 힙 기능으로 ..

2021. 7. 29.

IT/자료구조 & 알고리즘

1. 기본 구조와 용어 트리(Tree): Node와 Branch를 이용하여, 사이클을 이루지 않도록 구성한 데이터 구조 노드(Node): 트리에서 데이터를 저장하는 기본 요소로, Branch 정보 또한 포함 간선(Edge): 노드와 노드를 연결하는 연결선 Root Node: 트리 맨 위의 노드 Leaf Node: Child Node가 하나도 없는 노드 Depth: 트리에서 Node가 가질 수 있는 최대 Level 2. 이진 탐색 트리(Binary Search Tree) 이진 트리에 추가적인 조건이 있는 트리 (왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값) 3. Python Linked list로 간단한 Binary Seach Tree 구현 Python class를 통해 Lin..

2021. 7. 29.

IT/자료구조 & 알고리즘

1. 기본구조와 용어 해쉬 테이블(Hash Table): Key에 Value를 저장하는 데이터 구조 ## 탐색을 할 때 키값을 통해 바로 데이터를 찾을 수 있으므로 탐색 속도가 빠름 ## 키값 입력 -> 해싱 함수 연산을 통해 해시 주소를 알아냄 -> 해시 주소를 통해 저장되어 있는 주소를 찾아냄 ## Python에서는 Dictionary 타입을 사용하면 된다! 해쉬(Hash): 임의 값을 고정 길이로 변환 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해쉬 값(Hash Value) or 해쉬 주소(Hash Address): Key값을 통해 알아낼 수 있는 찾으려는 데이터가 있는 주소 해싱 함수(Hashing Function): Key에 대해 산술연산을 하여 데..

2021. 7. 28.

IT/자료구조 & 알고리즘

1. 기본 구조와 용어 - 노드: 데이터 저장 단위(데이터, 포인터) - 포인터: 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 #파이썬에서는 list타입이 linked list의 기능을 모두 지원합니다. 2. 장점 - 배열의 단점인 '미리 연결된 공간을 예약해야 하는 점'을 해결할 수 있다. - 필요할 때마다 데이터를 추가할 수 있다. - 메모리 관리가 용이하다. 3. 단점 -배열의 장점인 index를 통한 탐색이 불가능하다. 4. Python으로 구현 class Node: def __init__(self, data, next=None): self.data = data self.next = next class NodeMgmt: def __init__(self, data): self.head =..

2021. 7. 28.

IT/자료구조 & 알고리즘

한국어로는 탐욕 알고리즘입니다. 현재 주어진 조건에서 가장 최적해를 구하는 데에 사용되는 '근사적 방법'입니다. 예제 ) 곱하기 혹은 더하기 근사적인 접근 : -> '보통' (근접해있는 두 수가 0 or 1인 경우)를 제외하면 +보다 *를 선택하는 것이 값을 더 크게 만든다. 예제 2) 모험가 길드 근사적인 접근 : -> 주어진 조건을 다 따르면서 최대한 많은 그룹을 만들어 줘야 한다. -> 오름차순으로 정렬 후, 하나씩 앞으로 가면서 작은 값들부터 나눠준다.

2021. 2. 3.