본문 바로가기

🏃 algorithm/programmers10

프로그래머스 Level 3 - 단어 변환 문제 프로그래머스 - 단어 변환 풀이 과정 시작 단어에서 목표 단어로 변형하는 최단 경로(비용)을 찾는 문제입니다. 각 단어는 최대 한 문자만 변경이 가능하고 주어진 리스트에 포함된 단어일 경우에만 해당 단어로 변환을 시도해볼 수 있습니다. 따라서 각 탐색마다 단어의 자리수를 하나씩 탐색하여 a to z 중 변환이 가능한 단어가 있는지 따져줍니다. 이때 Python 에서는 ord & chr 를 통해서 문자의 아스키코드 값을 활용할 수 있는데 문자열을 쉽게 처리하기 위해 활용하였습니다. 또한 중복된 변환을 피하기 위해 visit 은 딕셔너리로 선언하여 문자열 해싱 을 통해 이미 변환을 시도했던 단어인지 효율적으로 판단하도록 했습니다. 코드 from collections import deque def bfs.. 2021. 3. 1.

프로그래머스 Level 2 - 타겟 넘버 문제 프로그래머스 - 타겟 넘버 풀이 과정 주어진 수에 덧셈과 뺄셈을 활용해서 목표 숫자를 만드는 문제입니다. 최대 20개의 숫자를 사용하고 2가지 연산밖에 사용할 수 없으므로 최대 2^20 개의 상태를 방문하게 됩니다. 이는 대략 1000000 으로 충분히 시간 내에 수행이 가능하므로 DFS 를 활용해 모든 경우의 수를 생성하여 가능한 방법의 수를 세어줬습니다. 코드 def dfs(numbers, depth, here, target): if depth == len(numbers): return 1 if here == target else 0 ret = 0 for operand in [-numbers[depth], numbers[depth]]: ret += dfs(numbers, depth+1, here.. 2021. 3. 1.

프로그래머스 Level 3 - 네트워크 문제 프로그래머스 - 네트워크 풀이 과정 주어진 인접행렬을 기반으로 그래프 내의 컴포넌트 개수를 세는 문제입니다. 각 정점별로 DFS 탐색을 통해 방문 가능한 모든 정점을 방문해주면 해당 정점이 속한 컴포넌트를 구할 수 있습니다. 따라서 총 DFS 탐색이 몇번 수행되었는지 파악한다면 네트워크의 개수를 구할 수 있습니다. 코드 def dfs(n, adj, visit, here): visit[here] = 1 for there in range(n): if adj[here][there] and not visit[there]: dfs(n, adj, visit, there) def solution(n, computers): visit = [0 for _ in range(n)] network = 0 for v in.. 2021. 3. 1.

프로그래머스 Level 3 - 최고의 집합 문제 프로그래머스 - 최고의 집합 풀이 과정 자연수 n 개를 사용해서 총합이 S가 되며 동시에 각 원소의 곱이 최대인 집합을 최고의 집합 이라고 표현합니다. 입력으로 주어지는 합 S가 1억이고 자연수 n의 개수는 최대 10,000 이기 때문에 모든 조합을 만들어보는 방법은 시간내에 수행이 불가능합니다. 좀 더 효율적인 방법은 없을까요? 바로 탐욕적인 선택 으로 최적의 답을 구할 수 있습니다. 이를 증명하기 위해 다음과 같이 생각해봤습니다. 우선 총 k 개의 j 합이 S 를 만족한다고 가정하겠습니다. j j j ... j => 총 k 개이며 합이 S, 따라서 j\*k = S합이 S가 되는 숫자의 조합은 상당히 다양하므로 이번에는 j에 임의의 양의 정수 l 만큼 값이 차이가 나는 경우를 따져보겠습니다. j-.. 2021. 3. 1.

프로그래머스 Level 2 - 큰 수 만들기 문제 프로그래머스 - 큰 수 만들기 풀이 과정 k 개의 숫자를 제거하여 만들 수 있는 수 중에서 가장 큰 수를 찾는 문제입니다. 만약 브루트 포스 로 접근해 모든 조합을 만들어 본다면 최대 문자열의 길이 때문에 시간내에 수행이 불가능합니다. 대신에 큰 수를 구성하기 위한 조건으로 각 숫자를 탐욕적인 선택 에 따라 제거해준다면 선형 시간내에 수행이 가능합니다. 이를 위해서는 탐욕적인 선택 에 따라 우리가 절대 손해보는 일이 없음을 증명해야합니다. 어떤 숫자가 가장 큰 수가 되기 위해서는 가장 높은 자리수부터 큰 수를 가져야함은 자명합니다. 따라서 우리는 큰 자리수 부터 탐색을 수행하며 (인덱스로 따지면 0 부터) 가장 큰 수가 되기 위한 각 숫자들의 정당성을 따져도록 합니다. 어떤 수를 제거한다는 의미는 .. 2021. 3. 1.

프로그래머스 Level 3 - 섬 연결하기 문제 프로그래머스 - 섬 연결하기 풀이 과정 모든 정점을 연결하는 최소 신장 트리(MST)를 구하는 문제이다. 프림과 크루스칼 알고리즘을 활용할 수 있는데 이번에는 크루스칼을 사용했다. 크루스칼 알고리즘은 간선 정보들을 오름차순으로 정렬해준 다음, 사이클을 형성하지 않는 간선들을 탐욕적으로 선택해준다. 이를 위한 union-find 자료구조만 신경써서 구현하면 무난히 풀 수 있는 문제이다. 코드 def union(p, u, v): u, v = find(p, u), find(p, v) if u == v: return p[u] = v def find(p, u): if p[u] == u: return u p[u] = find(p, p[u]) return p[u] def kruskal(v, edges): ans.. 2021. 3. 1.

이전 1 2 다음

티스토리툴바