깊은바다거북
개발 공부 기록
깊은바다거북
전체 방문자
오늘
어제
  • 분류 전체보기 (219)
    • JAVA (9)
    • JavaScript (15)
    • 스파르타코딩클럽 (11)
      • [내일배움단] 웹개발 종합반 개발일지 (5)
      • [내일배움캠프] 프로젝트와 트러블 슈팅 (6)
    • SQL | NoSQL (4)
    • CS 등등 (0)
    • TIL | WIL (173)
    • 기타 에러 해결 (3)
    • 내 살 길 궁리 (4)

인기 글

최근 글

최근 댓글

태그

  • 최소 힙(Min Heap)
  • 팀 프로젝트
  • 시간 복잡도
  • POST / GET 요청
  • BST(이진 탐색 트리)
  • Inorder Traversal(중위 순회)
  • TypeScript
  • leetcode-cli
  • 자료 구조
  • Binary Tree(이진 트리)
  • Til
  • 프로그래머스
  • 최대 힙(Max Heap)
  • BFS(너비우선탐색)
  • DFS(깊이우선탐색)
  • 혼자 공부하는 자바스크립트
  • Backtracking(백트래킹)
  • 자잘한 에러 해결
  • 재귀 함수
  • Leetcode
  • 트러블 슈팅 Troubleshooting
  • tree
  • 코딩테스트 연습문제
  • 01. 미니 프로젝트
  • 자바스크립트 기초 문법
  • Trie
  • Linked List
  • Preorder Traversal(전위 순회)
  • 점화식(Recurrence Relation)
  • TIT (Today I Troubleshot)
hELLO · Designed By 정상우.
깊은바다거북

개발 공부 기록

TIL | WIL

11/23 (자료 구조와 탐색, 수) TIL

2022. 11. 23. 21:39

(어제에 이은) 자료 구조:

  • 트리 : 완전 이진 트리의 경우 잎 노드에서 뿌리 노드까지 도달하는 데 O(logN)O(logN)O(logN) 단계가 필요함.
  • 힙 : 최대힙과 최소힙이 있음. 완전 이진 트리의 일종이므로 원소 추가와 삭제시 시간 복잡도는 최대 O(logN)O(logN)O(logN)이 된다.
  • 그래프 : 노드와 노드 사이의 연결 관계를 강조하여 나타낸 자료 구조. 인접 행렬과 인접 리스트로 표현할 수 있음.

트리와 그래프를 탐색하기:

DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색) 모두 인접 리스트를 데이터 삼아 구현을 연습했다. 인접 행렬로 표현한 버전이 연결 관계를 찾을 때 O(1)의 시간만으로 빠르게 찾는다던데, 정작 탐색을 할 때는 어떻게 활용해야 할지 모르겠다.

다이나믹 프로그래밍과 메모이제이션:

내가 이해하기로는 보통의 재귀 함수에 그 때까지의 계산 값을 저장해 둔 메모를 덧붙여서 사용하는 방식을 다이나믹 프로그래밍이라고 하는 것 같다. 그 때까지의 계산 값을 메모해 놓는다고 해서 메모이제이션을 활용한다고 하고.

피보나치 수열처럼 ‘반복되는 형태로 작은 문제가 계속해서 파생된다면’ 다이나믹 프로그래밍으로 풀어야겠다고 생각하면 된다.

하지만 어째서 ‘다이나믹’ 프로그래밍인가? 이 전까지의 프로그래밍은 그럼 정적인 프로그래밍이었다는 말인가? 재귀에 메모이제이션을 덧붙인 어느 부분이 그렇게 다이나믹하다는 걸까..?

강의에 덧붙여 나오는 숙제 문제들이 기하급수적으로 어려워졌다. 세 문제 중 하나를 붙잡고 저녁 전부터 잠자기 직전까지 고민 중이다. 아니 이렇게 논리가 복잡해지는 게 맞는 거야..? 내가 쓴 코드 내일 다시 보면 나도 이해 못할 것 같은데.


Uploaded by N2T

    'TIL | WIL' 카테고리의 다른 글
    • 11/25 (대칭 키와 비대칭 키, 금) TIL
    • 11/24 (재귀 함수와 쪼끔 더 친해진, 목) TIL
    • 11/22 (정렬과 자료 구조, 화) TIL
    • 11/21 (시간 복잡도, 월) TIL
    깊은바다거북
    깊은바다거북

    티스토리툴바