코딩 테스트39 [프로그래머스] 섬 연결하기 (Python) - 유니온 파인드 알고리즘 문제 설명https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 코드 구현# 실패 - 사이클을 감지하지 못함대표 예시는 통과했지만, 막상 제출하고 보니 대부분의 테스트 케이스를 통과하지 못한 저의 첫 번째 풀이입니다. 어디서부터 잘못됐는지 확인하기 위해 문제를 다시 읽어보니, 이 코드로는 사이클을 감지하지 못한다는 점을 깨달았습니다. 처음에는 최소 비용만을 고려한 단순한 트리 문제라고 생각했지만, 본질은 최소 신장 트리(MST)였던 것이죠. def solution(n, costs): ans.. 2025. 4. 10. [집합] 개념 정리 (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. 이전 1 2 3 4 ··· 7 다음
