[TIL] 1월 11일

yeon·2021년 1월 11일
1
post-custom-banner

학습한 내용

연결 리스트(Linked List)

블로그 참고하여 내용정리

  • 단열 연결 리스트(singly-linked list)
    • 다음 원소를 가르키는 next 포인터 또는 레퍼런스(연결 링크)
    • 마지막 원소에는 빈 링크 null
    • 연결 링크가 next 포인터로만 구성이 되어있어서 리스트를 한 방향으로만 다룰 수 있다.
    • 반드시 첫번째 원소(head)가 필요하다.
  • 이중 연결 리스트(doubly-linked list)
    • 각 노드별로 다음원소에 대한 링크와 앞 원소에 대한 링크도 있다.
    • 어떤 원소로 시작하던 리스트를 앞, 뒤 양 방향으로 다룰 수 있다.
  • 원형 연결 리스트(circularly-linked list)
    • head나 tail 이 없다.
    • 시작점을 제대로 파악하지 않으면 무한루프에 빠질 수 있다.

Linked list

Linked list - Data Structure (자료구조)

생활코딩 Linked list, Hello coding 알고리즘 책보고 정리함

  • 자료구조의 미션은 메모리의 효율적 사용
  • Linked list에서는 요소를 node, vertex라고 부른다.
  • Linked list 를 사용하면 원소를 메모리의 어느곳에나 둘 수 있다.
  • 흩어져있는 임의의 메모리 주소들이 하나의 목록으로 연결되어 있는 것
  • Linked list의 장점
    • 요소들의 중간에 삽입할 때 용이
    • 삭제할 때 용이
  • Linked list의 문제점
    • 마지막 원소를 보고 싶을 때 바로 읽을 수 없다.
    • 주소를 타고 타고 접근해야한다. → 순차접근
    • 원소에 접근할 때는 배열의 인덱스 접근이 더 용이하다. → 임의접근

Lined list의 구조

  • 노드들의 모임
  • 노드는 노드의 값과 다음 노드에 대한 정보(포인터)를 갖고있다.
  • head
    • 건물의 출입문 같은 것
    • Linked list를 사용하려면 head가 가르키는 첫번째 노드를 찾아야함

빅오 표기법

[자료구조 알고리즘] 빅오(Big-O)표기법 완전정복

출처 : 유튜브 엔지니어대한민국, 이 영상 너무 좋다.

  • 알고리즘의 속도는 시간이 아니라 연산횟수가 어떻게 증가하는지로 측정
  • 원소의 개수가 커질수록 이진탐색의 속도가 단순탐색의 속도보다 훨씬 빨라진다.
  • 이진 탐색은 크기가 n인 리스트를 확인하기 위해서 log n번의 연산이 필요하다. → O(log n)

빅오 표기법의 예

  • O(log n), 로그시간 : 이진탐색
  • O(n), 선형시간 : 단순탐색
  • O(n*log n) : 퀵정렬과 같은 빠른 정렬 알고리즘
  • O(n2n^2) : 선택정렬과 같이 느린 정렬 알고리즘

오늘 한 일

  • 생활코딩 영상과 Hello coding 그림으로 개념을 이해하는 알고리즘 책 보고Linked list, 이진탐색, 빅오표기법 학습
  • 미션 해결 완료

Todo

(내일)

  • 미션 진행한 것 README.md 작성하기
  • 이중 연결 리스트 학습하기

Doubly linked list (이중 연결 리스트) - Data Structure (자료구조)

  • 밑에 블로그 학습하기

알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기

  • 알고리즘 책 보고 복잡도 학습하기
  • 학습정리에 나온 내용 학습하고 정리하기
post-custom-banner

2개의 댓글

comment-user-thumbnail
2021년 1월 11일

벌써 미션 완료 하셨군요 "미션진행한 것 README.md 작성하기"는 나중에서 어디에서 볼 수 있나yeon?

1개의 답글