[자료구조] 1.2 계산모델

JourniYoon·2022년 8월 9일
0

오늘의 용어 정리

  • word: 메모리에서 레지스터로 데이터를 옮기거나, ALU를 통해 데이터를 조작할 때, 하나의 명령어로 실행될 수 있는 데이터 처리 단위를 말한다. 64비트 CPU라면 워드는 64비트가 된다.
  • 상수시간: 알고리즘 실행 시간이 입력 자료의 크기에 관계없이 일정할 때의 연산 시간을 말한다.
  • 선형시간: 알고리즘 실행 시간이 입력 자료의 크기에 비례하는 연산 시간을 말한다.

알고리즘이란?

알고리즘: 컴퓨터 프로그램의 수학적 추상화, 문제 해결을 위한 계산 과정

임의 접근 머신

출처: 수업 자료

아주 큰 '배열'을 생각하면 쉽다.
RAM(Random Access Memory)와 이름이 같아서 헷갈릴 수 있으나 접근 방식이 비슷하다.
배열 안에 주소값이 잔뜩 들어있고 그 주소에 데이터가 저장되는 방식이다.

포인터 머신

https://www.programiz.com/dsa/doubly-linked-list

'Linked List'를 생각하면 쉽다. 동적으로 할당된 객체 안에 data, prev(이전 노드의 주소), next(다음 노드의 주소)가 들어있는 형태다. 사실 위에 모델은 'Doubly Linked List' 이고, 다음과 같이 data, next(다음 노드의 주소)로 이루어진 기본 형태가 'Liked List'이다.

https://www.programiz.com/dsa/linked-list

파이썬 모델

  1. 리스트는 사실 배열이다. => RAM으로 접근
    L[i] = L[j] + 5 => O(1) 시간
  2. O(1)개의 속성을 가진 객체 => 포인터 머신으로 접근

문서거리(Documents Distance Problem)

모르는 개념이 많아 우선 알고리즘만 적어두자면

  1. 각 문서를 단어들로 쪼갠다.
  2. 단어 빈도를 센다.(이때 해시테이블 개념이 사용된다.)
  3. 내적을 계산한다.(& 나눈다.)

0개의 댓글