예니의 코딩일기

강의 "양방향 연결 리스트"는 앞뒤 모두 진행 가능한 연결 리스트입니다. 기존의 연결 리스트와 다르게 Node의 구조 확장이 필요합니다. dummy node를 양방향으로 두어 모든 연결 리스트의 형태를 통일화할 수 있습니다. class DoublyLinkedList: def __init__(self): self.nodeCount = 0 self.head = Node(None) self.tail = Node(None) self.head.prev = None self.head.next = self.tail self.tail.prev = self.head self.tail.next = None 10강 실습: (1) 양방향 연결 리스트 역방향 순회 ⭐ 시작 노드를 tail로 설정하여 순회하는 문제! def re..

강의 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 ..