알고리즘6 퀵정렬(Quick Sort) 설명 최근 알고리즘 문제를 다시 풀어보며 까먹었던 정렬 알고리즘들에 대해서 복습하는 시간을 가졌었다.그중 가장 애용하고 있는 정렬인 퀵정렬에 대해서 설명해보고자 한다. 퀵정렬 작동 방식퀵정렬의 작동 방식은 의외로 간단하다.어찌보면 선택 정렬과도 유사하다. (선택 정렬은 추후에 다룰 예정이다.)하지만 퀵정렬은 재귀적인 방식을 채택한다.그리고 퀵정렬은 크게 3가지 단계를 거치는데분할(Divide) : 정렬할 배열을 2~1개의 칸으로 나눈다. 정렬할 구역은 2개로 이루어진 칸이다.정복(Conquer) : 나눠진 배열을 부분 배열이라 말하며, 부분 배열을 정렬한다.결합(Combine) : 정렬된 배열을 다시 하나의 배열에 결합한다. 그리고 가끔 알고리즘 문제에서 순서에 민감한 문제들이 있다.이런 문제들에서는 퀵정렬을.. 2025. 5. 26. Graph에 대해서 그래프는 알고리즘에서 자주 나오고 또 중요한 자료구조입니다.최단거리를 찾는 다익스트라 알고리즘이나 특정 지점을 탐색하는 DFS, BFS가 대표적입니다. 서론은 짧게 하고, 본론으로 들어가겠습니다. Graph란 무엇인가?그래프는 정점과 간선로 이루어진 구조라고 할 수 있습니다.여기서 정점은 보통 node, vertex라고 부르며 간선은 edge라고 부릅니다.*주의할 점 : 간선이 존재하지 않으면 그래프가 아닙니다. 그래프를 시각적으로 보자면 이렇습니다. A, B, C라는 3개의 노드와 3개의 간선으로 이루어진 간단한 그래프입니다.후에 설명드릴 내용으로 조금 더 자세히 설명해 드리자면 이 그래프는 무방향 그래프로 방향성이 존재하지 않는 그래프입니다. 바로 다음으로 넘어가도 되지만 그래프의 잘못된 예도 .. 2025. 3. 23. BFS (Breadth First Search) 너비 우선 탐색 설명 BFS는 DFS와 같이 탐색을 주로하는 알고리즘입니다.이와 관련한 설명은 DFS 설명할 때 같이 했으니 보고오시는 것을 추천드립니다.https://ris-blog.tistory.com/22 DFS (Depth First Search) 깊이 우선 탐색 설명DFS는 우선 제목에 나와있듯이 '탐색'하는 알고리즘입니다.고로 이는 순서가 있는 혹은 방향이 있는 자료구조에서 쓰이며이는 선형 자료구조라고 합니다. 우선 DFS의 탐색 과정을 봅시다.위의 사ris-blog.tistory.com 바로 BFS의 작동 순서를 표시하겠습니다.노드 안의 숫자는 순서를 나타냅니다.이 그림에서 DFS와 BFS의 차이가 나타납니다.DFS는 하나의 노드를 끝까지 탐색한다면 BFS는 각 노드를 한번씩 탐색합니다.이해를 돕기위해 예를 들자.. 2024. 11. 2. DFS (Depth First Search) 깊이 우선 탐색 설명 DFS는 우선 제목에 나와있듯이 '탐색'하는 알고리즘입니다.고로 이는 순서가 있는 혹은 방향이 있는 자료구조에서 쓰이며이는 선형 자료구조라고 합니다. 우선 DFS의 탐색 과정을 봅시다.위의 사진은 DFS의 작동 순서를 매우 간단히 표현한 그래프입니다.화살표를 신경쓰기보다는 노드의 숫자를 보시면 좋습니다.노드의 숫자는 순서를 의미합니다. 고로 DFS의 원리를 정리하자면연결된 노드들 중 하나를 골라 그 노드에서 계속 탐색하고 탐색되지 않은 노드는 따로 처리하는 것입니다. 이를 코드로 구현하면 아래처럼 됩니다.*코드에서는 연결요소(connected component)를 구합니다.주석 On, m = map(int ,input().split()) # n : node, m = 간선visited = []graph =.. 2024. 11. 2. 이전 1 2 다음
