프로그래머스 - 최고의 집합 [Python]

code 문제 문제 상황 - 총 합이 주어지고 요소의 수가 주어졌을 때 곱이 최대가 되는 집합을 찾는 문제 해결 전략 - 몇차 함수인지를 떠나 해의 개수가 늘어날 수록 자연수 범위에서 함수의 증가속도는 떨어진다. 즉, 요소의 곱은 모든 항이 다 같을 때, 가장 크면 같지 않더라도 그 차이가 적을수록 결과가 크게 된다. - 최소 요소가 1이므로 총 합은 최소 1*n = n보다 커야하므로 n > s이면 [-1]을 반환한다. - 고르게 나눠 몫을 배치하고 나머지를 1씩 배치하면 곱이 최대가 되는 집합이 된다. 코드 1 2 3 4 5 6 7 8 def solution(n, s): if n > s: return [-1] q, r = divmod(s, n) result = [q] * n for i in range(..
알고리즘 학습/프로그래머스 2020. 9. 4. 15:46
프로그래머스 - 야근 지수 [Python]

문제 문제 상황 - works에 존재하는 숫자들은 남은 업무량을 의미하고 야근 지수는 이 숫자들의 제곱의 합을 의미한다. 즉, works에 존재하는 요소들에서 n 만큼을 제거하여 각 요소의 제곱의 합을 계산한 결과가 최소가 되게 한다. 해결 전략 - works의 길이가 20,000 이므로 O(N^2)면 400,000,000(4억)의 연산이 된다. 즉 N^2는 시간 초과가 날 가능성이 높다. 최대 NlogN안에서 해결해야한다. 코드 # 성공한 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 def solution(n,works): # 요소를 다 합친 값보다 줄일 수 있는 값이 더크면 ..
알고리즘 학습/프로그래머스 2020. 9. 3. 22:21
프로그래머스 - 줄서는 방법 [Python]

문제 문제 상황 - permutation은 O(N!)의 속도를 갖기 때문에 permutation을 전부 계산하고 인덱스로 찾으면 속도 이슈가 난다. 그래서 수학적 계산을 해야한다. 해결 전략 - 먼저 (n-1)!을 기준으로 나눠 몫만큼 아래로 내려간다. 만약 나머지가 0이라면 n-1번째 요소의 숫자를 리스트의 맨 앞에 두고 남은 리스트 값을 역순으로 하여 붙여준다. 나머지가 0이 아니라면 나머지를 새로운 k로 설정해준다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import math def solution(n,k): # n명의 사람 리스트 lst = [i for i in range(1,n+1)] result = [] # 조건을 만족할..
알고리즘 학습/프로그래머스 2020. 9. 3. 18:33
프로그래머스 - 멀리 뛰기 [Python]

문제 문제 상황 - 계단을 뛰는 방법이 1칸 또는 2칸일 때에 n번째 칸에 도달하는 방법의 수 해결 전략 - 전형적인 피보나치 문제로 매우 쉬운 문제 코드 1 2 3 4 5 6 7 8 def solution(n): cache = [0 for i in range(n+1)] cache[1] = 1 if n >=2: cache[2] = 2 for i in range(3,n+1): cache[i] = (cache[i-1] + cache[i-2])%1234567 return cache[n] Colored by Color Scripter cs 해설 - 선택지가 2개이고, 어떤 선택을 만드는 방법이 이전 부분 문제의 합이므로 dp를 사용한다. 새로 학습한 것 & 실수 - 처음에 n의 조건이 1이상인데 cache[2]..
알고리즘 학습/프로그래머스 2020. 9. 3. 12:29
프로그래머스 - 거스름돈 [Python]

문제 문제 상황 - 동전의 종류가 결정되어 있지 않은 상태에서 입력받은 동전의 종류를 통해 거스름돈을 줄 수 있는 방법의 수를 계산한다. 해결 전략 - 탐욕적 방법으로 계산했던 10원, 50원, 100원.. 의 문제와 다르게 이 문제는 하나의 거스름돈을 만드는데 훨씬 많은 경우의 수가 생긴다. 그래서 DP를 사용해야 한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 # n 원, money는 거스름돈의 종류를 담은 list def solution(n, money): # cache[x][y] 는 동전 1~x로 y원을 만들기 cache = [[0 for i in range(n+1)] for j in range(len(money))] # 0,0을 ..
알고리즘 학습/프로그래머스 2020. 9. 2. 20:06
프로그래머스 - N Queen [Python]

문제 문제 상황 - N x N의 체스판에서 N 개의 퀸이 서로 공격할 수 없는 위치에 존재할 방법의 수를 찾는다. 해결 전략 - 완전 탐색으로 단순 DFS를 사용할 경우 속도 이슈가 발생한다. 그래서 BackTracking의 Pruning을 사용하여 탐색 해야 할 경우의 수를 제거한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 def check(x, row): # x 이전까지 행을 검사한다. for i in range(x): # 이미 해당 열이 차지되어 있다면 if row[i] == row[x] or (abs(row[x] - row[i]) == x - i): ..
알고리즘 학습/프로그래머스 2020. 9. 2. 15:08
프로그래머스 - 2 x n 타일링 [Python]

문제 문제 상황 - 직사각형의 타일로 특정 길이의 사각형을 만드는 방법의 수 해결 전략 - 대표적인 dp문제로 피보나치의 개념을 활용한다. - 어떤 길이 n의 타일을 구성하는 방법은 n-1의 길이 타일에 세로로 하나의 타일을 덧대는 방법, n-2길이 타일에 가로로 눕힌 타일 2개를 붙이는 방법 뿐이므로 dp[n] = dp[n-1] + dp[n-2]가 된다. - 반복으로 해결한다. - 재귀의 경우 오류 발생 가능성이 크다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 # 반복문을 활용 def solution(n): cache = [0 for _ in range(n+1)] cache[1] = 1 cache[2] = 2 for i in range(3,n..
알고리즘 학습/프로그래머스 2020. 9. 1. 18:28
프로그래머스 - 구명보트 [Python]

문제 문제 상황 - 최대로 2명이 탑승 가능한 보트에 사람을 태워 최소 횟수로 움직이는 경우를 계산한다. 해결 전략 - 역순으로 정렬하여 사람들을 태우는 데 몸무게가 큰 사람과 가장 몸무게가 적은 사람을 묶어 태운다. 이 때 보트의 탑승 가능 몸무게를 초과하지 않게 한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 def solutio..
알고리즘 학습/프로그래머스 2020. 9. 1. 09:41
1 ··· 12 13 14 15 16 17 18 ··· 22