파이썬_실전 프로젝트

본 토픽은 현재 준비중입니다. 공동공부에 참여하시면 완성 되었을 때 알려드립니다.

프로젝트 오일러 18번 문제 - 최대 합 경로찾기

삼각형 모양의 숫자 배열을 따라 내려가면서, 가장 큰 합을 찾는 문제입니다.

경로의 갯수는 2^14 = 16384개 입니다. 일단 그렇게 크지 않을듯 하니, 그냥 경로를 다 찾아보는것도 괜찮은 방법인것 같습니다. 출제자는 그렇게 하지 말고, 좀더 스마트한 방법을 찾아보라고는 하지만, 일단은 그냥 한번 해 보기로 하죠.

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

 

순서는,

1. 파일을 불러오고,

2. 합을 계산하는 서브 함수를 만들도록 하겠습니다.

 

먼저 데이터 파일을 텍스트파일에서 불러오는 부분입니다. 데이터파일 불러오기 참조

(data파일에는 미리 저 수열을 그대로 복사해서 txt파일로 저장해놓으면 됩니다. 삼각형 모양은 신경안써도 됩니다.)

filename = 'q018_data.txt'
with open(filename) as data:
    lines = data.readlines()
m=len(lines)

numbers=[]
for line in lines:
	print(line.split())
	numbers.append(line.split())

이렇게 해주면, numbers 라는 리스트를 배열처럼, numbers[3][2] 형식으로 불러서 사용할수 있습니다.

 

그다음으로 합을 계산하는 함수입니다.

이런 수열문제는 자기스스로를 다시 호출하는 재귀호출 함수로 만들면 편합니다. 좀 햇갈리긴 한데, 익숙해지면, 코딩이 그만큼 편해집니다.

재귀호출 함수는, 수열의 각항이 해야할일과 같은데, 이 문제에서 각항은 아래에 있는 두개의 숫자중에 큰것만을 판단해서 자신과 합한후 위쪽수로 넘겨주면 됩니다. 마지막줄은 아래항이 없기 때문에, 자기자신만을 리턴시키구요,

def biggest_sum(i=0,j=0):
    if i==m-1:  #m-1 = 14(15번째줄, 마지막항)일때는 아래항을 찾지말고,
		return numbers[i][j] #바로 자기자신만 리턴.
	else :  # 그외에 나머지 항들은,
		num1=biggest_sum(i+1,j) #아래쪽 항목1 조사. i값 바꿔서 재귀호출.
		num2=biggest_sum(i+1,j+1) #아래쪽 항목2 조사. 여기도 i,j값 바꿔서 재귀호출.
		if num1>num2:     # 값판단후, 값에따라서, 
			return int(numbers[i][j])+int(num1) #num1 또는
		else :
			return int(numbers[i][j])+int(num2) #num2 값 리턴.

print(biggest_sum())

사실 한번에 이렇게 딱 하고 잘 안나옵니다. 보통 여러번 시행착오를 거쳐야 됩니다. 처음만들때는 프린트문으로 값도 찍어 가면서 만들어야 해서 시간이 더 걸리죠.

 

답은 이렇게만 하면 구해지는데, 이렇게만 하면, 뭔가 미심쩍기도 하고, 심심하기도 하고, 궁금하니깐,

어떤숫자들이 합해졌는지 알아보기로 하죠. 똑같은 함수를, 숫자의 합을 계산하지 말고, 문자열의 합으로 바꿔주기만 하면, 합해진 숫자들의 전체 리스트가 됩니다.

def biggest_path(i=0,j=0):
    if i==m-1:
		return numbers[i][j]
	else :
		num1=biggest_path(i+1,j)
		num2=biggest_path(i+1,j+1)
		if num1>num2:
			return numbers[i][j]+","+num1 #원래 리스트가 문자열이여서, int만 제거.
		else :
			return numbers[i][j]+","+num2 #구분을 위해서, "," 삽입.

 

함수를 두개로 하지말고, 한번에 하려면 아래와 같이 해주면 됩니다.

def biggest_sum_with_path(i=0,j=0):
    # not completed
	if i==m-1:
		return numbers[i][j],numbers[i][j]
	else :
		num1,str1=biggest_sum_with_path(i+1,j)
		num2,str2=biggest_sum_with_path(i+1,j+1)
		if num1>num2:
			return int(numbers[i][j])+int(num1),numbers[i][j]+","+str1
		else :
			return int(numbers[i][j])+int(num2),numbers[i][j]+","+str2

 

 

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
노마드
현재 버전
선택 버전
graphittie 자세히 보기