알고리즘216

• 

  [프로그래머스] 사칙연산 - 파이썬(python) 나의 풀이 import math def solution(arr): N = math.ceil(len(arr) / 2) # dp[] 는 피연산자만 담아둔다 # 즉, dp[i][j] 는 i번째숫자~j번째숫자까지의 최대/최솟값이다 max_dp = [[float('-inf') for _ in range(N)] for _ in range(N)] min_dp = [[float('inf') for _ in range(N)] for _ in range(N)] for step in range(N) : # i~j 까지의 간격 for i in range(N-step) : j = i + step if step == 0 : # 간격이 0 일때는 자기자신이 최대/최소 max_dp[i][i] = int(arr[i*2]) min_dp.. 알고리즘/동적프로그래밍(DP) 2022. 9. 20.

• 

  [프로그래머스] 도둑질 - 파이썬(python) 나의 풀이 def solution(money): # 방법1. 맨 뒷 집을 제외한 경우 dp1 = [0]*len(money) dp1[0] = money[0] dp1[1] = max(money[0], money[1]) # 0,1번 집 중 더 돈이 많은 집 하나만 털 수 있음 for i in range(2,len(money)) : if i != len(money) - 1 : dp1[i] = max(dp1[i-2]+money[i], dp1[i-1]) else : dp1[i] = max(dp1[i-2]+0, dp1[i-1]) # 마지막집이 없다고 가정했으므로 dp[i] 는 i-2, i-1 중 더 큰 값이 된다. # 방법2. 맨 앞 집을 제외한 경우 dp2 = [0]*len(money) dp2[0] = 0 # 맨 .. 알고리즘/동적프로그래밍(DP) 2022. 9. 19.

• 

  [프로그래머스] 등굣길 - 파이썬(python) 나의 풀이 def solution(m, n, puddles): dp = [[0]*(m+1) for _ in range(n+1)] print(dp) for i in range(1, n+1) : for j in range(1, m+1) : if i == 1 and j == 1 : dp[i][j] = 1 elif [j,i] in puddles : dp[i][j] = 0 else : dp[i][j] = dp[i-1][j] + dp[i][j-1] # print("dp[{}][{}] = {}".format(i,j,dp[i][j])) return dp[n][m] % 1000000007 (1,1) 을 집으로, (n,m) 을 학교 좌표로 만들기 위해, 이차원 배열을 [n+1][m+1] 의 크기로 초기화한다. 이번 문제는.. 알고리즘/동적프로그래밍(DP) 2022. 9. 19.

• 

  [프로그래머스] 정수 삼각형 - 파이썬(python) 나의 풀이 def solution(triangle): d = triangle[:] for i in range(1, len(d)) : for j in range(0,i+1) : if j == 0 : d[i][j] += d[i-1][j] elif j == i : d[i][j] += d[i-1][i-1] else : d[i][j] += max(d[i-1][j-1], d[i-1][j]) return max(d[len(d)-1]) 전형적인 bottom up 동적프로그래밍 문제이다. dp[] 에는항상 dp[i][j] 까지의 최댓값 경로가 저장되어 있다. 따라서 dp[i][j] 를 구하려면, dp[i-1][j-1] 와 dp[i-1][j] 둘 중 더 큰값을 나의 값에 더해주면 된다. 만약 한 줄에서 첫번째 값(j=0).. 알고리즘/동적프로그래밍(DP) 2022. 9. 17.

