💿 Data/부트캠프

[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. 다음 노드에 대한 정보 를 담고 있다. 데이터를 읽을 때는 헤드 노드부터 순차적으로 거쳐야하기 때문에 배열보다 시간복잡도가 크지만 데이터를 추가/제거할 때, 노드 사이의 링크만 바꿔주면 되기 때문에 더 빠르다.(연결리스트의 장점) 단방향, 양방향, 환형 연결리스트가 존재 배열과 달..

[TIL] 95. python 자료구조 및 알고리즘 기본

키워드 자료구조 알고리즘 복잡도, Big O 자료구조 데이터를 효율적으로 관리하기 위한 다양한 구조 자료구조를 체계적으로 정립하기 위해 프로그래밍 언어별로 다양한 자료형이 발생 그 중 가장 기본적인 형태로 배열이 등장하였고, 파이썬에서는 리스트와 튜플을 통해 배열을 구현 [자료구조] 리스트(in python) 파이썬에서의 리스트는 배열과 연결리스트의 특징을 모두 갖고 있음 일반적인 자료구조의 배열 : 인덱스를 통해 노드에 접근 가능 연결리스트 : 인덱스의 크기를 자유롭게 확장 가능, 서로 다른 자료형을 가질 수 있음 알고리즘 컴퓨터에 내리는 명령의 절차 처리의 대상이 되는 것은 입력값 데이터 데이터가 메모리에 저장된 후 사용(변수, 함수, 클래스 등에 객체로 저장) 복잡도 공간 복잡도 : 얼마나 많은 저..