728x90 알고리즘 & 자료구조9 Hash Tables이란? #NomadCoders #자료구조 1. HashTable이란? key value system으로 javascript에서는 object로 python에서는 dictionary, Go에서는 map 등등.. 이 있다. array와 비교해보자. 예를 들어 카페 메뉴가 다음과 같이 배열로 되어있다고 가정하자. menu = [{bread, 2000}, {coffee, 1500}, ... ]; 여기서 coffee의 가격을 알고 싶으면 선형검색을 하면 되나 메뉴가 많을수록 오래걸린다. 이때 hash tables로 정리하면 다음과 같다. menu = {"bread" : 2000, "coffee" : 1500, ... }; // key(메뉴) : value(가격) Hash tables의 시간복잡도는 상수시간인 Q(1)이기.. 2021. 8. 24. 정렬 알고리즘이란? #알고리즘 #코딩 #노마드 코더 본 포스팅은 노마드코더 영상을 정리하며 학습하기 위한 목적을 가지고 있습니다. 정렬 알고리즘이란? Sorting : 뜻대로 정렬하는 것 그 중 배열 정렬 중에서 이해하기 쉬운 3가지 정렬을 살펴보도록 하자. 1. Bubble Sort(버블 정렬) 시간 복잡도 : O(n^2) ...................................................( 스포하자면 이번에 공부할 3가지 정렬 모두 시간 복잡도는 같다 ) 버블 정렬은 잘 사용되지 않음 좋은 알고리즘은 아님. 그러나 이해하기 쉬운 알고리즘이다. 원리는 간단하다. 배열에서 두개를 선택하여 선택된 왼쪽이 오른쪽보다 크면 swap을 하여 정렬하는 방식 버블 정렬 예시 : java for(int i=0;.. 2021. 7. 26. BigO란? #알고리즘 #코딩 #노마드 코더 본 포스팅은 노마드코더 영상을 정리하며 학습하기 위한 목적을 가지고 있습니다. BigO를 알아보자 작성된 코드는 더 빠르다, 더 느리다는 시간으로 표현하지 않는다. 왜 그럴까? 속도는 하드웨어가 결정하기 때문에 시간으로 표현하지 않고 알고리즘 속도는 '완료까지 걸리는 절차의 수'로 결정한다. 예를 들어, 딱 5번의 스탭이 10개스탭보다 훌륭한 알고리즘인 것이다. 선형 검색은 한개씩 한개씩 검색해 데이터가 10개면 10개 스텝이 필요하다. 선형 알고리즘은 input 사이즈가 n이라면 n스텝을 요구하게 된다. 따라서 선형 검색의 시간 복잡도는 O(N)이고 그래프로 표현하면 다음과 같다. 이렇게 BigO는 시간복잡도를 빠르게 설명할 수 있다. 이것을 이해하면 알고리즘 분석을 빠.. 2021. 7. 19. 검색 알고리즘 #이진검색 #선형 검색 #노마드 코더 본 포스팅은 노마드코더 영상을 정리하며 학습하기 위한 목적을 가지고 있습니다. 알고리즘이란? 절차/ 스텝이다 - 생활속의 레시피라고 생각하자. 어떤 알고리즘을 선택하는지에 따라 해당 작업을 수행하는 속도 차이가 난다. 어떤 자료구조를 언제 선택하는지 중요한 것 처럼 알고리즘도 같다. 알고리즘 또한 얼마나 많은 절차와 스텝이 필요한 시간복잡도가 있다. - 당연히 적은 절차가 더 훌륭한 알고리즘 검색 알고리즘 오늘은 이진검색 알고리즘 vs 선형검색 알고리즘을 알아보자. 모두 검색 알고리즘이며, 다른 종류로는 정렬 알고리즘도 있다. 선형 검색 알고리즘 자연스러운 검색으로 1번 부터 차례로 검색해 목표값을 찾는다. 배열의 순서대로 찾기 때문에 최악의 경우는 맨 마지막 배열 .. 2021. 7. 10. Array 배열이란? #Array #코딩 #노마드 코더 본 포스팅은 노마드코더 영상을 정리하며 학습하기 위한 목적을 가지고 있습니다. Array 배열이란? 시간복잡도(time complexity)는 데이터 구조의 오퍼레이션 혹은 알고리즘이 얼마나 빠르고 느린지 측정하는 방법. 실제 시간 측정이 아니라 얼마나 많은 단계가 있는가로 측정한다. 당연히 단계가 적을수록 좋다. 메모리는 non-volatile Memory vs volatile Memory 두가지 경우가 있다. 비휘발성 메모리는 하드디스크 같은 것이고 휘발성 메모리는 RAM과 같은 것이다. 데이터 접속을 랜덤으로 하니까 빠르다. 순차적이 아니라 5번째를 가고싶으면 5번째로 갈 수 있다. 배열을 만들때에는 얼마나 긴지 알려줘야 한다. 왜냐하면 컴퓨터는 그 길이를 알아야 .. 2021. 7. 9. BFS 알고리즘이란? 너비 우선 탐색(BFS, Breadth-First Search) 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 이는 **그래프 탐색** (하나의 정점으로 시작하여 모든 정점을 한번씩 방문)에 속한다. BFS는 두 노드 사이의 **최단 경로** 및 **임의의 경로** 를 찾을때 사용하며 자료 구조 **큐(Queue)** 를 이용해 탐색을 한다. 유사 알고리즘 : Prim, Dijkstra 너비 우선 탐색(BFS) 예제 - Python 해당 예제는 같은 숫자끼리 땅따먹기로 인접한 같은 숫자끼리의 넓이를 구하는 예제이다. 바로 구현해보기 위한 예제이므로 코드가 지저분하다.. 구현 방식은 방문 여부, 큐(Queue)를 활용하였다. def solution(v): result = [0, 0, 0] .. 2021. 7. 8. 알고리즘 왜 필요할까? #알고리즘 #코딩 #노마드 코더 본 포스팅은 노마드코더 영상을 정리하며 학습하기 위한 목적을 가지고 있습니다. 알고리즘 왜 필요할까? 처음 코딩을 공부할때에는 데이터 구조와 알고리즘을 공부할 필요가 없다. 왜 그럴까? 이제 막 시작한 초보 개발자는 니즈가 없기 때문이다. 앱을 동작하는 것이 첫번째 목적이기 때문이다. 그럼 언제 필요할까? 소스코드에 버그는 없으나 앱이 느릴때 ( = 코드 최적화를 어디서부터 해야할지 모를때 ) 관리가 편하고, 다른사람들과 일하기 편하게 코드를 작성할때 초보 개발자가 첫번째 목적을 달성한 뒤에 그다음 단계가 바로 어떻게 더 빠르고 효율적이게 구현할 것인가 이다. 데이터 구조 vs 알고리즘 데이터 구조 프론트엔드 : 모두 데이터를 필요. json 데이터를 아름답게 표현 백엔드.. 2021. 7. 8. [Java] Queue란? Queue란? Queue는 줄을 지어 순서대로 처리되는 자료구조로 First In First Out의 형태를 가진다. 말 그대로 먼저 들어온 뎅터가 먼저 나가는 구조를 말한다. 사용 예제로는 그래프의 넓이 우선탐색인 BFS와 컴퓨터 버퍼(큐)에서 사용되며 맨 앞쪽의 데이터 삭제를 Dequeue, 맨 마지막의 데이터 추가를 Enqueue라 한다. Queue 사용법 - 생성 Queue를 JAVA에서 사용하기 위해서는 Queue와 LinkedList 모두 Import가 필요하다. import java.util.LinkedList; import java.util.Queue; Queue queue = new LinkedList(); Queue queue = new LinkedList(); Queue 사용법 - 값.. 2021. 7. 5. Dijkstra 알고리즘 목적 다익스트라 알고리즘을 이해하기 다익스트라 알고리즘을 Java로 구현하기 시작하는 말 티스토리 블로그로 이전하고 처음 포스팅하는 글입니다. 첫 게시글은 전 github.io 블로그에서 가장 클릭 수가 많았던 다익스트라 알고리즘을 옮기려고 한다. (검색어는 '다익스트라 2차원 배열') 다익스트라(dijkstra) 알고리즘 이란? 다익스트라 알고리즘은 최단경로를 탐색하는 알고리즘이다. 구현 방법으로 2차원 배열 또는 힙(Heap)을 이용하여 구현할 수 있으며 각각 O(N^2)와 O(ElogN) 시간복잡도를 가진다. 다익스트라 알고리즘은 음수 가중치를 가진 그래프에서는 사용할 수 없는 단점이 있는데 이때에는 벨만-포드 알고리즘을 사용해야 합니다. 원리 1. 모든 가중치를 무한으로 설정한다. 2. 방문하지 .. 2021. 6. 22. 이전 1 다음 728x90
