본문 바로가기

알고리즘 문제

Programmers Level 5 2 x n 타일링 def tiling(n): answer = 0 a=1 b=2 if n==1:return 1 if n==2:return 2 while n>2: answer = a+b a,b=b,answer n-=1 return answer%100000 #생각해보니 100000으로 나누면 자리수가 무조건 5 이하.# 아래는 테스트로 출력해 보기 위한 코드입니다.print(tiling(271))
Programmers Level 5 124나라의 숫자 def change124(n): answer = "" i=0 while n>0: i = n%3 n //= 3 if i==0: n-=1 answer = '412'[i] + answer return answer # 아래는 테스트로 출력해 보기 위한 코드입니다.print(change124(10))
Programmers Level 4 땅따먹기 게임 def hopscotch(board, size): sumList = [0]*4 for row in board: tmp = sumList.copy() for i in range(len(row)): sumList[i] = row[i] + max(tmp[:i] + tmp[i+1:]) return max(sumList) #아래는 테스트로 출력해 보기 위한 코드입니다.board = [[ 1, 2, 3, 5 ], [ 5, 6, 7, 8 ], [4, 3, 2, 1]]print(hopscotch(board, 3))
Programmers Level 4 공항 건설하기 def chooseCity(n,city): #city.sort(key=lambda x: x[0]) city.sort() total = sum([x[1] for x in city]) #인구수 총합 s = 0 for i in range(n): s += city[i][1] #인구수 누적 if s >= (total // 2):#인구수의 절반보다 크다면 break return city[i][0]print(chooseCity(3,[[1,5],[2,2],[3,3]]))
Programmers Level 4 최고의 집합 #s - s//n 를 원소에 배분한다.def bestSet(n, s): if n>s: return [-1] answer = [] avg = s//n for i in range(n): answer.append(avg) addingNumber = s-avg*n while addingNumber>0: for i in range(n): if addingNumber>0: answer[i]+=1 addingNumber -= 1 else: break return sorted(answer) # 아래는 테스트로 출력해 보기 위한 코드입니다.print(bestSet(3,13))
Programmers Level 4 가장 큰 정사각형 찾기 ★ def findLargestSquare(board): col = len(board[0]) row = len(board) mx=0 dp=[[0]*col for i in range(row)] for i in range(1,row): for j in range(1,col): if board[i][j] == 'O': dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1 if mx < dp[i][j]: mx=dp[i][j] return mx**2testBoard = [['X','O','O','O','X'],['X','O','O','O','O'],['X','X','O','O','O'],['X','X','O','O','O'],['X','X','X','X','X']]print(..
Programmers Level 4 숫자의 표현 def expressions(num): answer = 0 for i in range(1,num+1): num1=num for j in range(i,num+1): num1 -= j if num1 == 0: answer +=1 break elif num1 < 0: break return answer# 아래는 테스트로 출력해 보기 위한 코드입니다.print(expressions(15));
Programmers Level 3 다음 큰 숫자 #n을 2진수로 바꾸고 n+=1 한 숫자를 이진수로 변환해서 1의 개수가 같은지 판단하기.def nextBigNumber(n): binary = bin(n).lstrip('0b')#앞에 0b 없애기 newn=n while True: newn += 1 newbin = bin(newn).lstrip('0b') if newbin.count('1')==binary.count('1'): break return newn #아래 코드는 테스트를 위한 출력 코드입니다.print(nextBigNumber(78))

티스토리툴바