[Python] 서로소 집합(disjoint set) 알고리즘 알아보기

서로소 집합 개념 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다.아래의 그림으로 예시를 알아보자(가)에서는 집합이 총 2개가 있으며, {1, 2}와 {3, 4}의 원소를 갖고 있다. 두 집합에서 원소가 겹치는 경우가 없기 때문에, 서로소 관계라고 할 수 있다. 반면, (나)의 경우, {1, 2, 4}, {3, 4}의 두 집합이 있으며, 4라는 원소가 두 집합에 공존하고 있기 때문에 서로소 집합 관계가 아니라고 할 수 있다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.이 때, 서로소 집합 자료구조는 union과 find의 2개의 연산으로 조작할 수 있다. 연산 명작동 방식union두 집합을 하나의 집합으로 합치는 연산find특정한 원소가 속한 ..

• format_list_bulleted CodingTest/algorithm
• · 2025. 2. 10.
• textsms

플로이드 워셜 알고리즘 (Floyd-Warshall) 개념 및 예시코드

모든 지점에서 모든 지점까지의 최단 경로를 구하는 플로이드 워셜 알고리즘플로이드 워셜 알고리즘은 모든 노드 쌍 간의 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘이 단일 시작점에서 출발하여 다른 모든 노드로의 최단 경로를 구하는 반면, 플로이드 워셜 알고리즘은 모든 노드 쌍에 대해 최단 경로를 구할 수 있다는 점에서 차이가 있다.이 알고리즘은 다이나믹 프로그래밍을 활용하며, 단계마다 특정 노드를 중간 노드로 거쳐가는 경우를 고려하여 경로를 갱신한다. 이 과정에서 2차원 리스트를 이용해 모든 경로의 최단 거리를 저장한다.시간복잡도는 (O(N^3))이며, 노드의 개수가 많아질수록 처리 시간이 급격히 증가하는 특징이 있다.플로이드 워셜 알고리즘 동작 방식알고리즘은 크게 다음과 같은 단계로 이루어진다.그..

• format_list_bulleted CodingTest/algorithm
• · 2025. 1. 10.
• textsms

코딩테스트 필수 알고리즘 및 개념 정리

코딩 테스트를 준비하기 위해 반드시 공부해야 하는 주요 알고리즘을 정리한다. 다음은 주요 알고리즘과 그 개념, 그리고 사용되는 상황에 대한 설명이다.1. 정렬 알고리즘정렬은 데이터를 특정 순서대로 배열하는 작업이다. 대표적인 정렬 알고리즘으로는 버블 정렬, 삽입 정렬, 선택 정렬, 병합 정렬, 퀵 정렬 등이 있다. 정렬은 배열을 정리하거나 탐색 효율성을 높이기 위해 사용된다.버블 정렬: 인접한 두 요소를 비교하여 정렬한다. 시간 복잡도는 O(n^2)이다.삽입 정렬: 정렬된 부분과 정렬되지 않은 부분으로 나눠 하나씩 삽입하며 정렬한다. 시간 복잡도는 O(n^2)이다.퀵 정렬: 기준점을 잡고 이를 기준으로 작은 값과 큰 값을 분리하여 재귀적으로 정렬한다. 평균 시간 복잡도는 O(n log n)이다.2. 탐색..

• format_list_bulleted CodingTest/algorithm
• · 2024. 12. 22.
• textsms

부분수열의 합을 구하는 알고리즘 정리 - 완전탐색, 백트래킹, DP, 비트마스크 비교 (Python)

부분수열의 합을 구하는 알고리즘: 다양한 접근 방법부분수열의 합을 구하는 문제는 기본적인 문제 중 하나이다.주어진 배열에서 가능한 모든 부분수열의 합을 구하거나, 특정 목표 합을 만족하는 부분수열을 찾는 것이 주 목적이다.이를 해결하기 위해 다양한 알고리즘들이 존재하며, 각각의 장단점이 있다. 이번 글에서는 부분수열의 합을 구하는 네 가지 대표적인 알고리즘- 완전 탐색, 백트래킹, 동적 계획법, 비트마스킹 - 을 정리해 보겠다.문제 정의우리가 풀고자 하는 문제는 다음과 같다. 정수 배열 arr이 주어졌을 때, 가능한 모든 부분수열의 합을 계산하거나 특정 조건을 만족하는 부분수열의 합을 찾는 것이다. 예를 들어, 배열 [1, 2, 3]이 주어진다면 가능한 부분수열의 합은 {0, 1, 2, 3, 4, 5, ..

• format_list_bulleted CodingTest/algorithm
• · 2024. 11. 27.
• textsms

[DP] Dynamic Programming 알고리즘 알아보기

오늘은 거두절미하고, DP(Dynamic Programming) 알고리즘에 대해서 알아보고자 한다.여기서 설명하는 DP 알고리즘은 동적 할당과는 다른 개념이므로, 착각하지 말자동적할당은 메모리 공간에 동적으로 (런타임에) 변수 공간을 할당한다는 개념이며,동적이라는 것 자체가 프로그램이 실행되는 런타임에 발생한다는 것을 이해하면 된다. DP 알고리즘을 설명할 때 주로 피보나치 수열을 예시로 들곤 한다.피보나치 수열은 특정 점화식으로 반복되는 수열을 의미한다.점화식은 아래와 같다. F(n) = F(n-1) + F(n-2), 단 F(0) = 0, F(1) = 1 이러한 피보나치 수열을 코드로 구현한다면 어떨까? # 재귀를 사용한 피보나치 수열 구현def fibonacci(n): if n  코드는 매우 간..

• format_list_bulleted CodingTest/algorithm
• · 2024. 11. 10.
• textsms

파이썬 Collections 라이브러리 사용법 - deque, Counter 등

파이썬 Collections 라이브러리 자세히 알아보기 파이썬의 collections 모듈은 고급 데이터 구조를 제공하여 개발자가 다양한 상황에서 데이터를 더 쉽게 관리할 수 있도록 도와줍니다. 뿐만 아니라, 대부분의 코딩테스트에서 활용할 수 있는 모듈이기 때문에 사용법을 잘 익혀두면 많은 도움이 됩니다. 따라서 이번 글에서는 collections 모듈에 포함된 주요 클래스들에 대해 알아보고, 예제 코드와 함께 각 클래스의 사용법을 단계별로 자세히 설명하겠습니다. 1. Counter Counter는 요소의 개수를 셀 때 유용한 클래스로, 주어진 iterable 객체의 요소들을 딕셔너리 형태로 저장하면서 그 개수를 세줍니다. from collections import Count..

• format_list_bulleted Programming/Python
• · 2024. 10. 13.
• textsms