분류 전체보기137 [집합] 개념 정리 (Feat. 유니온-파인드 알고리즘) 집합 개념 유니온-파인드 알고리즘 유니온-파인드 알고리즘 구현파인드 알고리즘 (부모 노드를 찾기!)현재 노드에서 부모 노드를 확인합니다. 부모 노드가 루트 노드이면 파인드 연산을 종료합니다.파인드 연산이 종료되지 않았다면, 위 과정을 반복합니다. 유니온 알고리즘 (랭크 기반으로 합치기!)두 노드의 루트 노드를 확인합니다.루트 노드의 랭크를 비교합니다.랭크 값이 다르면, 랭크 값이 큰 루트 노드를 기준으로 삼아, 랭크가 더 큰 노드를 랭크가 작은 루트 노드의 부모 노드로 바꿉니다. 트리의 깊이는 더 깊어지지 않기 때문에, 랭크 값은 변하지 않습니다.랭크 값이 같다면, 루트 노드를 아무거나 선택해서 바꾸고 최종 루트 노드의 랭크에 1을 더합니다. """[간단한 유니온-파인드 알고리즘 구현하기]상호배타적 집합.. 2025. 4. 9. [그리디] 개념 정리 및 활용 사례 (Feat. 최소 신장 트리 & 배낭 문제) 그리디 개념그리디는 '탐욕스러운'이라는 영단어 뜻처럼, 문제 해결 과정에서 결정하는 순간마다 눈 앞에 보이는 최선의 선택을 하는 알고리즘을 말합니다. 이러한 특성으로 인해 '지역 최적해를 추구한다'고 생각할 수 있습니다. 그리디 알고리즘은 부분적으로는 최적해, 전체적으로는 최선의 해를 구합니다. 그리디 알고리즘은 아래 2가지와 같은 특정 상황에서 최적해를 보장합니다. 1. 최적 부분 구조 : 부분해를 푸는 과정이 최적해를 구하는 과정과 일치2. 그리디 선택 속성 : 선택 과정이 다른 과정에 영향을 주지 않음 위 조건을 만족하는 경우, 최적해를 도출하지만,조건을 만족하지 않는 경우, 현재의 최적의 결정이 이후 선택에 제약이 될 수 있으므로,항상 최적해를 도출하지 못한다는 한계가 있습니다. 그리디 알고.. 2025. 4. 8. [프로그래머스] 게임 맵 최단거리 (Python) - BFS 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 코드 구현# 거리의 최적값 = 너비 우선 탐색 (BFS)from collections import dequedef solution(maps): # 상하좌우 이동 방향 moves = [[-1,0],[1,0],[0,-1],[0,1]] # 게임 맵의 행/열 n = len(maps) m = len(maps[0]) # 거리를 저장하는 배열 dist를 -1로 초기화 dist = [[-1]*m for.. 2025. 4. 7. [프로그래머스] 네트워크 (Python) - DFS 문제 설명https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 위 문제의 경우, 모든 경우의 수를 탐색하기 때문에, DFS 알고리즘을 선택했습니다. 코드 구현from collections import defaultdictdef dfs(computers, visited, node): visited[node] = True for idx, connected in enumerate(computers[node]): # 연결되어있는데 방문하지 않은 노드일 경우 if co.. 2025. 4. 7. [그래프] 깊이 우선 탐색 (DFS) DFS 소개그래프는 노드와 간선을 이용한 비선형 데이터 구조입니다. 깊이 우선 탐색(Depth First Search)는 시작 노드부터 탐색을 시작하여, 간선을 따라 최대 깊이 노드까지 이동하며 차례대로 방문하는 알고리즘 입니다. 최대 깊이 노드까지 방문한 이후, 이전에 방문한 노드를 거슬러 올라가며 해당 노드와 연결된 노드 중 방문하지 않은 노드로 다시 최대 깊이까지 차례대로 방문합니다. DFS 알고리즘은 가장 깊은 곳을 우선하여 탐색하고, 더 이상 탐색할 수 없으면 백트래킹하여 최근 방문 노드부터 다시 탐색한다는 특징이 있어, 모든 가능한 해를 찾는 백트래킹 알고리즘을 구현할 때나 그래프의 사이클을 감지해야 하는 경우 활용할 수 있습니다. 알고리즘 동작 방식 깊이 우선 탐색은 재귀를 활용한 시스템 .. 2025. 4. 7. [그래프] 너비 우선 탐색 (BFS) BFS 소개그래프는 노드와 간선을 이용한 비선형 데이터 구조입니다. 너비 우선 탐색(Breadth First Search)은 시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘 입니다. 여기서 거리는 시작 노드와 목표 노드까지의 차수를 말합니다. BFS 알고리즘은 루트 노드에서 가까운 노드부터 탐색하므로, 가중치가 없는 그래프에서 최단 경로를 보장합니다. 알고리즘 동작 방식BFS는 주로 큐를 이용해 구현합니다. 일단 시작 노드를 정하고, 큐에 시작 노드를 푸시합니다.시작 노드를 큐에 푸시하면서, 방문 처리를 합니다.큐에 있는 노드는 이미 방문 처리했고, 그 노드와 인접한 노드는 아직 탐색하지 않은 상태입니다.이후, 큐가 비어있는지 확인합니다.큐가 비었다면, 방문할 수 있는 모든 노드.. 2025. 4. 7. 이전 1 2 3 4 ··· 23 다음
