[Python] 서로소 집합을 활용하여 그래프 사이클 확인하기 (Graph Cycle)

직전에 알아봤던 서로소 집합 알고리즘은 다양한 알고리즘에서 활용될 수 있다.특히, 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다는 특징이 있다. 참고로 방향 그래프에서의 사이클 여부는 DFS로 판별할 수 있다. 서로소 집합의 연산은 find와 union으로 두가지가 있으며, 여기서 union은 그래프의 간선정보로 이해할 수 있다고 했다.따라서, 간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하는 것만으로도 사이클을 판별할 수 있다. 알고리즘의 순서는 아래와 같다. 서로소 집합을 활용한 사이클 판별 알고리즘각 간선을 활인하며 두 노드의 루트 노드를 확인한다.루트 노드가 서로 다르다면, 두 노드에 대해서 union연산을 수행한다.루트 노드가 서로 같다면..

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

[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

최단거리 다익스트라(dijkstra) 알고리즘 개념 이해 및 코드 알아보기 - Python

최단 거리 알고리즘: 다익스트라 알고리즘다익스트라(Dijkstra) 알고리즘은 특정 노드에서 출발하여 다른 모든 노드로 가는 각각의 최단 경로를 구하는 알고리즘이다. 그리디 알고리즘(탐욕법)에 기반하며, 매 단계마다 가장 비용이 적은 노드를 선택하여 과정을 반복한다. 다익스트라 알고리즘은 최단 거리 정보를 1차원 리스트에 저장하고 계속 갱신하여 최종 결과를 도출한다.다익스트라 알고리즘의 기본 동작 원리출발 노드를 설정한다.최단 거리 테이블을 초기화한다.방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.3, 4 과정을 반복한다.1. 간단한 다익스트라 알고리즘간단한 다익스트라 알고리즘은 매 단계마다 방문하지 않은..

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

[Collections] defaultdict 알아보기 - 코딩 테스트에서의 defaultdict 활용하기

Python의 defaultdict는 기본값을 자동으로 생성하는 딕셔너리로, 단순한 문제 해결뿐만 아니라 코딩 테스트에서도 매우 유용하게 사용된다. 이번 글에서는 defaultdict의 심화된 활용 방법과 코딩 테스트에서 어떤 상황에서 활용하면 좋은지 중점적으로 다룬다.1. 기본 개념 복습defaultdict는 Python의 collections 모듈에서 제공하며, 기본값 생성 함수를 설정하여 키가 존재하지 않을 때 자동으로 기본값을 생성한다. 이는 KeyError를 방지하고 코드의 가독성을 높이는 데 도움을 준다.기본 사용법from collections import defaultdictd = defaultdict(int)d['a'] += 1 # 키 'a'가 없으면 0으로 초기화한 후 1을 더함prin..

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

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

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

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