야미스터디/Algorithm6 제자리 정렬 & 안정 정렬 🤔 정렬(sorting) 이란? 순서 없이 나열된 자료를 특정한 키 값에 따라 오름차순이나 내림차순으로 자료를 재배열하는 것이다 정렬은 자료 탐색에 있어 필수적이다 사전에서 단어를 찾을 때 알파벳 순으로 정렬되어 있어 단어를 찾는 것이 수월한 것처럼, 정렬은 자료 탐색에 있어 중요한 부분이다! ✍️ 오늘의 토픽 오늘은 알고리즘 공부를 하다보면 종종 등장하는 제자리 정렬과 안정 정렬에 대해 간단하게 알아보려고 한다! 사실 처음에는 이들이 퀵 정렬, 합병 정렬처럼 정렬 알고리즘의 종류인 줄 알았다..ㅎㅎ 그래서 정리를 하고 넘어가려고 한다! 🚶제자리 정렬 (Inplace algorithm) 추가적인 메모리 공간을 많이 필요로 하지 않거나 전혀 필요하지 않은 정렬이다 예시 위처럼 추가적인 메모리 공간 없이 정.. 2023. 7. 13. [알고리즘] DFS/BFS 📌 DFS (Depth-First Search, 깊이 우선 탐색) 한 노드에서 다음 분기(branch)로 넘어가기 전에, 해당 분기(branch)를 모두 탐색하는 방법 탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색한다 DFS의 특징 자기 자신을 호출하는 순환 알고리즘의 형태를 갖는다 : 재귀 or 스택 DFS를 구현할 때 노드의 방문 여부를 반드시 검사해야 한다 검사하지 않을 경우 무한 루프에 빠질 수 있다 ex) visit[index] = true; 미로를 탐색할 때, 해당 분기에서 갈 수 있을 때까지 계속 가다가, 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길(새로운 분기)로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다 모든 노드를 방문하고자 할 떄, DFS를 사용한다 BFS(.. 2022. 10. 2. [알고리즘] Tree 구조 📌 Tree구조 Tree 구조란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조이다 트리는 위와 같이 나무를 거꾸로 뒤집어 놓은 모양과 유사하다고 하여 붙여진 이름이다 또한 트리 내에 다른 하위 트리가 있고, 그 하위 트리 안에 또 다른 하위 트리가 있는 재귀적 자료구조읻 대표적인 예시로는 컴퓨터의 directory 구조가 있다 Tree 구조 용어 1) 노드 (Node) 트리를 구성하고 있는 기본 요소 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있다 위의 그림에서 A, B, C, D, ..., I, J 까지 모두 노드이다 2) 간선 (Edge) 노드와 노드 간의 연결선 위의 그림에서 노드 간을 연결하는 직선이다 3) 루트 노드 (Root Node) Tree 구조에서 부모가 없는 최상위 노.. 2022. 9. 13. [알고리즘] 동적 계획법(DP) 📌 동적 계획법 (Dynamic Programming) 동적 계획법은 다이나믹 프로그래밍(DP)라고도 불린다 이는 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로, 특정한 알고리즘이 아닌 하나의 문제 해결 패러다임으로 볼 수 있다 쉽게 생각하면 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용하기 떄문에 '구한 값은 기억하며 푸는 방법'이다 DP를 사용하는 이유 DP는 일반적인 재귀 방식과 매우 유사하다 그러나 일반적인 재귀를 단순히 사용 시, 동일한 작은 문제들이 여러번 반복되어 비효율적인 계산이 될 수 있다 🧮 대표적인 예시 : 피보나치 수열 피보나치 수열은 다음과 같다 1, 1, 2, 3, 5, 8, 13, 21.. 2022. 8. 28. [알고리즘] 빅 오(Big-O) 표기법 📌 🖐 최선, 평균, 최악의 경우 동일한 알고리즘도 입력되는 데이터에 따라 다른 실행 시간을 보일 수 있다 예를 들어 정렬을 하는 알고리즘에 대부분 정렬이 완료되어 있는 데이터를 입력한다면 뒤죽박죽 섞여 있는 데이터 집합보다 더 빨리 정렬이 완료될 것이다 따라서 알고리즘의 효율성은 입력되는 데이터의 집합에 따라 3가지의 경우로 나누어 평가할 수 있다 최선의 경우 (Best Case) : 실행 시간이 가장 적은 경우를 말한다 평균의 경우 (Average Case) : 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려한 평균 수행 시간을 말한다 최악의 경우 (Worst Case) : 알고리즘의 수행 시간이 가장 오래 걸리는 경우 평균적인 경우의 실행 시간이 가장 측정하기 좋아보이지만, 광범위한 데이터 집합에.. 2022. 8. 26. [알고리즘] 시간 복잡도 vs 공간 복잡도 📌 알고리즘 성능 평가 알고리즘의 성능을 평가하기 위해서는 '복잡도(Complexity)의 척도'를 사용한다 동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을 수록 좋은 알고리즘이다 복잡도는 시간 복잡도와 공간 복잡도가 있다 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 알고리즘 성능 분석의 조건 서로 다르 알고리즘을 비교하려면 반드시 동일한 하드웨어(Hardware)를 사용한 상태에서 알고리즘의 실행 시간을 측정해야 한다 만약 알고리즘 A는 일반 개인용 컴퓨터에서 측정하고, 알고리즘 B는 슈퍼 컴퓨터에서 측정한다면 측정 결과는 객관성이 없게 된다! 또한 알고리즘을 측정할 때 사용하는 소프트웨어의 환경.. 2022. 8. 26. 이전 1 다음
