Algorithm Study (9) 썸네일형 리스트형 [파이썬 알고리즘 인터뷰] 4장 - 빅오, 자료형 다음은 의 4장 내용을 요약한 것입니다. 빅 오(big-O) 점근적 실행 시간을 표기할 때 쓰이는 수학적 표기법 중 하나. 점근적 실행 시간: 입력값 $n$이 커질 때, 즉 $lim_{n\rightarrow \infty}$ 함수의 실행 시간의 추이를 의미한다. 시간 복잡도(Time Complexity) : 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도, 이 계산 복잡도를 표기하는 대표적인 방법이 빅오! 대표적인 빅오 표기법의 종류 : $O(1)$ 입력값이 아무리 커도 실행 시간은 일정함. 해시 테이블의 조회 및 삽입이 이에 해당한다. $O(log n)$ 로그는 매우 큰 입력값에도 크게 영향 받지 않으므로 매우 견고함. 이진 검색이 이에 해당 $O(n)$ 알고리즘 수행 시간이 입력값에 비.. 데이터 구조 및 분석 : Recursions & Dynamic Programming 본 게시글은 Edwith 문일철 교수님의 데이터 구조 및 분석: Linear Structure and Dynamic Programming을 듣고 정리한 내용입니다. 1. Recursions (재귀호출) Idea Repeating problem ex) 예산이 600만원 있을 때, 전체 예산 기획 과정과 그 하위 부서의 예산 기획 과정은 동일한 문제일 것. => 큰 하나의 문제가 정의되면, 그 문제를 쪼개 반복되는 또 다른 문제로 만든다는 것. Divide and Conquer : 문제를 잘게 쪼개어서 해결하는 과정 Examples) (1) Factorial : $$ Factorial(n) = \left\{\begin{matrix}1 & \textrm{if } n = 0 \\ n \times (n-1) \t.. 데이터 구조 및 분석 : Linked List 본 게시글은 Edwith 문일철 교수님의 데이터 구조 및 분석: Linear Structure and Dynamic Programming을 듣고 정리한 내용입니다. 1. Linked List 한줄 요약 : array와 다르게 index가 아닌 reference 구조로 동작해 중간의 공간을 만들어 낼 수 있음. ==와 is 차이를 구분해야 함. == : 값의 일치를 확인함. (values are equivalent) is : 두 object의 reference link를 확인함. 같은 곳에 저장되어있는가 (values are stored at the same place) 2. Basic Structure : Singly linked list Singly linked list는 node와 reference로.. 데이터 구조 및 분석 : Abstract Data Types & List(Array) 본 게시글은 Edwith 문일철 교수님의 데이터 구조 및 분석: Linear Structure and Dynamic Programming을 듣고 정리한 내용입니다. 토픽 : Data Structures - Linked list, stack, and que. 특히 Singly linked list, 이를 이용하면 stack과 que를 만들 수 있음. 1. Array for List Idea) 군중들 속에서 Koh라는 사람을 찾는다고 하자. 순서없이 물어본다면 비효율적일 것임. 가장 현실적으로 할 수 있는 것은 line을 세워 찾을 수 있을것임. 즉, 사람들을 일렬로 세운다는 것은 list임. 2. Abstract Data Types An abstract data type(ADT) : data structu.. 데이터 구조 및 분석 : UML notation & Structure and Relationship 본 게시글은 Edwith 문일철 교수님의 데이터 구조 및 분석: Linear Structure and Dynamic Programming을 듣고 정리한 내용입니다. More About UML Notations : class를 어떻게 하면 잘 설계할 수 있을까? 현실에서는 다양한 UML diagram들이 있다. use-case, class, state, deployment diagram 등이 존재. OOP (Object-Oriented Programming) 이외에도 다양한 설계 문서들이 있다! Person : Abstract Class(속에 abstract method가 존재.) -> Customer(instantiation) : 위 Person을 상속받아, method를 override해서 사용됨. -.. 데이터 구조 및 분석 : Polymorphism & Abstract Class 본 게시글은 Edwith 문일철 교수님의 데이터 구조 및 분석: Linear Structure and Dynamic Programming을 듣고 정리한 내용입니다. Polymorphism이란? poly : Many Morph : Shape => 다양한 모양이다. 즉, 다른 행동이 일어난다. 유사한 시그니처를 가지고 있지만 완전히 다른 행동을 할 때 Polymorphism이 적용된다고 함. Signature = Method name + parameter list 사람으로 치면 Sign, 이 Signature로 구분할 수 있다는 의미 Method Overriding Sub1) 상속받고 있는 Base class (parent)가 method A(num)을 가지고 있고, 이것의 자식 Class(Child)가 m.. 데이터 구조 및 분석 : Object-oriented paradigm and Software design 본 게시글은 Edwith 문일철 교수님의 데이터 구조 및 분석: Linear Structure and Dynamic Programming을 듣고 정리한 내용입니다. 1. Program을 설계하는 방법. - 좋은 소프트웨어 설계란? Correctness : 개발 목적에 맞아야 한다. + 에러없이 Robustness : 예상되는 overload, 잘못된 입력, 습관에 대해선 잘 동작. Flexibility : 시간이 지나 변경해야 할 경우 유연하게 미래의 수정을 반영할 수 있어야 함. Usability and Reusability : Designed purpose에 대해 좋은 지원. 인터페이스 등 / 다른 목적, 다른 환경에서도 맞춰 쓸 수 있도록 설계 Efficiency : 1. 빠르게 실행되며 작은 사이.. 데이터 구조 및 분석 : Python 기초 요약 (1) 본 게시글은 Edwith 문일철 교수님의 데이터 구조 및 분석: Linear Structure and Dynamic Programming을 듣고 정리한 내용입니다. 1. Python이란? interpreter 언어 (반대 : compiler) 최적화되지 않아도 되니 프로그램이 그때그때 실행될 수 있도록 하는 언어 Object-oriented Dynamic type of variables 많은 컴파일 언어들은 Dynamic 이 아니라 변수의 형을 함께 선언. 그때그때 타입이 변할 수 있도록 지원. Unique code structure 코드 규칙이 잘 정의되어있음. 2. List, Tuple, Dictionary List - lst = [1, 2, 3, 4] , 대괄호에 정의. - lst + lst = [.. 이전 1 2 다음
