2019년 혁신성장 청년인재 집중양성(빅데이터)/[UDACUTY] Data Structures & Algorithms (7) 썸네일형 리스트형 Lesson 8 : Technical Interviewing Techniques 1. 레알 인터뷰 연습이다. 나에게 지금은 별 필요는 없을 것 같지만, 코스의 일부기도 하고, 전체 리뷰도 가능하니.. 1. 문제를 분명히 하는 것이 소프트웨어 개발자에게는 중요하다. 코드 부터 쓰지 말고 문제를 분명히하고 코드로 문제를 푼다. 2. 문제는 1과 0으로 2 D 행렬에 있는 섬의 갯수를 새는 것이다. 이때의 섬은 1이거나, 1의 집합이다. 그리고 섬은 수평이나 수직으로 연결 될 떄만 인정 된다. 1. 문제를 확인 한 이후엔, 인풋과 아웃풋에 대해서 확인을 해야한다. 2. 2차원 행렬이 인풋이고, 섬의 갯수가 아웃풋이다. 1. 가능한 이상한 인풋(null이나 empty)에 대해서 집고 넘어가야 한다. 1. 면접관을 네편으로 만들어서 힌트를 얻어라. 2. DFS나 BFS를 사용함으로써, 얼마나.. Lesson 7 : Case studies in Algorithms 1. 많은 것을 배웠지만, 많은 것을 까먹었다고 합니다... 이래서 복습이 중요합니다. 2. 근본 문제에 대한 분명한 이해를 해야 합니다. 1. 가장 짧은 길을 찾는 문제는 그래프에서 가장 짧은 path를 찾는 것과 같은 문제이다. 2. 그래프의 타입에 따라 이 path를 계산하는 방식에는 차이가 있다. 가중치 그래프라면 가중치를 계산해야 하지만, 그렇지 않다면 엣지의 수를 계산해야 한다. 3. 비가중치 그래프는 BFS(Breath First Search)와 같다. 1. Weighted undirected graph일 때, Shortest path를 차즌 문제를 Dijkstra's Algorithm이라고 부른다. 2. 이때 모든 엣지에 ditance value를 주게 된다. 3. 그리고 distance는.. lesson 6: Graph 1. 이곳에서 말하는 그래프는 위의 그림과 같다. 2. 그래프의 목적은 얼마나 다른 것들이 연결되어 있는 지 보여주는 것이며, 네트워크라고 부르기도 한다. 1. 트리구조와 비슷하며, 연결의 대상이 되는 것을 노드(Node) 또는 Vertex라고 부르며 연결을 edge라고 한다. 2, 사실 트리는 그래프의 형태 중 하나이다. 마치 바이너리 트리가 트리의 중 하나이고, BST가 바이너리 트리의 하나인 것처럼 말이다. 1. 노드 뿐만 아니라 엣지도 연결의 강도와 같은 정보를 포함할 수 있다. 1. 그래프는 데이터 모델링을 위한 부가적인 특성들이 있다. 2. 엣지는 방향을 가지고 있으며, 이 방향은 두 노드 사이의 관계가 일방적임을 의미한다. 1. 만남을 표시할 때 처럼, 방향이 필요가 없는 모델은 언디렉티드 .. Lesson4 Maps and Hashing 1. map은 일종의 Key-Value 구조이다. Key로 찾고, Value에 값을 저장한다. 2. Set은 List와 비슷하지만 조금 다르다. Set은 리스트와 다르게 순서가 없으며, 중복을 허용하지 않는다. 2-2. Key는 유일해야한다. Definition은 여러가지일 수도 있어도 말이다. 즉 키는 맵 상에서 유일하다. 3. 이제까지는 어떤 아이템을 찾는데, 모든 아이템을 다 뒤져봐야 했기 때문에 시간은 아이템 수에 비례해서 증가하였다. 3-2. Constant time look-up은 당신의 작업을 엄청나게 빠르게 해줄 것이다. Hash Function을 사용하세요! 4. 해쉬 퐁션의 목적은 값을 쉽게 저장 되며 불러올 수 있는 값으로 변환하는 것이다. 4-2. Hash Function의 특징 중.. Lesson 3: Searching and Sorting 1. Binary Search의 예를 들어, 알고리즘이 무엇인가에 대해서 설명했다. 알고리즘이란 문제를 풀기 위한 트릭의 높은 수준의 묘사이다. 2. 바이너리 서치의 효율성: 우리가 공부하고 있는 것은 알고리즘의 효율성에 관한 문제다. 어떤 알고리즘이 얼마 효율 적인가에 대해 알기 위해서는, 얼마나 반복되고 있는가에 대해서 알아야 한다. 2-1. Binary Search의 효율성은 O(logN)이라고 외우고 있는 방법이 가장 똑똑한 방법이긴 하지만, 알지 못하는 알고리즘이 나왔다면 증명을 해야 한다. 이 증명을 위해서 표를 그리고, 최악의 경우를 생각해보자. 반을 가르고, 왼쪽을 본다고 가정할 때, 현재 비교해야 하는 어레이의 값보다 큰 하나를 정하고 반복을 진행해본다. 2-2. 예를 들어 어레이 사이즈.. list-based collection 1. 콜렉션(Collection)은 어떤 것들의 집합이다. 2. 리스트(List)는 콜렉션의 확장이다. 리스트에는 순서가 있다. 언어의 종류에 따라서 리스트는 핵심 기능을 담당한다. 3. 리스트에는 순서가 있다. 4. 배열(Array)는 인덱스가 있는 콜렉션이다. 인덱스는 일종의 태그다. 배열은 생성 될 때 그 사이즈가 결정된다. 배열에서도 배열에 변형을 가할 때, 주위 인덱스에 영향을 준다면, 변형하는 요소 외에도 큰 영향을 주게되어 자원이 많이 소모된다. 4-1. 예를 들면, 리스트에 어떤 요소를 삽입하는 것은 상수 배로 일어나기 때문에 쉽다. 하지만 어레이로 삽입하는 것은 O(n)의 시간이 소요된다. 왜냐하면 삽입하려는 하나의 요소로 인하여 다른 요소들을 움직여야 하거나, 공간이 모자라다면 새로운 .. INTRODUCTION AND EFFICIENCY 1. 데이터의 구조와 알고리즘 목차 : ...더보기 Introduction and Efficiency Course Introduction Syntax Efficiency Notation of Efficiency List-Based Collections Lists/Arrays Linked Lists Stacks Queues Searching and Sorting Binary Search Recursion Bubble Sort Merge Sort Quick Sort Maps and Hashing Maps Hashing Collisions Hashing Conventions Trees Trees Tree Traversal Binary Trees Binary Search Trees Heaps Self-Balan.. 이전 1 다음
