문제 www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 0을 제외한 모든 숫자는 앞에 올 수 있다. 이때 1~8은 뒤에 올 수 있는 숫자가 총 2종류이다(숫자±1). 하지만 9 뒤엔 오직 숫자 8만이 올 수 있다. 이를 그림으로 표현하면 다음과 같다. dp테이블은 이차원 리스트이며 dp[자리 수][앞에 오는 숫자]=경우의 수이다. 정리하면 다음과 같다. 앞에 오는 숫자 = 0 ) dp[자리 수][0] = dp[자리 수 - 1][1] ※ dp[1][0] = 0이기 때문에 어차피 결과엔 영향을 미치지 않는다. ex) 0, 01, 012 -> 안 셈! 앞에 오는 숫자 = 1..
문제 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 이 문제의 핵심은 같은 색으로 연속해서 집을 색칠할 수 없다는 것이다. 다시 말해서 같은 색이 아닌 색으로 다음 집을 칠해야 한다는 것이다. 이것이 점화식을 세우는 핵심이다. 이것을 간단하게 표현하면 다음과 같다. 이전 집의 색깔 현재 집의 색깔 G or B R R or B G R or G B 이를 통해 점화식으로 표현하면 다음과 같다. R, G, B = 0, 1, 2 dp[i]..
파이썬은 정렬 함수를 기본으로 제공한다. sort()와 sorted()의 차이를 살펴보고 key 매개변수와 lambda 함수를 활용한 커스텀 정렬을 살펴본다. 1) Sort() vs Sorted() sort() .sort([key = ], [reverse = True|False]) 리스트 자료형에서만 사용 가능하다. 원래의 리스트가 변경된다(in-place). 아무것도 반환하지 않는다(None 리턴). 리스트를 정렬할 땐 sorted()보다 빠르다. reverse 매개변수로 True를 전달하면 내림차순 정렬할 수 있다. sorted() sorted(, [key = ], [reverse = True|False]) 모든 iterable한 객체에서 사용 가능하다. 원래의 리스트는 변화가 없다. 정렬된 새로운 ..
리스트을 순회하는 과정에서 데이터를 변경하다가 에러가 나는 경우는 굉장히 잦다. 특히 그 중에서 삭제는 가장 까다롭다. 이때, 리스트 표현식과 슬라이싱을 활용하여 데이터를 변경할 수 있다. 문제 예제 lost = [2,4]; reserve = [1,2,5] for i in range(len(reserve)): if reserve[i] in lost: del reserve[i] print(reserve) ''' Traceback (most recent call last): File "main.py", line 3, in if reserve[i] in lost: IndexError: list index out of range ''' 해결방법 리스트 표현식(List Comprehension) + 슬라이싱 lo..
알고리즘 문제들을 풀 땐 시간복잡도와 공간복잡도가 중요하다. 그 중 파이썬에서 자주 쓰이는 연산들의 시간복잡도를 자료형에 따라 정리했다. 리스트(List) Operation Example Complexity Notes Index l[i] O(1) Store l[i] = 0 O(1) Length len(l) O(1) Append l.append(5) O(1) Pop l.pop() O(1) same as l.pop(-1), popping at end Clear l.clear() O(1) similar to l = [] Slice l[a:b] O(b-a) l[1:5]:O(l)/l[:]:O(len(l)-0)=O(N) Extend l.extend(...) O(len(...)) depends only on len ..
