Computer Science/Algorithem (10) 썸네일형 리스트형 📌유니온 파인드(Union-Find)를 알아보자 (이코테 WITH 파이썬) 어젯밤 알고리즘 스터디 모의 코테 중 못 푼 문제가 있는데 검색해보니 유니온 파인드로 푼다고 했다. 유니온 파인드가 뭔지 알아보고 못 풀었던 백준 문제도 풀어보겠다😇 유니온 파인드 우선 서로소 집합(Disjoint Sets)에 대해 알아야 한다. 서로소 집합은 공통 원소가 없는 두 집합을 말한다. 서로소 집합 자료구조는 서로소 부분 집합들로 나누어진 데이터를 처리하기 위한 자료구조이며, union과 find 연산으로 조작할 수 있기 때문에 유니온 파인드 자료구조라 불리기도 한다. union: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 find: 특정 원소가 어느 집합에 포함되어있는지 찾는 연산 유니온 파인드 알고리즘은 서로소 집합을 표현하기 위한 알고리즘이다. 이를 통해 각 집합이 어떤 원.. 📌다익스트라 최단 경로 알고리즘 (이코테 WITH 파이썬) 이번달 코딩테스트 중에서 이거 딱 다익스트라인데 하면서 못 푼 문제가 있었다. 끝나고 후기를 찾아보니 정말 다익스트라로 풀 수 있는 문제여서 아쉬웠던 기억이 있다. 이참에 다익스트라 알고리즘을 복습해보자. 최단 경로 알고리즘 말 그대로 가장 짧은 경로를 찾는 알고리즘. 그래프를 이용해 표현하며 각 지점은 노드로, 지점간의 연결은 간선으로 표현한다. 다익스트라 알고리즘 다익스트라 알고리즘은 그래프의 여러개의 노드가 있을 때 특정한 노드에서 출발해 다른 노드로 가는 각각의 최단경로를 구하는 알고리즘이다. 과정은 다음과 같다. 출발 노드 설정 > 최단 거리 테이블 초기화 > 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택 > 해당 노드에서 부터 다른 노드로 가는 거리를 계산한 후 테이블 갱신 > 반.. 알고리즘 | 재귀 ✔ 학습목표 함수를 재귀적으로 사용하는 코드를 작성할 수 있다. 재귀 동일한 작업을 반복할 때는 사용자 정의 함수를 사용하면 보다 효율적으로 코드를 만들 수 있다고 배웠다. 하지만 함수 내에서 동일한 작업이 반복되는 경우에는 어떻게 해야 할까. 본 글에서는 함수를 함수 내에서 재사용하는 방법, 즉 재귀적으로 호출하는 방법을 공부한다. 우리는 이제껏 int main(void){}안에서 프로그램을 작성하고 함수를 호출했다. 그런데 생각해보면 main()도 역시 함수이다. 함수 안에서 또 다른 함수를 사용해온 것이다. 이 사실을 알게 되면 함수가 본인 스스로를 호출해서 사용할 수 있는지에 대한 의문이 생긴다. 답은 할 수 있다 이다. 이를 재귀(Recursion)라고 한다. # ## ### #### #####.. 알고리즘 | 병합 정렬 ✔ 학습목표 재귀를 활용한 병합 정렬을 구현할 수 있다. 병합 정렬 병합 정렬(merge sort)은 원소가 한 개가 될 때까지 계속해서 나누다가 다시 합쳐가며 정렬을 하는 방식이다. 합병 정렬이라고도 한다. 이는 분할 정복(divide and ) 알고리즘의 하나이다. 분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음 결과를 모아 원래의 문제를 해결하는 전략이다. 병합 정렬의 단계 병합 정렬은 세 단계로 이루어진다. 1) 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 2) 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할한다. 3) 결합(Combine): 정렬된 부분 배열들을 하나의 배열로.. 알고리즘 | 정렬 알고리즘의 실행시간 ✔ 학습목표 1. 여러 정렬 알고리즘과 검색 알고리즘의 실행 시간을 Bio O와 Big Ω로 정의할 수 있다. 2. 조건문을 사용해 좀 더 효율적인 알고리즘을 만들 수 있다. 알고리즘의 실행 시간 이제껏 배운 선형 검색(Linear search), 이진 검색(Binary search), 버블 정렬(Bubble sort), 선택 정렬(Selection sort)의 실행시간(시간 복잡도)은 각각 어떻게 되는지 정리해보자. 상한은 다음과 같다. O(1) O(log n) O(n) O(n log n) O(n^2) Linear search o Binary search o Bubble sort o Selection sort o 하한은 다음과 같다. Ω(1) Ω(log n) Ω(n) Ω(n log n) Ω(n^2) L.. 알고리즘 | 선택 정렬 ✔ 학습목표 선택 정렬의 원리와 실행 시간을 설명하고 구현할 수 있다. 선택 정렬 선태 정렬(selection sort)은 버블 정렬과 마찬가지로 정렬을 위한 알고리즘 중 하나이다. 선택 정렬에서는 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환한다. 넣을 위치는 이미 정해져있고, 어떤 수를 넣을지 선택한다는 게 특징이다. 선택 정렬은 아래와 같은 의사 코드로 나타낼 수 있다. For i from 0 to n–1 Find smallest item between i'th item and last item Swap smallest item with i'th item 이해를 위해 간단한 GIF를 보자. 선택 정렬은 버블 정렬과 달리 교환 횟수가 .. 알고리즘 | 버블 정렬 ✔ 학습목표 버블 정렬의 원리와 실행 시간을 설명하고 구현할 수 있다. 정렬 어떤 배열이 주어졌을 때, 그 배열이 미리 정렬되어 있다면 훨씬 빠른 속도로 검색이 가능하다. 정렬하기 위한 방법은 여러 가지가 있으며 각각의 효율성도 다르다. 이번 글에서는 그중 하나인 버블 정렬에 대해 공부한다. 버블 정렬 버블 정렬(bubble sort)은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말한다. 마치 거품이 터지면서(서료 비교 및 교환하면서) 위로 올라가는(옆으로 이동하는) 것처럼 말이다. 이는 접근법이 간단하다는 장점이 있지만, 자칫하면 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다. 버블 정렬은 아래와 같은 의사 코드로 나타낼 수 있다. Repe.. 알고리즘 | 선형 검색 ✔ 학습목표 주어진 배열 또는 구조체에서 선형 검색(linear research)을 할 수 있다. 1) 선형 검색 자료를 검색하는 데는 다양한 알고리즘이 사용될 수 있다. 우리는 그 예시로 선형 검색과 이진 검색을 배웠다. 선형 검색은 원하는 원소가 발견될 때까지 순서대로 보는 방법이다. 본 글에서는 주어진 배열에서 선형 검색으로 값을 찾는 방법을 배운다. 효율성 선형 검색은 정확하지만 효율적이지 못한 방법이다(알고리즘 표기법에서 배운 대로 시간의 상한선이 O(n)이다). 이는 자료가 정렬되지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에만 유용하다. * 참고로 검색에 앞서 정렬이 필요한 이유가 이것이다. 정렬은 시간이 오래 걸리고 공간을 많이 차지하지만 매우 큰 데이터를 다룰 경우 시간을 단축.. 이전 1 2 다음
