전체 글28 [알고리즘-14] 깊이 우선 탐색(DFS) 안녕하세요 기린입니다 :) 오늘은 지난 시간에 이어 깊이 우선 탐색(Depth-Frist Search)에 대해 알아보도록 하겠습니다. 먼저 깊이 우선 탐색이란 말 그대로 보다 깊은 것을 우선적으로 탐색하는 알고리즘입니다. 맹목적으로 각 노드를 탐색할 때 주로 사용되죠. 너비 우선 탐색과는 다르게 큐(Queue)를 사용하지 않고 스택(Stack)이 사용됩니다. 그리고 굳이 스택을 사용하지 않아도 구현이 가능하다는 특징이 있습니다. 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문입니다. DFS는 맨 처음에 시작 노드(Start Node)를 스택에 삽입하면서 시작합니다. 또한 그와 동시에 시작 노드를 방문했다고 알리는 '방문 처리'를 해주도록 합니다. 방문 처리는 파란색으로 해주도록 하겠습니다. 이제는 .. 2022. 4. 25. [알고리즘-13] 너비 우선 탐색(BFS) 안녕하세요 기린입니다 :) 오늘은 배울 알고리즘은 바로 너비 우선 탐색(Breadth-Frist Search, BFS)은 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 입니다. 특히 '맹목적인 탐색'을 하고자 할 때 사용할 수 있는 탐색 기법입니다. 너비 우선 탐색은 '최단 경로'를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용합니다. 준비물은 큐(Queue)인데요 아래와 같이 큐와 그래프를 준비해보도록 합시다. BFS는 맨 처음에 시작 노드(Start Node)를 큐에 삽입하면서 시작합니다. 또한 시작 노드를 방문 했다고 '방문 처리' 해주도록 합니다. 방문 처리는 파란색으로 해주도록 하겠습니다. 이제 BFS는 다음과 같은 간단한 알고리즘에 따라서 작동합니다. 1. 큐에서 하.. 2022. 4. 22. [알고리즘-12] 스택(Stack), 큐(Queue) 안녕하세요 기린입니다 :) 이번 시간에는 스택과 큐를 배워보겠습니다. 스택(Stack)과 큐(Queue)는 컴퓨터 공학에서 가장 기본이 되는 자료구조입니다. 말 그대로 자료를 표현하고 처리하는 방법에 관한 것입니다. 예를 들자면 스택은 택배 상하차를 생각하시면 되고, 큐는 은행 창구를 생각하시면 됩니다. 먼저, 스택부터 확인해봅시다. 어렵지 않은 개념이니 천천히 생각해보시죠 :] 스택은 아래와 같이 출구가 하나밖에 없는 상태로 표현할 수 있습니다. 첫 번째 명령어 삽입(7)이 실행되면 7이 삽입됩니다. 다음 명령어 삽입(5)이 실행되면 위와 같습니다. 이후에 원소 4가 삽입됩니다. 이제 명령어 삭제()가 수행되는데, 삭제할 때는 항상 가장 최근에 들어간 원소가 나갑니다. 이후에 원소 6이 삽입됩니다. 결.. 2022. 4. 19. [알고리즘-11] 심화 정렬 문제 풀어보기 안녕하세요 기린입니다 :) 이번에는 지난 시간까지 배운 정렬들을 활용하여 백준 온라인 저지 https://www.acmicpc.net/ 에 있는 심화 정렬 문제들을 풀어보고자 합니다. 실제 프로그래밍 대회나 실무에서 요구하는 대부분의 정렬 문제는 단순한 형태의 정렬 문제가 아닙니다. 다양하게 연관된 데이터 상에서 정렬을 수행해야 하는 문제가 대부분입니다. 따라서 심화적인 정렬 문제들을 풀어보면서 연습하는 시간이 필요합니다. ① 단어 정렬 https://www.acmicpc.net/problem/1181 위 문제는 단어들을 정렬하는 문제입니다. 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 1. 길이가 짧은 것부터 2. 길이가 같으면 사전 순으로 .. 2022. 4. 12. [알고리즘-10] 계수 정렬(Counting Sort) 안녕하세요 기린입니다 :) 지금까지 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬 알고리즘에 대해 알아보았는데요 여기서 정렬 속도가 가장 빠른 알고리즘은 퀵 정렬, 병합 정렬, 힙 정렬 등이 시간복잡도 O(N * logN)으로 가장 빠르다고 할 수 있습니다. 하지만 이 보다 더 빠르게 정렬해야 한다면 어떻게 해야할까요? 다음의 5이하 자연수 데이터들을 오름차순 정렬하세요. 1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1 이번 예시의 데이터의 갯수는 30개입니다. 다만 모든 데이터가 1부터 5사이에 속한다는 특징이 있습니다. 이처럼 '범위 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘이 있습니다. 시간 복잡도가 무려 O(.. 2022. 4. 11. [알고리즘-9] 힙 정렬 (Heap Sort) 안녕하세요 기린입니다 :) 오늘은 힙 정렬(Heap Sort)에 대해 알아보겠습니다. 먼저 힙 정렬은 병합 정렬과 퀵 정렬만큼 정렬속도가 빠른 알고리즘입니다. 그리고 실제 고급 프로그래밍 기법으로 자주 사용하기 때문에 반드시 알고 넘어가야 할 정렬 알고리즘이지요. 힙 정렬은 힙 트리 구조(Heap Tree Structure)를 이용하는 정렬 방법입니다. 힙 트리 구조를 이해하기위해 먼저 힙과 트리 구조에 대해 알아야 합니다. 가장 먼저 트리 구조 중 이진 트리(Binary Tree)에 대해서 알고있을 필요가 있습니다. 이진 트리란 컴퓨터 안에서 데이터를 표현할 때 데이터를 각 노드(Node)에 담은 뒤에 노드를 두 개씩 이어 붙이는 구조를 말합니다. 이 때 트리구조에 맞게 부모 노드에서 자식 노드로 가지.. 2022. 4. 5. 이전 1 2 3 4 5 다음
