본문 바로가기

Algorithm202

프로그래머스 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.
프로그래머스 Level 4 - 게임 맵 최단거리 문제 프로그래머스 - 게임 맵 최단거리 풀이 과정 BFS 를 통해 목표지점까지의 최단 거리를 탐색하는 문제이다. 방문여부와 거리 정보를 저장히기 위해서 딕셔너리 자료형을 사용할수도 있지만 게임맵과 동일한 이차원 배열을 선언해서 -1일 경우는 아직 방문하지 않은 지점, 그 외의 경우는 이미 방문해서 최단 경로를 구한 지점으로 판단하도록 했다. 이렇게 하면 트리 탐색시간을 절약할 수 있어서 더 빠른 수행시간을 가지게 된다. 코드 from collections import deque dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def bfs(maps, start): N, M = len(maps), len(maps[0]) q = deque() dist = [[-1 for _ in rang.. 2021. 3. 1.

티스토리툴바