Algorithm14 DFS (Depth-First Search) BFS가 궁금하면 아래 글을 참조 BFS (Breadth-First Search) ✔ DFS(Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며, 그래프를 탐색하는 방법 중 하나이다. 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문하는 것으로 즉, 시작 노드에서 출발해 인접한 노드(가까운 노드)를 먼저 탐색하고 그 정점의 최대 깊이까지 탐색을 마친 후 돌아와 다른 분기로 다시 탐색하는 알고리즘이다. 넓게 탐색하기 전에 깊게 탐색 스택 or 재귀를 사용하여 구현 모든 노드를 방문할 때 사용 ※ 중요한 점은 방문한 정점은 다시 방문하지 않아야 한다. DFS는 스택으로도 구현할 수 있지만 재귀로 구현하는 편이 더 깔끔해서 재귀로 더 많이 구현하는 것 같다. DFS와 BF.. 2023. 6. 25. BFS (Breadth-First Search) DFS가 궁금하면 아래 글을 참조 DFS (Depth-First Search) ✔ BFS(Breadth-First Search) BFS는 너비 우선 탐색이라고도 부르며, 그래프를 탐색하는 방법 중 하나이다. 하나의 정점으로부터 시작해서 차례대로 모든 정점들을 한 번씩 방문하는 것으로 즉, 시작 노드에서 출발해 인접한 노드(가까운 노드)를 먼저 탐색하고 현재 깊이의 모든 노드를 탐색하면서 가는 알고리즘이다. 깊게 탐색하기 전에 넓게 탐색 두 정점 사이의 최단 경로를 구할 때 사용 같은 가중치를 가진 그래프에서 사용 큐(queue)를 사용하여 구현 ※ 중요한 점은 방문한 정점은 다시 방문하지 않아야 한다. 만약 가중치가 다른 그래프일 때 최단거리를 구하는 알고리즘은 다익스트라, 벨만포드 등으로 구현해야 한다.. 2023. 6. 17. 큐(Queue) ✔ 큐(Queue) 큐도 스택과 마찬가지로 알고리즘보단 자료 구조에 해당하고 컴퓨터에서 많이 사용되는 자료 구조이다. 큐는 먼저 집어넣은 데이터가 먼저 나오는 선입선출(FIFO: First In First Out) 구조로 저장하는 형식을 말한다. 즉, 가장 처음에 넣은 값이 먼저 나오는 것을 FIFO 구조라고 한다. 나중에 넣은 값이 먼저 나오는 스택과는 반대되는 개념이다. 쉬운 예시로 파이프 혹은 드라이브 스루를 생각하면 된다. 드라이브 스루는 가장 먼저 들어가는 사람이 먼저 주문을 하게 되고 그 뒤로 차례로 줄을 서게 된다. 먼저 들어간 사람이 주문을 끝내고 가지 않는 이상 그 뒤로는 계속 기다려야 하는 구조이다. 이 구조가 큐 자료 구조에 해당한다. ✔ 큐의 연산 큐는 양쪽이 뚫려 있는 구조로 한쪽.. 2023. 5. 2. 스택(Stack) ✔ 스택(Stack) 스택은 알고리즘보단 자료 구조에 해당하고 컴퓨터에서 아주 많이 사용되는 자료 구조이다. 스택은 제한적으로 접근할 수 있는 나열 구조로 한쪽 끝에서만 자료를 넣고 뺄 수 있는 후입선출(LIFO : Last-In First-Out) 구조이다. 즉, 가장 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다. 쉬운 예시로 프링글스 과자를 생각하면 된다. 프링글스 과자를 포장할 때 처음 과자가 통 맨 밑으로 들어가게 되고 그다음부터 위로 쌓이게 되고 구매자는 과자를 먹을 때 통 맨 위에서부터 하나씩 꺼내서 먹게 된다. 이 구조가 스택 자료 구조에 해당한다. ✔ 스택의 연산 스택은 가장 윗부분을 "top"이라 명칭 한다. top(): 스택의 가장 윗 데이터를 반환 pop(): 스택의 가.. 2023. 4. 15. 합병 정렬 알고리즘(Merge Sort) ✔ 합병 정렬(Merge Sort) 합병 정렬은 퀵 정렬과 마찬가지로 분할 정복(divide and conquer) 방법을 통해 정렬하는 알고리즘이다. 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할한다. (한 원소만 든 리스트는 정렬된 것) 분할한 부분리스트를 반복해서 비교하며 병합하여 정렬된 리스트로 만든다. 합병 정렬은 분할, 정복, 결합, 복사의 순으로 이루어진다. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 리스트의 길이가 1 이하일 때까지 반복한다. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한.. 2023. 1. 10. 퀵 정렬 알고리즘(Quick Sort) ✔ 퀵 정렬(Quick Sort) 퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 정렬하는 알고리즘이다. 간단히 얘기하면, 하나의 원소를 기준으로 기준 앞은 작은 모든 원소들이 오고, 뒤에는 큰 모든 원소들이 오도록 리스트를 둘로 분할하여 정렬하는 방법이다. 정렬하려는 리스트 가운데서 하나의 원소를 고른다. 고른 원소를 Pivot(피벗)이라 부른다. 피벗 기준 앞에서 큰 값을 찾고, 기준 뒤에는 작은 값을 찾아 교환하면서 피벗 앞에는 작은 원소들이 오게 하고 뒤에는 큰 원소들이 오도록 정렬을 진행한다. 분할 정복(divide and conquer) 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법 ✔ 퀵 정렬 동작 과정 왼쪽 → 오른쪽 순으로 봐주시기 바랍니다.. 2022. 12. 14. 삽입 정렬 알고리즘(Insertion Sort) ✔ 삽입 정렬(Insertion Sort) 삽입 정렬은 적절한 위치에 삽입하여 정렬하는 알고리즘입니다. 삽입 정렬은 리스트의 두 번째 인덱스부터 시작해서 자기 기준의 왼쪽으로 비교하면서 정렬합니다. 또한, 자기 기준 왼쪽 부분은 정렬된 상태라 가정이 되기 때문에 적절한 위치를 파악할 수 있습니다. 예를 들면 [1, 2, 5, 4]인 리스트가 있을 때 현재 세 번째까지 정렬이 완료된 상태고 오름차순이라 가정하겠습니다. 네 번째와 자기 기준 왼쪽 값을 비교해서 자리를 변경하고, 다시 두 번째와 비교를 하지만 두 번째가 더 작기 때문에 변경이 발생하지 않습니다. 그리고 첫 번째는 이미 정렬된 상태여서 더 작은 값이기 때문에 아무 일도 일어나지 않습니다. 그래서 선택, 버블, 삽입 정렬 중에는 가장 적은 연산 .. 2022. 11. 30. 버블 정렬 알고리즘(Bubble Sort) ✔ 버블 정렬(Bubble Sort) 버블 정렬은 구현이 간단하지만 가장 비효율적인 알고리즘입니다. 버블 정렬은 바로 옆에 있는 두 원소를 비교하면서 정렬하는 알고리즘입니다. 오름차순일 경우, 두 원소를 비교해서 작은 값을 앞으로 보내고 큰 값을 뒤로 보내 가장 큰 값이 맨 뒤로 가면서 뒤에서부터 정렬이 완료되는 방법입니다. 내림차순일 경우, 두 원소를 비교해서 큰 값을 앞으로 보내고 작은 값을 뒤로 보내 정렬이 됩니다. ✔ 버블 정렬 동작 과정 왼쪽 → 오른쪽 순으로 봐주시기 바랍니다. 리스트의 첫 번째 인덱스를 교환(Swap) 대상으로 선정하고, 가장 가까운 두 번째 인덱스를 비교해서 교환 대상의 값이 더 크면 위치를 교환하고, 더 크지 않으면 넘어갑니다 리스트의 두 번째 인덱스를 교환(Swap) 대.. 2022. 11. 21. 선택 정렬 알고리즘(Selection Sort) ✔ 선택 정렬(Selection Sort) 선택 정렬은 가장 원시적이고 기초적인 방법 중 하나입니다. 선택 정렬은 이름 그대로 선택한 값을 제일 앞으로 보내서 정렬하는 알고리즘이다. 선택한 값이란 오름 차순일 경우 최솟값을 얘기하고, 내림 차순일 경우 최댓값을 얘기한다. ✔ 선택 정렬 동작 과정 리스트의 첫 번째 인덱스를 교환(Swap) 대상으로 선정하고, 교환 대상과 교환 대상 이후의 리스트를 전체 비교하면서 최솟값을 찾은 후 교환 대상과 최솟값의 위치를 교환(Swap) 첫 번째 인덱스는 정렬된 상태이기 때문에 고정. 두 번째 인덱스를 교환(Swap) 대상으로 선정하고, 첫 번째 인덱스를 제외한 전체 리스트를 비교하면서 최솟값을 찾은 후 교환 대상과 최솟값의 위치를 교환(Swap) 정렬이 완료될 때까지.. 2022. 11. 9. [Algorithm] 소수 구하기 ✔ 에라토스테네스의 체 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. ✔ 알고리즘 에라토스테네스의 체 방식은 위와 같이 2부터 시작해 해당 배수의 값을 지워 나가면 된다. 에라토스테네스의 시간 복잡도는 O(nloglogn) 이다. 사실 O(nloglogn)이 어느 정도인지 모르겠다... 다만, O(n)인 선형 알고리즘보다 빠르다고 생각하고 있다. 배수의 값을 미리 지우기 때문이라고 생각한다.(DP 느낌? 👀) #include #include using namespace std; int main() { int n=120, cnt=0; vector v(n+1, 1); for(int i=2; i*i 2022. 4. 5. [Algorithm] 알고리즘 읽기와 분석(시간복잡도) ·코딩 테스트를 준비하면서 지금까지 알고리즘 문제를 풀 때 시간 복잡도/공간 복잡도 등에 대해서는 생각을 안 하고, 문제를 읽고 해당 문제의 조건으로 구현해서 제출하고 맞으면 다른 사람의 풀이 보고 넘어가고 틀리면 "왜 틀렸지?"라고 막연히 생각만 했었다. 그러다 좋은 강의로 인해 시간복잡도 등 분석에 대해서 알게 되어서 기록 및 공유하고자 한다. 먼저 시간 복잡도에 대해서 간단히 얘기하면, 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 시간 복잡도는 주로 빅-오 표기법을 사용하여 나타내며, 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. $$ O(N!) > O(2^N) > O(N^2) > O(NlogN) > O(N) > O(\sqrt{N}) > O(logN).. 2022. 3. 16. 하노이 탑 이동 순서 ✔ 하노이 탑 하노이의 탑에는 크기가 다른 원반이 n개 있고 원반을 끼울 수 있는 기둥이 세 개 있다. 하노이의 탑 문제는 어떻게 하면 원반 n개를 모두 가장 왼쪽 기둥(출발점, 1번 기둥)에서 오른쪽 기둥(도착점, 3번 기둥)으로 옮길 수 있을까 하는 문제이다. ※ 하노이 탑 규칙 - 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. - 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력. 단, 이동 횟수는 최소가 되어야 한다. ✔ 하노이 탑 풀이 원반이 3개일 때 원반 전체를 'C'로 옮기려면, 3원반이 'C'로 먼저 옮겨져야 하니깐, 1,2원반이 'B'로 옮겨져야 한다. 그러면 위와 같이 3원반을 'C'로 옮길 수 있다. 이제 'B'에 .. 2021. 4. 12. 이전 1 2 다음
