데굴데굴

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 https://www.youtube.com/watch?v=Lqd8o7vL2Z8&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=6 배열 (array) vs. 리스트(list) 파이썬 - 가장 기본적인 순차적인(sequential) 자료구조 C언어의 배열 A[2] = A[2] + 1은 기본연산만 포함하기 때문에 O(1) A[2]의 주소: RAM A[0] 주소 + 2 * 4bytes 100 + 8 = 108 배열은 읽기와 쓰기를 연산으로 제공. 기본시간 내에 다 수행할 수 있다. 파이썬의 리스트 A = [2, 4, 0, 5] 결정적인 차이: 객체가 다른 메모리에 저장됨 A[2] = A[2] + 1 0이 1로 바뀌는 것이 ..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 (주요 알고리즘 배울 때마다 슈퍼마리오 블로그 정독할 것!) [강의 주요 내용] 알고리즘의 수행시간을 함수로 표현 다항식의 성질에 따라서 수행시간이 어떻게 변화하는가 수행시간을 표기하는 간단한 방법 함수로 표현하여 그래프를 그림. Algorithm2가 Algorithm1보다 2배 느리다. True Algorithm3 n5/3면 항상 Algorithm2보다 느리다. T1(n), T2(n), T3(n) 앞의 두 개는 n값에 따라 선형적으로 증가하는 반면, T3(n)은 제곱으로 증가함. (최고차항이 n제곱) n이 증가함에 따라 얼마만큼 빠른 속도로 기본연산 횟수가 증가하는가는 최고차항이 결정함. 모든 함수를 다 분석해서 표현하기보다는 최고차항만 표시하면 수..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 알고리즘의 시간복잡도를 어떻게 측정하는가? algorithm ArrayMax(A,n): # 지금부터 ArrayMax라는 가상의 코드를 기술하겠다 input: n개의 정수를 받는 배열 A output: A의 수 중에서 최대값 리턴 currentMax = A[0] for i=1 to n-1 do if currentMax 현실적으로 불가능 (고려해야 할 입력이 무한히 많기 때문) 가장 안 좋은 입력(worstcase input, 기본연산을 가장 많이 요구하는 입력)에 대한 기본..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 자료구조 + 알고리즘 --> [[[코드(C, java, Python)] 컴퓨터] HW/SW 환경 상이] 또한, 다양한 크기의 입력이 존재함. 알고리즘별로 빠르고 느린 입력이 다르다. Q. 내가 작성한 코드가 얼마나 빨리 동작하는가를 객관적으로 어떻게 측정하는가? - 가상컴퓨터 (Virtual Machine) + 가상언어 (Pseudo language) + 가상코드 (Pseudo Code) --> 누구나 같은 환경에서 여러 알고리즘을 객관적으로 비교할 수 있게 됨. 1. 가상컴퓨터 Turing Machine -> von Neumann: RAM(Random Access Machine) RAM = CPU + Memory (CPU의 계산 수행, 메모리에는 프..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 자료구조 자료: data 저장공간(memory) 에 저장된 데이터를 읽고 쓰고 삽입하고 삭제하고 탐색할 수 있어야 함. --> 연산이 가능해야 함. 지원되는 연산에 따라서 다양한 자료구조 존재 알고리즘: 입력을 가지고 유한한 횟수의 연산들을 반복해서 정답을 출력하는 것 자료구조 예시 1. 변수 - 파이썬에서 a=5는 a 그 자체가 5라는 것을 의미하지 않음. 5라는 값의 주소가 a라는 것을 뜻함. 객체 2. 배열 - 파이썬에서는 리스트가 배열의 역할을 하기도 함. 접근은 각 원소의 인덱스로. 읽기와 쓰기는 A[n]. 새로운 값 추가하려면 A.append(n). 삭제하려면 A.pop() 매개변수가 없으면 가장 뒤에 있는 값을 리턴해서 없앰. 알고리즘 인..