본문 바로가기
728x90

Python169

[BOJ/Python] 2579. 계단 오르기 📌 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 📌 문제 접근 방법 첫 번째 칸을 밟는 경우, 최대값은 첫 번째 칸의 점수 두 번째 칸을 밟는 경우, 최대값은 첫 번째 칸 + 두 번째 칸의 점수 세 번째 칸을 밟는 경우, 첫 번째 칸 + (2칸 이동) 세 번째 칸 두 번째 칸 + (1칸 이동) 세 번째 칸 i번째 칸을 밟는 경우, i-3번째 칸 + (2칸 이동) i-1번째 칸 + (1칸 이동) i번째 칸 i-2번째 칸 + (1칸 이동) i번째 칸 .. 2021. 10. 8.
[BOJ/Python] 1208. 부분수열의 합2 📌 문제 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 📌 문제 접근 방법 시간 초과를 피하기 위해 리스트를 2개로 나누어 준다. (N의 최대값은 40으로, 나누지 않고 부분집합을 구할 경우 2^40번의 연산이 필요하다. 둘로 나눌 경우, 2^20 + 2^20번의 연산으로 줄일 수 있다.) left, right로 나눈 두 개의 부분집합에 대해서 나올 수 있는 합의 경우의 수를 구한다. 투 포인터를 활용하.. 2021. 10. 8.
[Python] 2차원 배열, 딕셔너리 정렬 2차원 배열 정렬 lst = [[3, 'B'], [0, 'D'], [1, 'A'], [2, 'C']] [sorted 사용] : 원본 리스트는 그대로 유지한 채, 정렬된 리스트를 반환 # 1 print(sorted(lst)) # 2 print(sorted(lst, key=lambda x : x[0])) # 3 print(sorted(lst, key=lambda x : x[1])) # [[0, 'D'], [1, 'A'], [2, 'C'], [3, 'B']] # [[0, 'D'], [1, 'A'], [2, 'C'], [3, 'B']] # [[1, 'A'], [3, 'B'], [2, 'C'], [0, 'D']] 기본적으로 key값을 설정하지 않고 sorted를 사용하면 리스트의 첫 번째 요소를 기준으로 정렬을 .. 2021. 10. 8.
[BOJ/Python] 2473. 세 용액 📌 문제 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 📌 문제 접근 방법 움직이지 않는 기준을 하나 설정하고 왼쪽, 오른쪽 인덱스를 바꿔가면서 합을 도출한다. 합이 양수라면 오른쪽 인덱스를 -1, 음수라면 왼쪽 인덱스를 +1 해줘서 0에 가깝게 만들어준다. 위의 과정을 반복하며 합이 0과 가장 가까운 인덱스 3개를 저장한다. 시간 초과 해결 1, 2의 과정으로는 자꾸 시간 초과가 나서 다음의 시도를 해보았다. 기준점(j.. 2021. 10. 7.
728x90

티스토리툴바