해당 글에서는 단어 변환 문제를 Python을 이용해 풀이하고자 한다. 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 🔷 문제 설명더보기 🔷 문제 풀이처음엔 완전 탐색을 이용해 문제를 푸려고 했다.combination을 이용해 words의 방문 순서를 정하고, 방문 순서에 따라 한 글자씩 차이나는지 아닌지를 통해 모든 경우를 탐색하고 최솟값을 찾으려고 했다. 하지만 시간초과가 발생하는 것을 확인했다. 해당 문제는 알고리즘 고득점 Kit에 있는 문제이기 때문에 카테고리가 깊이/너비 우선 탐색이라는 것을 알고 있었지만, 마땅히 풀이 방식이 떠오르지 않아서 구..
해당 글에서는 이중우선순위큐 문제를 Python을 이용해 풀이하고자 한다. 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 🔷 문제 설명더보기 🔷 문제 풀이먼저 필자가 풀이한 방식보다 더 효율성이 좋은 알고리즘이 있을 수 있다.나름은 이해하기 쉬운 코드라고 생각하여, 문제가 어려운 사람들을 위해 돕고자 글을 올린다. 해당 문제를 푸려면 min_heap과 max_heap에 대해 알아야 한다.min-heap: 부모노드 값이 자식노드의 값보다 작다.max-heap: 부모노드 값이 자식노드의 값보다 크다.즉, 큐에 삽입된 숫자들 중 최댓값, 최솟값을 구하기 위해서..
1️⃣ 신장 트리란?크루스칼 알고리즘은 '최소 신장 트리 알고리즘'이다. 즉, 최소 신장 트리를 찾기 위한 알고리즘이라는 것이다.최소 신장 트리란 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 의미한다. 크루스칼 알고리즘을 설명하기 전에 신장 트리에 대해 설명을 하고 넘어가겠다. 신장트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건에 해당한다. 따라서 이런 그래프를 신장 트리라고 부르는 것이다. 신장 트리는 동일한 그래프에서도 여러 개의 신장트리를 찾을 수 있다. 하지만 가능한 한 최소한의 비용으로 신장 트리를 찾아야 하는 상황이 존재한다.따라서 신장 ..
1️⃣ 유니온 파인드란?Union-Find는 서로소 집합을 찾는 알고리즘으로, 서로소 집합은 공통 원소가 없는 두 집합을 의미한다. 아래와 같이 루트 노드를 찾고(find), 연결된 두 노드를 합치는(union) 연산으로 이루어져 있다.def find(parent, x): # 부모 찾기 if parent[x] != x: parent[x] = find(parent, parent[x]) # 루트 노드가 아닌 경우, 재귀호출을 통해 루트 노드를 찾음 return parent[x]def union(parent, x, y): # 합치기 x = find(parent, x) y = find(parent, y) if x 2️⃣ 유니온 파인드로..
