오늘의 공부/자료구조와 알고리즘 (6) 썸네일형 리스트형 DP 는 아직도 너무 어렵다. 서울에서 경산까지 https://programmers.co.kr/learn/courses/30/lessons/42899 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr dp 테이블을 무엇을 기준으로 만들어야 하는지, 인덱스는 어떻게 잡는지가 어렵다. 처음에 나는 walk table, bike table만 만들었다. 즉 들른 도시의 수를 인덱스로 잡으려고 한 것이다. 도시를 인덱스로 잡은 후, 각 인덱스에 (남은 시간, 총 모금액)을 기록하려 했는데 너무 복잡했다. 쉬운 방법은 모든 것을 잘게 쪼개는 것이다! 도시 별로 (맞았다) 시간(K)을 인덱스(띠용!).. [Hash table] 1.Limit of divide and conquer : the efficiency is limited to the logarithm of the problem size! still remain time complex.. 2. Searching and sorting without comparison!! but... how..? 3. Hash Table : Dictionary 형식 key , value 사용! hash funtion은 key를 이용하여 array index를 찾아 거기에 value를 store 한다! -> time complex 없이 그냥 찾을 수 있음! f( Key ) -> array index -> store value * one key -> one index * multi key ->.. [Sorting Algorithm] O(N^2) Sorting -Without a divide-and-conquer approach -Sequential comparisons with two index iteration: 두 번의 iteration -> N! -종류:Insertion Sort / Selection Sort / Bubble Sort O(N * logN) Sorting -With a divide-and-conquer approach : 타겟 시퀀스를 쪼개서 비교한다! -recursion 이 들어감! -종류: Quick Sort : pivot (기준점) 을 설정하고, 이를 기준으로 원소를 pivot보다 더 큰 것/ pivot보다 더 작은 것으로 나눈다. pivot을 잘 설정하지 않으면 그냥 O(N^2) 될 수도 있음! Merge.. Genetic Algorithm 문제 풀이 난이도 : optimize 루트를 계산하는 시간이 오래 걸릴수록 + optimize 하다는 확신이 없을수록 어려운 문제이다. (1) Traveling salesman problem TSP 의 해결 시간은.... O(N!) complexity (2) Search space and global optimum binary search tree 는 이미 최적의 경로가 define 되어 있다. 반면 path가 정의되어 있지 않은 거대한 N 사이즈의 데이터에서 global optimum 을 찾아야 한다면 최적의 경로를 확신할 수 없고, 도달한 곳이 Local optimum 일수도 있어 어려운 문제가 될 것이다. 이때 필요한 것이 Heuristic! Heuristic Algorithm : 구조나 규칙이 있.. Priority Queue and Heap 강의 : https://www.edwith.org/datastructure-2019s2/joinLectures/22005 1.Queue input gate와 output gate가 별개로 존재하는 data storage Data In : Enqueue Data out : Dequeue Queue에 In 한 순서대로 데이터 Out. (FIFO) 2. Priority Queue Queue 에 들어가는 data에 우선순위(Priority)가 존재함! 들어온 순서에 상관 없이 우선순위가 높은 data 먼저 dequeue. - Lazy approach == Unsorted implementation : Enqueue 할 때는 그냥 넣고 -> Dequeue 할 때 priority 순으로 out! -Early-Bir.. Big O notation 동작하는 프로그램의 효율성을 왜 재야할까? 큰 데이터를 분석할 때, runtime이 너무 오래 걸리면 결국 효용성이 없는 프로그램이라는 뜻!(indfficient) program 의 효율성을 따질 때 고려할 것 -Algorithm : (1)문제를 풀기 위하여 (2)명확히 정의된 지시들 - Data Structure : 데이터가 만들어져 있는 구조 모두 중요하다!! Big O notation 왜 우리는 효용성을 고려할 때, Big O notation을 사용할까? Big O notation은 최악의 경우를 가정하여 runtime이 '적어도' 이정도는 걸릴 것이다 라는 보장을 한다. --> 현업에서는 적어도 얼마나 걸릴지가 중요하기 때문에 Big O notation을 주로 사용함. Big O notation이.. 이전 1 다음
