DATA101

본 포스팅에서는 삽입 정렬(Insertion sort) 알고리즘에 대해 알아봅니다. 📚 목차 1. 삽입 정렬이란? 2. 삽입 정렬의 동작 과정 3. 삽입 정렬 구현(Python) 4. 삽입 정렬의 시간 복잡도 1. 삽입 정렬이란? 삽입 정렬은 정렬이 필요한 데이터를 찾고 적절한 위치에 삽입하며 정렬하는 알고리즘입니다. 삽입 정렬은 필요할 때만 데이터를 비교하고 삽입하기 때문에 데이터가 어느 정도 정렬되어 있을 때 더욱 효율적으로 동작합니다. 이러한 특징 덕분에 정렬 상태와 상관없이 모든 데이터를 일일이 비교하며 정렬하는 방식인 선택 정렬보다 일반적으로 효율적입니다. [알고리즘] 선택 정렬에 대해 알아보자! (+Python 구현) 오늘은 선택 정렬(selection sort) 알고리즘에 대해 알아보도록 하..

본 포스팅에서는 선택 정렬(selection sort) 알고리즘에 대해 알아봅니다. 📚 목차 1. 선택 정렬이란? 2. 선택 정렬의 동작 과정 3. 선택 정렬 구현(Python) 4. 선택 정렬의 시간 복잡도 1. 선택 정렬이란? 선택 정렬은 여러 개의 데이터가 무작위로 있을 때 전체 데이터에서 매번 가장 작은(또는 가장 큰) 데이터를 선택하여 데이터 간의 위치를 변경하는 과정을 반복하여 데이터를 오름차순(또는 내림차순)으로 정렬할 때 사용합니다. 선택 정렬의 종류는 2가지로 나눌 수 있습니다. 최소 선택 정렬(Min-selection sort): 매번 가장 작은 데이터를 선택하고 데이터 간의 배치를 변경하며 오름차순으로 정렬 최대 선택 정렬(Max-selection sort): 매번 가장 큰 데이터를 ..

본 포스팅에서는 너비 우선 탐색이라고 불리는 BFS(Breadth-First Search)에 대해 알아봅니다. 📚 목차 1. BFS 알고리즘이란? 2. BFS 알고리즘 동작 과정 3. BFS 파이썬 구현 3.1. 소스코드 설명 3.2. 전체 소스코드 1. BFS 알고리즘이란? BFS(Breadth-First Search)란 너비 우선 탐색이라고도 불리며 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘입니다. BFS 알고리즘은 언제 사용하면 좋을까요? BFS 알고리즘은 주로 그래프에서 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제를 효과적으로 해결할 수 있는 알고리즘입니다. 그리고 "미로를 빠져나가는 최단 거리(경로)"를 구하는 문제 등에서 효과적으로 활용할 수 있는 알고리즘입니다...

본 포스팅에서는 깊이 우선 탐색 DFS(Depth-First Search) 알고리즘에 대해 알아봅니다. 📚 목차 1. DFS 알고리즘이란? 2. DFS 알고리즘 동작 과정 3. DFS 파이썬 구현 1. DFS 알고리즘이란? DFS(Depth-First Search)는 그래프 전체를 탐색하는 방법(i.e., 완전 탐색) 중 하나로, '깊이'를 우선적으로 탐색하는 알고리즘입니다. DFS는 한 노드를 시작으로 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색합니다. 예를 들어, DFS 알고리즘은 미로 탐색 시 한 방향으로 모든 노드를 방문하다가 더 이상 다른 노드를 방문할 수 없는 노드에 이르렀을 때, 다시 가장 가까운 갈래길로 돌아가 방문하지 않은 노드 방향으로 탐색을 이어가는 방법입니다...

본 포스팅에서는 큐(Queue) 자료구조에 대해 알아봅니다. 📚 목차 1. 큐(Queue) 자료구조란? 2. 큐 동작 예시 3. 큐 구현(Python) 1. 큐(Queue) 자료구조란? 큐 자료구조는 선입선출(先入先出, First In First Out, 줄여서 FIFO) 구조로 흔히 놀이공원 내 놀이기구 대기줄에 비유합니다(그림 1 참고). 즉, 놀이기구 대기줄에 먼저 선 사람(데이터 입력)이 먼저 놀이기구를 타는(데이터 출력/제거) 방식입니다(단, 새치기는 없다고 가정). 큐 자료구조는 아래 2가지 핵심적인 함수로 동작합니다. 데이터 삽입(append) 데이터 삭제(popleft) 큐 자료구조를 사용할 때는 오버플로우(Overflow)와 언더플로우(Underflow)가 발생하지 않도록 유의해야 합니다..

본 포스팅에서는 스택(Stack) 자료구조에 대해 알아봅니다. 📚 목차 1. 스택(Stack) 자료구조란? 2. 스택 동작 예시 3. 스택 구현(Python) 1. 스택(Stack) 자료구조란? 스택 자료구조는 먼저 들어온 데이터가 늦게 나가는 형태의 자료구조로서 선입후출(先入後出) 방식입니다. 스택 자료구조는 아래의 그림 1 과 같이 입구와 출구가 동일한 형태로 표현할 수 있으며 "박스 쌓기"를 연상하시면 기억하기 편합니다. 스택 자료구조는 아래 2가지 핵심적인 함수로 동작합니다. 데이터 삽입(Push) 데이터 삭제(Pop) 스택 자료구조를 사용할 때는 오버플로우(Overflow)와 언더플로우(Underflow) 발생에 유의해야 합니다. 오버플로우: 어떠한 자료구조가 저장할 수 있는 데이터의 크기를 초..

안녕하세요, 이번 포스팅에서는 지난 포스팅에서 다룬 그리디 알고리즘 연습문제의 소스코드를 공유합니다. heytech.tistory.com/44 [알고리즘] 그리디(Greedy) 알고리즘에 대해 알아보자! (연습문제 포함) 오늘은 알고리즘 스터디 첫 번째 포스팅으로서 그리디 알고리즘에 대해 알아보도록 하겠습니다. 그럼 바로 시작하죠! 1. 그리디 알고리즘이란? 그리디(Greedy)는 그림 1 에서 보실 수 있듯이 사전 heytech.tistory.com 1. 연습문제 그리디 알고리즘의 가장 대표적인 예시 문제는 거스름돈 계산 문제입니다. Q. 당신은 카페의 계산을 도와주는 직원이며 카운터에는 거스름돈으로 사용하는 화폐로서 500원, 100원, 50원, 10원짜리 동전이 무한히 있다고 가정한다. 손님에게 제..

본 포스팅에서는 그리디(Greedy) 알고리즘에 대해 알아봅니다. 1. 그리디 알고리즘이란? 그리디(Greedy)는 그림 1 에서 보실 수 있듯이 사전적 의미로서 "탐욕스러운"이라는 뜻을 갖고 있습니다(그림 2 참고). 즉, 그리디 알고리즘은 주어진 문제를 프로그래밍을 통해 탐욕스럽게 풀어내는 알고리즘입니다. 여기서 "탐욕스러운"이라는 말은 그리디 알고리즘이 주어진 상황에서 최선의 옵션만 선택하며 현재의 선택이 향후에 미칠 영향은 고려하지 않는다는 의미입니다. 2. 특징 그리디 알고리즘 문제에서는 주로 "가장 큰 숫자 순서대로" 혹은 "가장 짧은 경로 순으로"와 같은 조건을 제시해 줍니다. 이러한 조건은 대체로 정렬 알고리즘으로 해결할 수 있다는 점에서 그리디 알고리즘은 정렬 알고리즘과 세트로 주어지는 ..