💿 Data

[TIL] 100. [알고리즘] 탐색

키워드 탐색 선형탐색 이진탐색 [알고리즘] 탐색 자료를 하나씩 탐색하는 알고리즘 문제를 해결하기 위해서는 문제를 탐색해야한다. [탐색] 선형탐색(Linear Search) 기본적인 탐색 알고리즘으로 한번에 하나씩 차근차근 모두 검색하는 것 def linear_search(arr, value): for i in range(len(arr)): if arr[i] == value: return i [탐색] 이진탐색(Binary Search) 탐색을 할 때, 반씩 줄여나가면서 탐색 마치 업다운 게임에서 가운데 값을 말하면 점점 좁혀나가는 방식 단, 데이터가 이미 정렬된 경우에만 작동한다. O(logn)의 시간복잡도를 갖는다.(그룹을 2개씩 나누면서 진행하기 때문) def binary_search(arr, valu..

[TIL] 99. [알고리즘] 정렬

키워드 알고리즘 정렬 버블정렬 삽입정렬 선택정렬 알고리즘 구구단을 예시로 든다면 구구단의 숫자들은 자료구조, 곱셈은 알고리즘에 해당 즉, 자료구조는 기반, 알고리즘은 방법 [알고리즘] 정렬 말 그대로 자료들을 일정한 규칙에 맞게 정리하는 알고리즘(보통은 오름차순) [정렬] 버블정렬(Bubble Sort) 오른쪽부터 정렬되며 마치 거품이 올라오는 모양 서로 이웃한 두 원소 크기를 비교하고 교환을 반복 정렬 알고리즘 중 가장 간단한 알고리즘이며 사실상 가장 비효율적인 알고리즘 1번째 항목과 2번째 비교 후 1번째가 더 크면 항목 교체 2번째, 3번째 ~ 쭉 1번처럼 반복 (한번의 사이클을 마치면 가장 끝에는 가장 큰 값이 위치하게 됨. 따라서 가장 끝단은 더 안봐도 괜찮다.) 한 사이클을 돌고나면 마지막에 ..

[TIL] 98. [자료구조] 트리

키워드 비선형 구조 이진트리 이진탐색트리 편향이진트리 [자료구조] 트리 루트(root) : 트리의 가장 위쪽에 있는 노드, 1개만 존재 리프(leaf) : 트리의 가장 아랫단에 있는 노드(가장 끝자락) 서브트리(sub tree) : 큰 트리에서 작은 트리를 쪼개서 보는 것(자식노드이면서 부모역할을 하는 노드가 있는 트리) 차수 : 노드가 갖고 있는 최대 자식 노드 수 레벨 : 루트 노드를 0으로, 아래로 한단계씩 +1 높이 : 제일 끝단 노드의 레벨과 루트 노트 레벨의 차이 형제 노드(sibling) : 부모가 같은 노드 [트리] 이진트리 각 노드 별로, 최대 2개의 서브노드를 가질 수 있음(left와 right) 트리 중 가장 기본이면서 가장 많이 활용 포화이진트리 : 모든 리프노드들이 동일한 레벨을 ..

[TIL] 97. 재귀(Recursion)

키워드 수학적 사고 재호출 로직 재귀 호출 -> 스택의 개념(함수 내부) 베이스 케이스 추가 조건 재귀(Recursion) 자기 자신을 재호출 하는 것, 종료 조건이 충족될 때까지 반복 수행 문제를 해결하는 재호출 로직 기억(추가 조건) 재귀함수를 멈추는 base case(반복을 중지하는 조건) 하위 문제를 쉽게 해결할 수 있을 때까지 더 작은 하위 문제로 나누는 것 재귀 예시 def sum_list(items): if len(items) == 1: return items[0] # base case -> 재귀함수 종료 else: return items[0] + sum_list(items[1:]) # 추가 조건 -> 재호출 로직 [재귀] 조건 base case(기본 케이스)가 있어야 한다. 추가 조건을 두..

[TIL] 96. 추상 자료형(Abstract Data Type ; ADT)

키워드 ADT(추상자료형) 연결리스트 스택/큐 추상자료형(ADT) 파이썬에는 기본 자료형인 숫자, 문자열, 리스트, 딕셔너리 등이 존재 ADT는 기본 자료형처럼 로직이 구성되어있는 자료가 아닌 필요한 기능만 사용자가 직접 구현한 로직 추상화 : 소프트웨어가 발전함에 따라 프로그램의 크기나 복잡도가 증가하였고 이런 부분을 간단하게 핵심만 설명하는 것 연결리스트(Linked-list) 연결리스트는 각 노드가 1. 본인의 값, 2. 다음 노드에 대한 정보 를 담고 있다. 데이터를 읽을 때는 헤드 노드부터 순차적으로 거쳐야하기 때문에 배열보다 시간복잡도가 크지만 데이터를 추가/제거할 때, 노드 사이의 링크만 바꿔주면 되기 때문에 더 빠르다.(연결리스트의 장점) 단방향, 양방향, 환형 연결리스트가 존재 배열과 달..