예니의 코딩일기

강의 Dummy Node 연결 리스트는 삽입과 삭제가 유연하다는 장점이 있습니다. 1. 특정 노드 다음에 삽입하기 2. 특정 노드 다음을 삭제하기 → dummy node 사용하기 class LinkedList: def __init__(self): self.nodeCount = 0 self.head = Node(None)# dummy node self.tail = None self.head.next = self.tail 연결 리스트 연산 1 길이 얻어내기 2. 리스트 순회하기 def traverse(self): result = [] curr = self.head while curr.next:# 따라갈 노드가 존재할 경우 curr = curr.next result.append(curr.data) return..

강의 "연결 리스트"는 선형 배열과 비슷한 구조입니다. 배열 연결 리스트 저장공간 연속한 위치 임의의 위치 특정 원소 지칭 매우 간편 선형탐색과 유사 시간 복잡도 O(1) O(n) 연결 리스트의 Node는 Data와 Link(next)로 이루어져 있습니다. 머리 부분을 Head, 마지막을 Tail이라고 부릅니다. nodeCount를 이용하여 노드의 개수를 지정하면 유용합니다. class Node: def __init__(self, item): self.data = item self.next = None class LinkedList: def __init__(self): self.nodeCount = 0 # 길이 self.head = None self.tail = None 연결 리스트에서의 연산 1. 특정..

강의 "복잡도"는 자원이 얼마나 필요한가를 나타내는 측도입니다. - 시간 복잡도 : 문제의 크기와 해결하는데 걸리는 시간 사이의 관계 - 공간 복잡도 : 문제의 크기와 이를 해결하는데 필요한 메모리 공간 사이의 관계 "시간 복잡도"에는 여러 가지 종류가 존재합니다. - 평균 시간 복잡도 : 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균 - 최약 시간 복잡도 : 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간 복잡도를 표기할 때, 점근 표기법 중에 하나인 "Big-O Notation"을 이용합니다. - 선형 시간 알고리즘 O(n) : 선형 탐색 - 로그 시간 알고리즘 O(log n) : 이진 탐색, 병합 정렬(O(nlog n)) - 이차 시간 알고리즘 O(\(n^2\)) : 삽입 정렬

강의 재귀 알고리즘을 응용할 수 있는 실제 예시를 풀어보았습니다. 1) 조합 : 같은 방법으로 순열이나 팩토리얼 계산도 가능할 것이라고 생각합니다. 2) 하노이의 탑 3) 피보나치 순열 : 재귀적 이진탐색으로 효율성을 높일 수 있습니다. 그러나 f(n)을 구하기 위해 f(n-10)을 여러번 계산해야 하는 부분에서 더욱 좋은 코드를 작성할 수 있을 것이라고 예상합니다. 5강 실습: 재귀적 이진 탐색 구현하기 ⭐ 이진 탐색에 재귀를 추가한 문제! def solution(L, x, l, u): if l > u: return -1 mid = (l + u) // 2 if x == L[mid]: return mid elif x < L[mid]: return solution(L, x, l, mid-1) else: r..

강의 "재귀함수"는 자신을 다시 호출하여 작업을 수행하는 알고리즘입니다. 예시로는 이진 트리와 자연수의 합 구하기가 있습니다. 재귀함수는 종결 조건을 작성하는 것이 매우 중요합니다. 모든 재귀함수는 반복문으로 작성이 가능합니다. 하지만 효율성이 항상 좋다고 할 수는 없습니다. 4강 실습: 피보나치 순열 구현하기 ⭐ 직관적 풀이 : 반복문 이용하는 방법! def solution(x): f = [0] * (x+1) print(f, x) if x == 0: return 0 f[1] = 1 for i in range(2, x+1): f[i] = f[i-2] + f[i-1] return f[-1] ⭐ 힌트 풀이 : 재귀함수 이용하는 방법! def fibo(n): if n == 0 or n == 1: return ..

강의 "정렬" 내장 함수는 2가지 종류가 있습니다. sorted() : 정렬된 새로운 리스트 sort() : 기존의 리스트 정렬 옵션을 이용해 다양한 기준으로 정렬할 수 있습니다. reverse : 역순 원소가 문자열인 경우 사전 순서에 따라 정렬합니다. 원하는 키를 지정하여 정렬의 기준을 설정할 수 있습니다. "탐색" 알고리즘은 선형 탐색과 이진 탐색이 있습니다. 선형 탐색 : O(n) 이진 탐색 : O(log n) 정렬이 되어 있거나 리스트의 크기가 큰 경우에는 선형 탐색보다 이진 탐색이 더 유리합니다. 3강 실습: 이진 탐색 구현해보기 ⭐ 직관적 풀이 : 리스트에 찾으려는 원소가 존재하는지 여부를 우선 확인한 후, index() 함수를 이용하는 방법! def solution(L, x): if x n..