이코테

[1로 만들기] 정수 X를 입력해, 5 로 나누거나, 3으로 나누거나, 2 로 나누거나, 1을 빼는 연산을 반복하여 1을 갖겠끔 하는 최단 연산의 갯수를 구하시오 도식화를 해보고 느낀 점은 1부터 해서 바텀 업 연산을 해야겠다. 1부터 X값 까지 최단 연산의 갯수를 다 구하면 되지 않을까? 근데 어떻게 연산 갯수 세는걸 어떻게 구현해야할지 모르겠어서 책을 봤다. ( 졸면서 5시간 고민 했는데 점화식이라는 개념이 미쳐 떠오르지 않았다. ) 점화식을 구해서 : $a_i = min(a_{i-1},a_{i/2},a_{a/3},a_{a/5})+1$ 점화식을 토대로 소스 코드를 작성한다. def sol(X): # df 테이블 초기화, d[1] = 0 d = [0]*(X+1) for i in range(1,X..

저희 스터디에서 학습 진도에 관해 제가 발표할 차례가 되어 발표 자료를 다음과 같이 만들었는데 그걸 가지고서 다이나믹 프로그래밍을 정리해보고자 합니다. [피보나치 수열을 통한 개념 설명] 효율적인 알고리즘! 이라고 간단히 표현할 수 있겠다. 예시) def fibo(x): if x=1 or x=2: return 1 return fibo(x-1) + fibo(x-2) fibo(6)을 호출해 봅시다. 중복되어 사용되는 코드가 보이시나요? 바로 이러한 중복된 코드 등을 줄임으로써 코드를 효율적으로 만드는걸 DP이라고 합니다. [다이나믹 프로그래밍] 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답이, 그것을 포함하는 큰 문제에서 구한 작은 문제에 대한 정답과 같다. 위 두 조건을 만족할..

[그래프] 그래프는 크게 두가지 형태로 그릴 수 있습니다. 위의 예시를 가지고 다뤄보도록 할게요 참고로, 인덱스 0에 해당하는 값들을 헷깔리지 않게 일부로 비운 상태로 더 만들었습니다. 인접행렬 양방향일 때 인접행렬은 늘 대칭입니다. 이를 이용하면 조금 더 쉽게 정리할 수 있을 것 같습니다. graph = [ [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 1, 0, 0, 0, 0], # 1행 [0, 1, 0, 0, 1, 1, 0, 0], # 2행 [0, 1, 0, 0, 0, 1, 1, 0], # 3행 [0, 0, 1, 0, 0, 0, 0, 0], # 4행 [0, 0, 1, 1, 0, 0, 1, 1], # 5행 [0, 0, 0, 1, 0, 1, 0, 0], # 6행 [0, 0, 0, 0,..

[구현] 피지컬 문제라고도 한다. 아이디어를 코드로 바꾸는걸 구현이라고 한다. 이코테 책에서는 완전탐색과 시뮬레이션을 가지고 구현 예제를 들었다. 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형 [파이썬에서 리스트 크기] 데이터의 개수(리스트의 길이) 메모리 사용량 1,000 약 4KB 1,000,000 약 4MB 10,000,000 약 40MB 리스트를 여러개 선언하고, 그 중에서 크기가 1000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다는 점을 기억하자. [채점 환경] 파이썬의 경우 1초에 2,000만 번의 연산을 수행한다고 가정하면 크게 무리가 없다. 시..