일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- API
- AWS
- MAC
- Algorithm
- es6
- CSS
- react
- c++
- 알고리즘 연습
- 알고리즘
- DRF
- django rest framework
- 알고리즘 문제
- Django
- PYTHON
- HTML
- 백준
- java
- js
- django ORM
- 알고리즘 풀이
- Baekjoon
- 장고
- 파이썬
- javascript
- form
- django widget
- 파이썬 알고리즘
- web
- Git
- Today
- Total
수학과의 좌충우돌 프로그래밍
땅따먹기(프로그래머스-level2) 본문
안녕하세요 여러분
알고리즘 외에도 여러가지를 공부하다보니 하루에 한 개씩 포스팅을 하겠다던 계획을 지키기가 많이 어렵네요 ㅠㅠ
곧 알고리즘 외에도 웹프로그래밍, 인공지능 등 유익한 정보로 찾아뵙도록 하겠습니다.
오늘 알아볼 내용은 '땅따먹기' 입니다.
제목만으로는 무슨 문제가 유추가 안될텐데요,
문제는 다음과 같습니다.
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 | def solution(land): answer = 0 N = len(land) # N은 행의 개수가 된다. num = 5 # 첫 행에서는 num 이 영향을 미치면 안되므로 열의 총 수인 4보다 큰 5를 대입해놓았다. for i in range(0, N): # 0번째 행부터 N-1행까지 반복 max = 0 for j in range(0, 4): # 각 행의 열들을 반복 if num == j: # 바로 직전의 행과 같은 열을 밟을 수 없다. continue if land[i][j] > land[i][max]: max = j # 각 열에서 최대값을 찾기 answer += land[i][max] #최대값들 더해주기 num = max # 이번 행에서 최대였던 열을 저장하여 다음 행에 영향을 준다. return answer | cs |
각 코드에 대한 설명은 옆에 주석으로 적어두었으니 전체적인 풀이방법은
첫번째 행부터 탐색을 하며 가장 큰 수를 고르고,
그 다음 행으로 내려와서 바로 직전 행의 최대값과 같은 열에 있는 수를 제외한 최대값을 고르는 과정을 반복했습니다.
그 결과,
주어진 예시에서는 맞았지만,
전체에서는 보기 좋게 틀리고 말았습니다.
그래서 다른 예를 생각하다보니 너무 말도 안되는 실수를 했더라고요.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | def solution2(land): answer = 0 N = len(land) # N은 행의 개수가 된다. for i in range(0,N-1): land[i+1][0] += max(land[i][1],land[i][2],land[i][3]) # i+1번째 행에 0번째 열에는 i번째 행에 1,2,3 열 중 최대값을 더해준다. 이런식으로 계속 더해나가면 # N-1번째에 열들을 각 선택지에서 가질 수 있는 최대값이 된다. 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]) answer = max(land[N-1]) # 바로 위에 코드가 똑같은 코드다. N-1행에서의 최대값을 가지는 열 answer에 대입한다. # answer = max(land[N-1][0],land[N-1][1],land[N-1][2],land[N-1][3]) return answer | cs |
먼저 5,6,7,8이 있는 두번째 행에 첫번째 행의 수들의 최대값을 더할 겁니다.
5,6,7에는 첫번째 행의 최대값인 5가 더해질테지만 8에는 같은 열에 있는 5를 제외한 최대값 3이 더해지겠죠.
그 결과,
다음과 같이 될 껍니다. 마찬가지로 3번째 행에도 더해주면,
4,3,1 에는 전 행의 최대값인 12가 2에는 12를 제외한 최대값 11이 더해질 겁니다.
그 결과,
이 문제도 처음부터 여러 가지 예시들을 고려하고 코드짜기 시작했으면 안해도 되었을 실수죠.
또 이렇게 자기반성을 마치도록 하겠습니다.
항상 겸손한 자세로..!
'알고리즘 > 파이썬' 카테고리의 다른 글
시저암호(프로그래머스-level1) (1) | 2018.09.06 |
---|---|
같은 숫자는 싫어(프로그래머스-level1) (0) | 2018.09.06 |
올바른 괄호의 갯수(프로그래머스-level4) (2) | 2018.08.01 |
하노이의 탑(프로그래머스-level3) (1) | 2018.07.30 |
다음 큰 숫자(프로그래머스-level2) (1) | 2018.07.30 |