개발지식 아카이브/Algorithms
-
[해커랭크 HackerRank] DP 알고리즘 Max Array Sum개발지식 아카이브/Algorithms 2019. 11. 3. 21:41
문제 자연수 행렬이 주어질 때, 비인접하는 원소의 행렬들을 구하고, 그원소들의 최대합을 구하라. 예를 들어, arr = [-2, 1, 3, -4, 5] 라는 행렬이 주어졌을 때 존재할 수 있는 비인접 원소 행렬들은 아래와 같다. SUBSET | 합 [-2, 3, 5] 6 [-2, 3] 1 [-2, -4] -6 [-2, 5] 3 [1, -4] -3 [1, 5] 6 [3, 5] 8 [3, 5] 행렬이 가장 큰 합인 8을 가지므로, 8을 return 한다. 풀이 k번째 원소를 포함하고 있는 비인접행렬은 아래의 경우들이다. (A) k-2번째에 존재할 수 있는 모든 비인접행렬에 arr[k]를 더해준 것 tip: 최대합을 구하는 문제이므로 단순히 k-2번째에 존재하는 비인접행렬의 최댓값에 arr[k]를 더해주면 그..
-
[해커랭크 HackerRank] 배열 문제 Minimum Swaps 2개발지식 아카이브/Algorithms 2019. 10. 30. 21:32
Minimum Swaps 연속하는 자연수로 된 배열을 input으로 주고, 안의 원소들을 서로 교환해서 정렬시킬 때, 가능한 가장 적은 교환 횟수를 구하는 문제이다. [7, 1, 3, 2, 4, 5, 6] 이라는 arr 배열을 입력받았을 때, arr[0] 과 arr[3]를 자리 교환, (i=0 에서 7과 2가 자리를 바꾸었다) arr[0] 과 arr[1]를 자리 교환, ...., 최종적으로 arr[5], arr[6]을 자리 교환하여 [1, 2, 3, 4, 5, 6, 7] 으로 정렬이 완료되었다. 정렬 되기까지의 최소 교환 횟수는 5번으로, 5를 리턴한다. 풀이법 원소가 제 자리에 있는지 확인할 때에는 인덱스로 확인하면 된다. 배열에서 인덱스 i에 대해, i+1 == x[i] 를 만족한다면 그 원소는 제 ..