2017/078 [DP]행렬곱 1번째부터 n번째의 모든 행의 곱인을 구하기 위해서는 여러가지 방법이 있다. 우선 첫번째 행렬이 pxq인 행렬이고 두번째 행렬이 qxr인 행렬인 경우 결과값으로 나오는 행렬은 pxr인 행렬이라는 것은 고등학교 수학 수업중 배웠을 것이다. 또 간단한 행렬에 대하여 곱을 수행해보면 총 연산 횟수는 pxqxr이라는 것을 알게 될 것이다. 그렇다면 이러한 여러 행렬의 곱연산은 어떨까? 행렬은 일단 교환법칙이 성립되지 않기 때문에 서로 자리를 바꾸게 되면 결과가 바뀌게 된다. 하지만 결합법칙은 성립하여 이 두가지의 결과는 같다. 하지만 결과는 같을지라도 결합의 방식에 따라서 계산 횟수가 달라지게 된다. 예를 들면 행렬 A를 10x100, B는 100x5, C는 5x50이라고 할 때 새 행렬 ABC는 10x50의 .. 2017. 7. 16. [boj-4811]알약 나는 항상 보면 접근 자체를 복잡하게 생각하는 경우가 많다. 부족한 두뇌로 복잡한 계산을 생각하다보니 스스로 지쳐서 머리 회전이 멈추는 듯 하다. 재귀는 항상 기억할 것은, 상태공간트리를 그려가며 작은 sub-problem으로부터 base case를 먼저 생각하고 그 후 recursion case를 정해 나가는 것이다. 이 과정만 제대로 할줄 안다면 정말 완벽할텐데.. 어쨌든 문제는 다음과 같다. 70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다. 첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다. 다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 .. 2017. 7. 15. (Recursion) 미로 찾기 출처: 인프런-영리한 프로그래밍을 위한 알고리즘 강좌(권오흠 교수님) 위와 같은 그림의 미로가 있다고 할 때 입구에서 출구로 빠져나가기 위한 경로를 구하고자 한다면 어떠한 방법이 최선일까요? 2중 for문을 통해서 찾아갈 수도 있겠지만 이는 너무 어리석은 짓이고.. recursion을 통해 해결할 수 있을 겁니다. 먼저 recursion을 통해 해결하기 위한 base case를 보면 다음과 같습니다.base case:참조된 점 (x,y)가 이미 출구인 경우 참조된 점 (x,y)가 벽인 경우그렇다면 recursion case는 무엇일까요? 이는 참조되고 있는 자기 자신을 제외한 인접한 점들에 대하여 재귀적으로 함수를 호출하면 될것같습니다.recursive case: 인접한 4개의 점들에 대해 재귀적으로 검.. 2017. 7. 9. Recursive(재귀 함수) Recursion : 자기 자신을 호출하는 함수를 지칭함ex)func() {print("hello world!");func();}무한루프를 방지하기 위한 조건base case: 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 함Recursive case: recursion을 반복하다보면 결국 base case로 수렴해야 함 순환 함수와 수학적 귀납법- ex) 정리: func(int n)은 음이 아닌 정수 n에 대해 0~n 까지의 합을 계산한다증명:n=0인 경우 0을 반환임의의 양의 정수 k에 대해 n=n인 양의 정수 m, n에 대해 m이 n의 배수라면// gcd(m,n)=n이고, 그렇지 않으면 gcd(n,m%n)이다if(n>m)swap(m,n);if(m%n==0)return n;else r.. 2017. 7. 8. 이전 1 2 다음
