본문 바로가기

Algorithm48

[프로그래머스] 행렬의 곱 파이썬 def solution(a, b): c = [] for i in range(0,len(a)): # row of a temp=[] for j in range(0,len(b[0])): # col of b s = 0 for k in range(0,len(a[0])): # col of a or row of b s += a[i][k]*b[k][j] temp.append(s) c.append(temp) return c a = b = [1, 4] [3, 3] [3, 2] [3, 3] [4, 1] matrix muliplication answer를 list라고 선언했을때 answer[0][0] = (a[0][0] * b[0][0]) + (a[0][1] * b[1][0]) . . . answer[2][1] = (a[2].. 2021. 3. 16.
[프로그래머스] 피보나치 수 파이썬 역시 재귀로 풀었더니 런타임오류 DP로 수정 def solution(n): fibo = [] for x in range(0,n): if x < 2: fibo.append(1) else: fibo.append(fibo[x-2] + fibo[x-1]) answer = fibo[-1]%1234567 return answer Pythonic way def solution(num): a,b = 0,1 for i in range(num): a,b = b,a+b return a 2021. 3. 16.
[프로그래머스] 숫자의 표현 파이썬 그냥 무식하게 brute force로 def solution(num): answer = 0 for i in range(1, num + 1): s = 0 while s < num: s += i i += 1 if s == num: answer += 1 return answer 2021. 3. 15.
[프로그래머스] 땅따먹기 파이썬 다른사람의 풀이 def solution(land): for i in range(0, len(land)-1): land[i+1][0] += max(land[i][1],land[i][2],land[i][3]) land[i+1][1] += max(land[i][0],land[i][2],land[i][3]) land[i+1][2] += max(land[i][0],land[i][1],land[i][3]) land[i+1][3] += max(land[i][0],land[i][1],land[i][2]) return max(land[len(land)-1]) def solution(land): for i in range(1, len(land)): for j in range(len(land[0])): land[i][j] .. 2021. 3. 15.
[프로그래머스] 다음 큰 숫자 def solution(num): b_num = bin(num) b_num_1 = b_num.count("1") new_num = num+1 while True: b_new_num = bin(new_num) new_num_1 = b_new_num.count("1") if b_num_1 == new_num_1: break new_num += 1 return new_num 지저분하지만 맞긴했따. def solution(num): new_num = num+1 while True: if bin(num).count("1") == bin(new_num).count("1"): break new_num += 1 return new_num 깔끔하게 2021. 3. 15.
[프로그래머스] 가장 큰 정사각형 찾기 파이썬 (DP) 예전에 fastcampus에서 한번 다뤘던 문제라고 기억을 하는데 이미 기억에서 지워진 문제 DP로 푸는것만 기억하고 나머지는 다 잊어버림 def solution(board): width = len(board[0]) height = len(board) for x in range(1,height): for y in range(1,width): if board[x][y] == 1: board[x][y] = min(board[x-1][y-1], min(board[x-1][y], board[x][y-1])) + 1 return max([item for row in board for item in row])**2 출처:geonlee.tistory.com/111 굳이 DP list를 만들겠다면 def solutio.. 2021. 3. 15.
[프로그래머스] 쿼드압축 후 개수 세기 파이썬 다른 사람의 풀이 def solution(arr): answer = [0, 0] N = len(arr) def comp(x, y, n): init = arr[x][y] # 해당 네모값중 하나 # 모두 같아야 통과임 for i in range(x, x + n): for j in range(y, y + n): if arr[i][j] != init: # 한번이라도 다르면 그 네모는 압축불가 nn = n // 2 comp(x, y, nn) comp(x, y + nn, nn) comp(x + nn, y, nn) comp(x + nn, y + nn, nn) return # 무사히 다 통과했다면 압축가능 answer[init] += 1 comp(0, 0, N) return answer 이해하기도 쉽고 깔끔한 풀이 같.. 2021. 3. 15.
[프로그래머스] 타겟 넘버 (BFS/DFS) 파이썬 다른 사람의 풀이 from collections import deque def solution(numbers, target): answer = 0 queue = deque([(0, 0)]) # sum, level while queue: s, l = queue.popleft() if l > len(numbers): break elif l == len(numbers) and s == target: answer += 1 queue.append((s+numbers[l-1], l+1)) queue.append((s-numbers[l-1], l+1)) return answer sum, level이라는 2개의 tuple를 queue를 활용해서 만든풀이 queue에 들어가는 tuple를 append하는 코드를 보면, .. 2021. 3. 15.
[프로그래머스] 카펫 파이썬 완전탐색으로 푸는 방법 def solution(brown, red): for a in range(1, int(red**0.5)+1): if not red % a: b = red // a if 2*a + 2*b + 4 == brown: return [b+2, a+2] 출처: geonlee.tistory.com/114 def solution(brown, red): for index in range(1,red+1): if red%index == 0: length = red//index if (((index+2)*(length+2))-(index*length)) == brown: return [max(index+2,length+2),min(index+2,length+2)] m.blog.naver.com/Post.. 2021. 3. 12.

티스토리툴바