728x90 공부/알고리즘28 너비 우선 탐색(BFS) ※이 포스팅은 나동빈님 강의를 듣고 정리한 것 입니다.※ https://www.youtube.com/watch?v=66ZKz-FktXo&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=16 너비 우선 탐색 (Breath-First-Search, BFS)입니다. 너비 우선 탐색은 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘입니다. 특히나 '맹목적인 탐색' 을 하고자 할때 사용하는 탐색 기법이고 미로찾기와 같은 곳에서 많이 활용이 됩니다. 이는 '최단 경로'를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용됩니다. 큐를 이용합니다. 'BFS는 가까운 거를 먼저 탐색한다'라는 개념입니다. 큐와 그래프가 준비가 되었습니다. BFS는 맨 처음에 시작.. 2020. 6. 3. 알고리즘 스택, 큐 알고리즘에서 가장 많이 활용이 되는 자료구조가 스택과 큐가 아닐까 싶습니다. 그냥 다른 수업을 들을 때도(메모리의 스택구조라던가, 데이터통신에서 큐잉이론이라던가) 정말 자주 나오는 주제인데요. 오늘은 알고리즘 측면에서 stack 라이브러리에 사용에 대해 이야기 해보겠습니다. 일단 stack 은 접시 쌓기라고 생각하시면 됩니다. 접시를 쌓는다고 생각할때 위로 쌓이잖아요? 그리고 접시가 필요해서 하나 들고갈때는 가장 아래거를 들고 가나요? 아니죠. 가장 위에 있는 접시, 즉 가장 최근에 놔둔 접시를 가져갑니다. 이처럼 스택은 가장 최근에 들어온 게 가장 먼저 나가는 구조입니다. 아래 그림을 보면 조금 더 쉽게 이해가 되실 겁니다. 스택을 삽입(Push) 하는 과정입니다. 4를 먼저 넣었기 때문에 4가 제일 .. 2020. 6. 3. 계수 정렬(Counting Sort) 이때까지 배운 O(N log N)의 시간복잡도인 선택, 버블, 삽입 정렬 그리고 O(N^2)의 시간복잡도인 퀵, 병합, 힙 정렬을 배웠습니다. 가장 빨랐던 정렬은 아무래도 퀵정렬이었는데요. 이거보다 빠르게 정렬을 하는 계수 정렬에 대해 알아보겠습니다. 다음의 5 이하 자연수 데이터들을 오름차순 정렬하세요. 1 3 5 2 3 1 3 4 4 3 4 2 3 4 3 1 1 2 4 3 3 1 2 3 4 5 1 3 2 4 정렬할 데이터 개수가 30개입니다. 특징은 모든 데이터가 1부터 5 사이입니다. 계수 정렬은 이처럼 적절한 '범위 조건'이 있어야한다는 전제에서 굉장히 빠른 알고리즘입니다. 그 속도는 O(N) 입니다. ( 저도 처음보는 시간복잡도의 속도입니다.) 계수 정렬(Counting Sort)는 단순하게 '.. 2020. 6. 1. 힙정렬 저번주에 공부하긴 했지만 이해하는데 좀 시간이 걸리는 바람에 지금 포스팅합니다. 힙정렬은 퀵정렬과 병합정렬과 더불어 시간복잡도 O(nlogn) 을 가진 정렬입니다. 힙정렬을 이해하기 위해서는 완전 이진 트리를 이해해야하는데요. 이진 트리는 자식노드가 두개 이하 트리를 의미합니다.. 여기서 가장 위에 있는 7은 루트노드(root)입니다. 그리고 8과 5의 부모노드입니다. 2와 3은 8의 자식노드입니다. 가장 밑 부분인 2 3 1 2 는 리프노드(leaf)라고 합니다. 트리는 다양하게 생길 수 있습니다. 이런식도 가능합니다. 그 중에서 이진 트리는 자식노드가 두개 이하인 트리이고 완전 이진트리는 자식노드가 두개인 트리를 의미합니다. 간단하죠? 힙은 이런 완전 이진트리를 사용합니다. 한번 트리를 만들어 볼까요.. 2020. 6. 1. 이전 1 2 3 4 5 6 7 다음 728x90
