cinnamonbrown 의 블로그

1. 최단 경로 알고리즘최단 경로 알고리즘은 그래프(Graph)안에서 두 정점 사이를 이동할 때 가장 짧은 경로를 찾는 것을 의미한다.대표적인 최단 경로 알고리즘으로는 다익스트라(Dijkstra), 벨만-포드(Bellman-Ford), 플로이드-워셜(Floyd-Warshall) 알고리즘 등이 존재한다.2. 다익스트라 알고리즘2.1 다익스트라 알고리즘이란?다익스트라 알고리즘은 하나의 시작 정점으로부터 시작해 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.최단 경로 문제를 해결한다는 것은 그래프 내부의 간선(Edge)들을 탐색하면서, 한 정점에서 다른 정점으로 이동할 때 간선들의 가중치 합이 가장 작은 경로를 찾는 것을 의미한다.이 때, 경로를 구성하는 간선들의 가중치 합을 경로 비용(Path Cost..

1. 그리디(Greedy) 알고리즘이란1.1 왜 탐욕 알고리즘이라고 부를까?매 순간 가장 유리해보이는 선택을 하기 때문이다. Greedy 알고리즘은 매 단 계마다 지금 당장 가장 좋아 보이는 선택을 하는 방식의 알고리즘이다.이런 선택을 계속 반복하면서 최종적으로는 최적의 해를 찾을 수 있기를 기대한다.1.2 동작 방식1️⃣ 목표 정하기먼저 문제에서 무엇을 최적화할 것인지를 결정한다.예를 들어 가치의 합을 최대화하거나 비용을 최소화하는 것이 목표가 될 수 있다. 2️⃣ 현재 상황에서 가장 좋아 보이는 선택하기지금 당장 가장 유리하다고 판단되는 선택지를 고른다 3️⃣ 해당 선택이 가능한 지 확인선택한 항목이 문제의 조건이나 제약 사항을 만족하는 지 체크한다. 조건을 만족하지 못하면 다른 선택지를 고려한다. ..

1. 탐색 알고리즘이란?우리는 종종 수백, 수천 개, 더 나아가 수십만 개의 데이터 중에서 특정 값을 찾아야 할 때가 있다. 예를 들어 휴대폰에서 특정 연락처를 찾거나, 수많은 정보 속에서 원하는 데이터를 검색해야 하는 상황이 그렇다.이때 중요한 역할을 하는 것이 바로 탐색 알고리즘(Search Algorithm) 이다. 만약 탐색 알고리즘이 없다면, 원하는 데이터를 찾기 위해 모든 데이터를 하나씩 직접 확인해야 한다. 데이터의 양이 많아질수록 이러한 방식은 시간이 오래 걸리고 비효율적일 수 있다. 탐색 알고리즘은 컴퓨터 사이언스에서 여러 데이터(컬렉션 자료형) 안에서 원하는 값을 더 효율적으로 찾기 위해 사용되는 알고리즘 이다.대표적인 탐색 알고리즘으로는 선형 탐색(Linear Search) 과 이진 ..

병합 정렬병합 정렬(Merge Sort) 은 효율적이고 안정적인 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 방식을 사용한다.쉽게 말하면, 배열을 계속 절반으로 나눈 뒤 정렬하면서 다시 합쳐가는 방식이다. 병합 정렬은 먼저 입력된 배열을 재귀적으로 두 개의 절반으로 나누고, 나누어진 배열들을 각각 정렬한 뒤, 마지막에 다시 병합(merge) 하여 최종적으로 정렬된 배열을 만든다.병합 정렬의 동작 방식 1️⃣ Divide(분할)배열을 더 이상 나눌 수 없을 때까지 계속 절반씩 나눈다 👉 배열의 크기가 1이 될 때까지 재귀적으로 분할한다2️⃣ Conquer (정복)나누어진 각 부분 배열을 정렬한다.👉 원소가 1개인 배열은 이미 정렬된 상태이기 때문에 다시 정렬할 필요가 없다...

퀵 정렬(Quick Sort)퀵 정렬(Quick Sort) 은 분할 정복(Divide and Conquer) 방식을 사용하는 정렬 알고리즘이다.여기서 기준이 되는 값(pivot)을 정한 뒤 그 값을 기준으로 작은 값과 큰 값을 나누어 정렬한다. 이 때, Pivot이 어떤 값인지에 따라 정렬 성능이 달라질 수 있다.동작 방식1️⃣ Pivot 선택하기먼저 기준이 될 값(pivot) 을 하나 선택한다. pivot은 상황에 따라 다르게 정할 수 있는데, 보통첫 번째 값마지막 값랜덤 값중앙값을 사용한다.2️⃣ Pivot 기준으로 값 나누기 이제 pivot을 기준으로 배열을 나눈다.pivot보다 작은 값 → 왼쪽pivot보다 큰 값 → 오른쪽으로 이동하게 된다.예를 들어[7, 5, 2, 4, 8, 1, 3]pivo..

재귀 함수(Recursive Function)란?자기 자신을 직접적이든 간접적으로 다시 호출하는 함수를 재귀 함수라고 한다.🤔 일반함수와 어떻게 다른가? 일반적으로 함수는 자신만의 scope(범위)를 가진다.즉, 함수 안에서 만든 변수나 코드들은 그 함수 안에서만 사용되는 작은 공간을 가진다는 뜻이다.그리고 함수가 호출되면, 컴퓨터는 그 함수가 실행되기 위한 정보들을 스택(Stack)에 저장해둔다. 일반 함수는 보통 한 번 호출되고 실행이 끝나면 종료된다. 예를 들어,def hello(): print('안녕!')hello()이 경우 hello()함수는 한 번 실행되고 끝난다. 즉, Stack에 함수 실행 정보가 한 번만 쌓였다가 사라지는 것이다. 반면, 재귀 함수는 함수 안에서 자기 자신을 다..

정렬이란?정렬은 데이터를 특정 기준에 따라 오름차순이나 내림차순으로 재배열하는 작업을 말한다. 정렬은 크게 내부 정렬과 외부 정렬 두 가지로 나뉜다- 내부 정렬(Internal Sorting)데이터양이 비교적 적을 때 주기억 장치(RAM)안에서 바로 정렬하는 방법이다. ※ RAM : 처리 속도는 매우 빠르지만, 용량이 상대적으로 작은 편이다.- 외부 정렬 (External Sorting)데이터양이 매우 많아서 RAM 안에 한 번에 올릴 수 없을 때, SSD나 HDD 같은 보조기억장치를 활용해 정렬하는 방식이다. ※ 보조기억장치(SSD/HDD) : 저장 용량은 크지만, RAM에 비해 속도가 느린 편이다.내부 정렬우리가 흔히 아는 정렬 알고리즘은 대부분 내부 정렬이다. 버블 정렬, 선택 정렬, 삽입 정렬 같..

1. 힙(Heap)이란 무엇인가1.1 힙(Heap)힙(heap)은 완전 이진 트리(Complete Binary Tree) 구조를 가지면서, 힙 속성(heap property) 을 만족하는 자료구조이다.※ 힙 속성이란?예를 들어,Min-heap 에서는 부모 노드의 값이 자식 노드의 값보다 작거나 같아야 한다. 반대로 Max-heap 은 부모 노드의 값이 자식 노드보다 크거나 같아야 한다. Min heap과 Max heap에 대한 자세한 내용은 뒤에서 더 다뤄보고자 한다.1.2 최대 힙(Max Heap) vs 최소 힙(Min Heap)힙(Heap)은 크게 두가지, 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 나뉜다.둘의 가장 큰 차이점은 부모 노드와 자식노드의 크기 관계이다. 구분최대 힙 (..

1. 시간 복잡도(Time Complexity)시간 복잡도(Time Complexity)는 알고리즘이 실행되는데 얼마나 시간이 걸리는 지 입력 크기(Input Size)를 기준으로 나타낸 개념이다. ※ 알고리즘 = 문제 해결 방법‼️ 시간 복잡도 ≠ 실제 코드 실행 시간시간 복잡도와 실제 코드의 실행 시간이 같은 개념이라고 생각할 수 있지만, 둘은 조금 다르다.예를 들어, 같은 코드라도 컴퓨터 성능, CPU, 메모리 환경에 따라 실제 실행 시간은 달라질 수 있다.하지만 시간 복잡도는 입력 데이터 크기가 증가할 때 알고리즘이 얼마나 많은 연산을 수행하는지를 분석하는 개념이다.즉, 입력이 커질수록 실행 시간이 어떤 방식으로 증가하는가 를 보는 것이다. 또, 시간 복잡도를 활용하면 같은 문제를 해결하더라도 ..

1. 해시 테이블(Hash Table)이란 무엇인가?해시 테이블은 키(key)를 이용해서 값(value)에 아주 빠르게 접근하는 자료구조이다.2. 해시 함수(Hash Function)해시 함수는 임의의 길이를 가진 데이터(key) 값을 입력 받아 배열의 특정 인덱스(index)로 변환해주는 함수이다.즉, 데이터를 저장하거나 검색하기 위해 key값을 숫자 형태의 위치 값으로 바꿔준다. 또한, 해시 함수는 key 값들이 특정 위치에 몰리지 않도록 배열 전체에 고르게 분산되게 만들어 충돌(Collision)을 줄이고, 빠른 검색 속도를 유지할 수 있도록 도와준다.3. Key와 Value의 구조 해시 테이블에서 key와 value는 한 쌍으로 저장되는 데이터 이다.Key는 해시 함수를 통해 데이터를 찾기 ..