연결리스트란? 연결리스트의 기본구조 - Node: 데이터 + 다음 데이터를 가리키는 주소. 기본 단위 - Pointer: 각 노드에서 다음 데이터를 가리키는 주소값을 저장 - Head: 시작점의 데이터 - Tail: 마지막 데이터 - Next: 다음 데이터. 없을 경우 Null값을 가진다. 연결리스트의 특징(C언어에 해당) 장점: - 미리 데이터 공간을 할당할 필요가 없다. - 유동적으로 데이터 삽입, 삭제 가능. (가리키는 주소값을 자신으로 하면 됨.) - 수정 시 시간복잡도 O(1). 단점: - 각 노드에 별도로 주소 공간을 가져야 함. (저장공간 효율이 떨어짐) - 데이터를 찾는데 시간이 오래걸림. (하나씩 타고 가야 하기 때문) 단방향 연결리스트 삽입: E라는 노드가 있을 경우, A의 Next값으..
큐란? -> 먼저 넣은 데이터가 먼저 나가는 구조이다. -> 놀이동산 줄서기를 생각하면 편하다. 먼저 기다린 사람이 먼저 탑승하는 구조. from collections import deque queue = deque() queue.append(3) # [3] queue.append(5) # [3, 5] queue.append(2) # [3, 5, 2] queue.popleft() # [5, 2] queue.append(8) # [5, 2, 8] queue.popleft() # [2, 8]
스택이란? -> 마지막에 넣은 데이터를 가장 먼저 빼는 구조이다. LIFO(Last-In First-Out)방식이다. 스택의 특징 장점: 구조가 단순하고 구현이 쉽다. 데이터 저장, 불러오는 속도가 빠르다. 단점: 데이터의 최대 개수를 미리 정해주어야 한다. 저장공간의 낭비가 발생할 수 있다. (미리 최대 개수를 지정하기 때문) -> 단점때문에 보통 배열로 대체하여 사용한다. stack = [] stack.append(3) # [3] stack.append(6) # [3, 6] stack.append(4) # [3, 6, 4] stack.pop() # [3, 6] stack.append(7) # [3, 6, 7] stack.pop() # [3, 6]
배열이란? -> 같은 종류의 데이터를 순차적으로 저장하는 자료구조 배열의 특징 -> index를 통해 직접 접근이 가능하다. 장점: 빠른 접근이 가능하다. 조회 시간복잡도 O(1) 단점: 데이터 추가와 삭제에 비용이 많이 든다. 데이터 추가 시 공간이 많이 필요하며, 삭제 시 빈 공간이 생겨 이를 관리해주어야 한다. 길이 조절이 어렵다. (C나 C++의 경우에만 해당) arr = [1, 2, 3, 4, 5] # index 접근(0부터 카운트) print(arr[2]) # 3 # 배열의 길이 출력 print(len(arr)) # 5 # 삽입(맨 끝) arr.append(6) # [1, 2, 3, 4, 5, 6] print(arr) # 삽입(인덱스, 값) arr.insert(1, 9) # [1, 9, 2, ..
재귀 함수란? 재귀 함수: 함수 안의 함수, 한 함수를 호출했을 때 그 안에 있는 함수를 다시 호출하는 형태의 함수 -> 탈출 조건을 명시하지 않으면 무한 반복함. 예) 팩토리얼 함수 def factorial(n): if n == 0: return 1 return n * factorial(n - 1) print(factorial(5))
O(1): 상수 시간 -> N의 값에 관계없이 동일한 숫자의 스텝이 필요한 시간복잡도 print(2) O(logN): 로그 시간 -> 각 단계에서 입력 데이터의 크기를 (반으로) 줄일 때 -> 예) 퀵 정렬 arr = [3, 6, 7, 2, 5, 8, 1, 4, 9, 0] def quick_sort(arr): if len(arr) 실행 시간이 입력 데이터와 정비례하고 선형적으로 증가할 때 -> 예) 일반적인 for문 1회 for i in range(30): print(i) O(nlogN): 선형 로그 시간 -> 예) 합병 정렬 O(N^2): 2차 시간 -> 선형 시간 안의 선형 시간 -> 예) 2중 for문 for i in range(30): for j in range(40): print(i, j) O(..
자료구조와 알고리즘의 정의 자료구조: 저장공간 + 연산(읽기, 쓰기, 삽입, 삭제, 탐색) -> 데이터를 표현하는 구조 -> 대량의 데이터를 효율적으로 관리할 수 있도록 하는 데이터의 구조 -> 표현을 하기 위해서는 먼저 저장을 해야한다. 알고리즘: 자료구조를 이용해 입력과 출력 -> 데이터를 처리하는 것 자료구조의 분류
