본문 바로가기

알고리즘

 (50)
[알고리즘/인프런정리] 1-1. Recursion 1 순환(recursion)? 자기 자신을 호출하는 함수이다. main() { code(); } code() { //... code(); } -> 무한루프 빠진다. main() { code2(4); } code2(int k) { if(k 4번 "Hello" 후 끝남. code2(4); -> code2(3); -> code2(2); -> code2(1); -> code2(0); -> return; recursion이 항상 무한루프에 빠지는 것은 아니다. 무한루프 빠지지 않을 조건 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다. recursion 반복하다보면 결국 base case로 수렴해야 한다. 관련 기본 문제 (1) 1~n 합 -> O (2) factorial: n! -> O 0! =..
[알고리즘/dp] 백준 2193번 이친수 문제 풀이0으로 시작하면 안된다. => 첫째 자리는 반드시 1이어야 한다.1이 두번 연속으로 나타나면 안된다. => 1의 앞,뒤에는 반드시 0이어야 한다.이 두 조건을 통해, N이 1보다 클 경우 반드시 앞 두자리는 1, 0 이 차례로 와야 한다.앞 1, 0를 고정으로 두고 맨 뒤는 0, 1일 때 각 경우의 수를 구하면 된다. N=1 일 경우, [1] => 가능한 수 1개N=2 일 경우, [1][0] => 가능한 수 1개 = 끝이 0일 경우 1개 + 끝이 1일 경우 0개N=3 일 경우, [1][0][0], [1][0][1] => 가능한 수 2개 = 끝이 0일 경우 1개 + 끝이 1일 경우 1개N=4 일 경우, [1][0] 0 0, [1][0] 1 0, [1][0] 0 1 => 가능한 수 3개 = 끝이 0..

티스토리툴바