알고리즘, 자료구조15 서로소 집합(Disjoint Sets) [Python / 파이썬] 1. 서로소 집합이란? 수학에서 서로소 집합(Disjoint Sets)이란 공통 원소가 없는 두 집합을 의미한다. 예를 들어 집합 {1, 2}와 {3, 4}는 서로소 관계이다. 반면 집합 {1, 2}와 {2, 3}은 2라는 원소가 두 집합에 공통적으로 포함되어 있기 때문에 서로소 관계가 아니다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 서로소 집합 자료구조는 union과 find 2개의 연산으로 조작할 수 있다. union 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. 서로소 집합 자료구조를 구현할 때는 트리 자료구조를 이용하여 집합을 표현한다. .. 2022. 1. 14. 삽입 정렬 [Python / 파이썬] 1. 삽입 정렬(Insertion Sort) 삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입 정렬(Insertion Sort)라고 부른다. 더불어 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징이다. 삽입 정렬은 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘으로 잘 알려져 있다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적이다. 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다. 선택 정렬 2022... 2022. 1. 6. 선택 정렬 [Python / 파이썬] 보통 정렬부터 공부하면 알고리즘의 효율성을 쉽게 이해할 수 있어 알고리즘 개론서 초반에 정렬 알고리즘을 설명하는 경우가 많다. 또한 일반적으로 문제에서 요구하는 조건에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 상황에 적절하지 못한 알고리즘을 이용하면 당연히 프로그램은 비효율적으로 동작하며 필요 이상으로 시간을 많이 소요한다. 그래서 알고리즘의 기초인 정렬 알고리즘을 통해 알고리즘 효율성의 중요성을 깨닫고자 글을 작성해보려 한다. 1. 선택 정렬(Selection Sort) 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하면 어떨까? 이 방법은 가장 원시적인 방법으로.. 2022. 1. 6. 구간 합 계산 [Python / 파이썬] 1. 구간 합 계산 백준이나, 프로그래머스 문제를 풀다보면 구간 합을 구해야 하는 문제가 종종 출제된다. 구간 합 문제란 연속적으로 나열된 N 개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 문제를 말한다. 예를 들어 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정해보자. 여기에서 두 번째 수부터 네 번째 수까지의 합은 20 + 30 + 40으로 90이 될 것이다. 이러한 구간 합 계산 문제는 여러 개의 쿼리로 구성되는 문제 형태로 출제되는 경우가 많다. 다수의 구간에 대해서 합을 각각 구하도록 요구된다. 예를 들어 M개의 쿼리가 존재한다고 가정해보자. 각 쿼리는 Left와 Right로 구성되며, 이는 [Left, Right]의 구간을 의미한다. 결과적으로 .. 2022. 1. 5. 이전 1 2 3 4 다음