• 

  [프로그래머스] N으로 표현 - 파이썬(python) 나의 풀이 from itertools import product def solution(N, number): d = [[] for _ in range(9)] if N == number : return 1 d[1] = [N] d[2].extend(list(set([10*N+N, N+N, N-N, N*N, N//N]))) if number in d[2] : return 2 for i in range(3, 9) : d[i].extend([int(str(N) * i)]) for j in range(1, int(round(i/2))+1) : for k in product(d[j], d[i-j]) : t1 = k[0] + k[1] t2 = k[0] - k[1] t3 = k[1] - k[0] t4 = k[0] * k.. 알고리즘/동적프로그래밍(DP) 2022. 9. 17.

• 

  [프로그래머스] 단속카메라 - 파이썬(python) 나의 풀이 def solution(routes): routes.sort(key = lambda item : item[1]) camera = 0 min_spot = -30001 for start, finish in routes : if start = min_spot : continue else : min_spot = finish camera += 1 return camera 차량이 고속도로에서 나간 지점을 오름차순으로 정렬한다. 이전 차량이 만난 카메라의 지점을 min_spot 으로 지정하고, 만약 현재 차량이 min_spot 을 만날 수 있다면 반복문을 넘어간다. -> if start = min_spot : continue 그렇지 않다면 내 차량이 마지막으로 빠져나가는 지점을 min_spot 으로 지정하.. 알고리즘/그리디 2022. 9. 17.

• 

  [프로그래머스] 섬 연결하기 - 파이썬(python) 나의 풀이 def find_parent(parent, x) : if parent[x] != x : # 자기 자신이 아닌 경우, 재귀적으로 부모를 찾으러 감 parent[x] = find_parent(parent, parent[x]) return parent[x] def union_node(parent, a,b) : a_parent = find_parent(parent, a) b_parent = find_parent(parent, b) if a_parent == b_parent : # 같은 부모인 경우, 싸이클 생성됨 return False elif a_parent < b_parent : parent[b_parent] = a_parent # 부모의 부모를 변경 else : parent[a_parent] =.. 알고리즘/그리디 2022. 9. 17.

• 

  [프로그래머스] 구명보트 - 파이썬(python) 나의 풀이 def solution(people, limit): people.sort() answer = 0 min_index = 0 max_index = len(people)-1 while max_index - min_index >= 1 : if people[max_index] + people[min_index] 알고리즘/그리디 2022. 9. 16.

• 

  [프로그래머스] 큰 수 만들기 - 파이썬(pytyon) 나의 풀이 def solution(number, k): length = len(number) - k answer = "" i = 0 index = length #가장 높은 자리 while len(answer) != length : if index == 0 : break max_index = i for x in range(i, len(number)-index+1) : if number[x] == '9' : max_index = x break elif number[x] > number[max_index] : max_index = x answer += str(number[max_index]) i = max_index+1 index -= 1 return answer 으아... 구현 아이디어를 떠올리는데 시간이 .. 알고리즘/그리디 2022. 9. 16.

• 

  [프로그래머스] 조이스틱 틀린 풀이 def solution(name): answer = list("A" * len(name)) count = 0 i = 0 # 현재 인덱스 while True : print("i: ",i) # 알파벳 변경하기 if name[i] != "A" : count += min(ord(name[i]) - ord("A"), ord("Z") - ord(name[i]) + 1) answer[i] = name[i] # 다 만들었으면 반복문 탈출 if ''.join(s for s in answer) == name : break left = right = 0 # 왼쪽으로 이동하기 while True : if name[i-left-1] != "A" and answer[i-left-1] == "A" : left += 1 .. 알고리즘/그리디 2022. 9. 16.

• 

  [프로그래머스] 체육복 나의 풀이 def solution(n, lost, reserve): lost.sort() reserve.sort() for i in lost[:] : if i in reserve : reserve.remove(i) lost.remove(i) for i in lost[:] : if i-1 in reserve : reserve.remove(i-1) lost.remove(i) elif i+1 in reserve : reserve.remove(i+1) lost.remove(i) return n - len(lost) 먼저 lost, reserve 리스트를 오름차순으로 정렬한다. 만약 reserve 에 있는 학생이 lost 에도 있다면, 해당 학생을 두개의 리스트에서 각각 제거한다. 만약 lost 에 있는 학생 번.. 알고리즘/그리디 2022. 9. 14.

• 

  [프로그래머스] 모음사전 - 파이썬(python) 나의 풀이 def dfs(x, dictionary, alpha): dictionary.append(x) for i in alpha : if len(x) != len(alpha) : dfs(x+i, dictionary, alpha) else : x[:-1] def solution(word): alpha = ['A','E','I','O','U'] dictionary = [] for i in range(len(alpha)) : dfs(alpha[i], dictionary, alpha) return dictionary.index(word) + 1 DFS 로 풀이한 문제이다. 먼저 dictionary 에 현재 나의 문자를 추가한다. 그리고, alpha 리스트를 반복문으로 돌면서, 문자열 x의 길이가 5 보다 작다.. 알고리즘/완전탐색 2022. 9. 7.