[바킹독의 실전 알고리즘] 0x0B강 - 재귀

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

질문 전에 이 글을 반드시 확인해주세요. 질문 가이드를 정확하게 따라간 질문에 대해서만 답변을 드리고 그렇지 않은 질문은 먼저 가이드에 맞게 수정을 요청할 예정입니다. github.com/encrypted-def/basic-algo-lecture/blob/master/docs/how-to-ask.md 25:16

[@꾸이꾸이-i5k]

저 살면서 처음으로 재귀문제 스스로 성공했네요..Z문제 스스로 풀었어요ㅠㅠㅜ 진짜 감격..재귀문제가 제일 벽으로 느껴졌는데 진짜 명강의... 학교에서도 배우면서 아 나는 재귀는 불가능이구나 했는데 절차적 사고를 버리라는게 진짜 도움이 됐어요 감사합니다

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

깨달으셨군요...💪💪 킵고잉합시다

[@ChaNyeok]

재귀 강의을 보니 겨울인데도 식은 땀이 흐르고 몸에서 열이나고 정신 나갈 것 같다 추울때마다 봐야겠다

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

목요일부터 엄청 추워지던데 목요일에 다시 보시면 되겠네여

[@castlename986]

귀납적 사고... 뭔가 이해는 되는데 자꾸 확인을 절차적으로 확인하네요 ㅋㅋ

[@휴학생생]

재귀를 절차적으로만 생각해왔는데 귀납적으로 생각해야했네요! 좋은 강의 감사합니다~

[@Lsapee]

재귀… 얘만 푸는 방법이 너무 어렵네요. 분명 빽트레킹/dfs할때는 그나마 사용되는데 그냥 재귀Z나 별찍기 같은 문제는… 그래도 또 보고 이해하려하겠습니다.

[@김훈민-s2m]

형님 사랑합니다.. 백트래킹과 재귀함수 구현에 큰 어려움을 겪고 검색과 유튜브 강의를 돌아다니다가 우연하게 형님 강의를 접했는데 너무 설명을 잘해주셔서 큰 깨달음을 얻고갑니다 좋은 강의 정말 정말 감사드립니다. 하시는 일 모두 잘 되시길 바랍니다!!

[@kimera5675]

재귀에선 절차 지향적인 사고보단 귀납적 사고...메모메모

[@becomeweasel]

재귀 곱셈에는 modulo 연산의 속성을 기억하면 빠르게 이해할수있어요 (a mod n * b mod n) mod n = (a*b) mod n

[@hoony30]

한동안 알고리즘 문제풀이 그만두었다가 다시 시작하려고 다시 방문했는데 하노이의 탑을 풀어보니 재귀라는 녀석이 얼마나 매력적인지 알아버렸습니다.. 귀납법을 이용해 식을 세우고 나머지는 컴퓨터에게 맡기기만하면 끝이네요 절차적으로 어떻게 프로그램이 흘러가는지는 전혀 신경 안써도 되는게 참 신기합니다 물론 귀납적으로 사고하는게 어렵지만 곧 쉬워질거라 믿고 계속해서 정진하겠습니다 좋은 강의 감사합니다

[@yunseong3680]

절차적 사고를 버리라는 말이 저에게 크게 다가왔습니다. 감사합니다. 지금까지 제가 재귀문제를 절차적으로 접근하고있었습니다... 진짜 큰 깨달음 얻고 갑니다 감사합니다 ㅎ

[@이성진-i7o]

230824 감사합니다. 뭔가 시야가 더 넓어지는 느낌이네요.

[@sitoutofbed9231]

저는 멍청입니다 .... 저는 바보입니다 ......

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

어렵읍니까,,,ㅠㅠㅠ

[@sitoutofbed9231]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog dfs까지 따라오다가 여기서 무너집니다 ... 여러 번 다시 들어볼께여 ....

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

@@sitoutofbed9231 화이팅,,,,

[@서민수-y7b]

와 귀납적 사고... 깨달았습니다 감사합니다👍👍👍

[@junsfernandez4929]

감사합니다😊😊😊

[@박창현-h9k]

재귀 해답을 보면 이해는가는데 귀납적 사고를 가지고 구현하려고 하는데 너무어렵네요.. 저는 지금 회사 코딩테스트 를 준비중인데 3문제가 나오거든요.. 시간이 많이 없어서 조언좀 부탁드리겠습니다. ㅠㅠ 도와주세요 1번은 그냥 코딩해봤으면 맞출수준의 문제 실버3 아래 2번은 BFS DFS응용문제 실버1~2 3번은 아이디어가 필요한 어느단원의 문제가 나올지 모르겠습니다. 골드5~플래5 위 구성으로 출제되는데 반타작이 목표거든요.. 1번 2번을 맞추려고하는데 재귀부분을 패스해도되는지 궁금합니다. 참고로 자료구조 알고리즘을 처음접했구요 백준 150문제정도 쉬운걸로 푼 상태입니다.. 추가로 뒤에 백트래킹 시뮬레이션 정렬1 정렬2 다이나믹프로그래밍 그리디 이중에서 패스해도 될만한 부분이 있을까요? 시간이 급해서요 ㅠㅠ 꼭 답변 달아주세요 킹독님... 감사합니다.

[@박창현-h9k]

꼭 답변 부탁드립니다 ㅠㅠ

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

재귀가 코딩테스트에 나온다 안나온다 제가 확답을 드릴 순 없지만 도저히 어려워서 진행이 안되면 그냥 나오면 틀린단 마인드로 버리셔도 될 것 같습니다. 제가 창현님 상황이면 시험 전까지 BFS 백트래킹 시뮬레이션만 주구장창 풀어볼 것 같아요.

[@박창현-h9k]

답변 정말 감사드립니다.. 마지막으로 한 번만 더 여쭤보겠습니다. 1.스택 2.큐 3.정렬 4.이진탐색 5.BFS 6.DFS 7.슬라이딩 윈도우 8.다이나믹 프로그래밍 알고리즘 9.그리디 알고리즘 10.Hash 알고리즘 1,2,5,6번은 바킹독님 강의 순서대로 들으면서 완강했습니다. 출제 범위과 위와같은데 이런 범위에서도 단기간내에 점수 딸만한 챕터가 BFS 백트래킹 시뮬레이션 3가지 무한반복이 맞을까요?! ㅠㅠ 구찮게해서 죄송합니다만 심사숙고한 답변 한번만 더 부탁드리겠습니다. 시험까지 40일 남았고 퇴근후 2~3시간 공부 할 수 있는 환경이거든요 ㅠㅠㅠㅠ 진짜 감사합니다.

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

​@@박창현-h9k 3번 문제는 버린다 치고, BFS 백트래킹 시뮬레이션 주구장창 돌리다가 세 유형 모두 실버 문제는 푸는데 문제없겠다 싶으면 나머지들도 공부하는걸 추천합니다

[@박창현-h9k]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog 사랑합니다.. 귀찮은 댓글에 다 답글 남겨주시고.. 이시대의 진정한 남자... 그대로 하겠습니다.

[@seunghyeon3003]

자신만만하게 BFS 20문제 풀고 넘어왔는데 첫번째 문제부터 너무 막막하네요 ㅋㅋ.... 화이팅

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

화이팅!

[@김민수-y6i2l]

24:00 6이라는 값이 갑자기 왜 나왔는지 모르겠습니다. ㅠㅠ -----------------혼자 해결함----------------- 1,2,3 번호의 기둥이 있으니 1+2+3 = 6 # n - 1 개의 원판을 기둥 1에서 기둥2로 옮긴다. # n 번 원판을 기둥 1에서 기둥3으로 옮긴다. # n-1 개의 원판을 기둥2에서 기둥3으로 옮긴다. 이런 생각을 이전에 할수 있었으니 # 1 == a 2 == 6 - a - b 3 == b 으로 표현하면 다음과 같은 명제를 생각할 수 있다. # n - 1 개의 원판을 기둥 a에서 기둥 6 - a - b로 옮긴다. # n 번 원판을 기둥 a에서 기둥b으로 옮긴다. # n - 1 개의 원판을 기둥 6 - a - b에서 기둥 b으로 옮긴다.

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

적힌 설명 그대로이긴 한데, 이를테면 a=1, b=2이면 남은 기둥은 3이고, a=1, b=3이면 남은 기둥은 2이고 이런 상황에서 남은 기둥의 번호를 어떻게 쉽게 계산하나 생각해봅시다. 그러면 기둥 3개의 번호의 합은 1+2+3=6이고, 6에서 a와 b를 빼면 자연스럽게 그 값이 남은 기둥의 번호가 됩니다.

[@김민수-y6i2l]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog 아 제가 처음에 이해를 못했다가 몇 분뒤에 이해가 돼서 똑같은거 모르는 사람 보라고 ------ 밑에다가 해답을 적은거에요. 그래도 친절한 답변 감사합니다

[@nuevo1682]

6:46 까지 공부~!

[@심재혁-i2r]

하노이탑 풀이 보고 이마를 탁 칩니다.... 어찌 이런 신세계 강의를.... 정말 감사드립니다!

[@취미로개발]

재귀가 뭐야? 잠시만 물어볼게 재귀가 뭐야? 잠시만 물어볼게 재귀가 뭐야? 잠시만 물어볼게 재귀가 뭐야? 잠시만 물어볼게 이게 재귀야 아 이게 재귀구나 이게 재귀야 아 이게 재귀구나 이게 재귀야 아 이게 재귀구나 이게 재귀야 아 이게 재귀구나

[@nono-qj6lb]

하노이탑보고 스택부터 생각했던... 직접 넣었다뺏다 하려는 생각부터 하면 스스로 편견깨기가 어렵네요

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

하노이탑 문제를 보고 혼자 재귀를 떠올려 풀어내는건 거의 불가능에 가깝다고 생각하긴 해요.

[@lsion333]

하노이탑 문제에서 N이 1~100인데 왜 (1

[@lsion333]

죄송합니다 다른 문제 풀고 있었네요 ㅠ

[@jinwoo-ng8eu]

강의 잘듣고있습니다. 질문이 하나있어서 그런데, 거듭제곱mod에서 홀수일 경우 val * (a % c) % c가 아니고 val * a % c 를 리턴하는 이유를 알고싶습니다. 강의를 듣고 모듈라연산을 공부하는데 (a*b)%c = ((a%c)*(b%c))%c 라고 해서 짝수인 경우는 이해를 했는데, 홀수인 경우 a^b%c = (a^b/2 * a^b/2 * a)%c 이므로 (val * (a%c))%c가 아닌가하여 여쭙습니다. 감사합니다!

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

val * (a % c) % c 와 val * a % c 의 결과는 동일해서 상관없습니다

[@jinwoo-ng8eu]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog 모듈라가 하도 복잡해서 오히려 그렇게 간단한걸 생각못했네요. 감사합니다!

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

​@@jinwoo-ng8eu 모듈로에서 많이들 헷갈려하네요ㅠ

[@jinwoo-ng8eu]

암호학 찍먹할때 약간 다뤄본거 외에는 안쓰다보니 매번 까먹고 낯선거같아요.. 덕분에 코테도 슬슬 재미를 붙히고 준비도 착실히 되어가고 있습니다. 정말 감사드립니다.

[@도파민-m1w]

절차지향적 사고에서 탈피하는게 너무 어렵지만 덕분에 재귀에 대해 더 알아갑니다 감사합니다!

[@gy1gp6fu1b]

아찔했습니다. 좋은 강의 감사합니다.

[@박창현-h9k]

혹시 1629 곱셉문제 설명하실때 a^n & a^n =a^2n 이부분 이해가잘안가는데요 혹시 이부분이 modulo연산의 속성에 대한 내용이 맞나요? (a%n * b%n)%n = (a*b)%n ((a^k)%n * (a^k)%n)%n = a^2k % n

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

넵

[@잔다안]

재귀가 참 어렵드라구요 최근에 솔브닷 플레찍었는데도 재귀를 잘 못 쓴다는 반성과함께 공부중이네요

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

하다보면 금방 익숙해집니다ㅎㅎ

[@이준석-o1j]

영상 잘봤습니다. 코드를 스스로 짜보고 풀이를 보려고 했는데 아무리 생각해봐도 안되더라구요. 서론처럼 귀납적으로 연습 문제를 접근하려고 해도 0x01. 거듭제곱 문제는 모듈러 공식을 몰랐고 0x02. 하노이탑은 함수 정의(매개변수부분)를 떠올리기가 너무 막막했고 0x03. Z는 half같은 변수를 이용할 방법이 생각이 안났습니다. 이런 건 문제를 많이 푸는거 말고 답이 없는 거겠죠?

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

재귀는 다들 어려워하시더라구요. 너무 조급하게 생각말고 연습문제부터 찬찬히 풀어보세요.

[@rootelon]

혹시 재귀의 경우에도 cout으로 출력해가면서 디버깅하시나요?

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

디버깅 툴을 잘 안쓰는 버릇을 해서 재귀 또한 cout으로만 디버깅을 하긴 해요.

[@김민수-y6i2l]

진짜 대가리 깨질 것 같으면서도 이분 설명은 최고라는 생각이 드네요. 머리를 좀더 돌려 보겠습니다.

[@jackson_park]

Z문제는 내일 다시 풀어봐야겠네요. 지금 이해했다고 해도 내일 되면 다시 헷갈릴 것 같아서요. 지금까지 절차적으로 많이 문제를 접근해서 그런지 수학적 귀납법이 생각보다 많이 어렵네요 흑흑

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

좋읍니다 원래 처음엔 좀 빡세여

[@하카타-m6n]

지금까지 재귀가 나오면 어려웠던 이유가 계속 절차적으로 생각해서였군요.... 귀납적 사고에 익숙해지도록 재귀 문제를 많이 접해봐야겠습니다..!

[@user-kj7vw8dw8]

바킹독님 영상 잘 보고있습니다! 재귀함수를 귀납적으로 생각하게 되었을 때, 함수 정의는 문제의 조건을 보면서 할 수 있게 되었습니다ㅎㅎ! 제가 문제가 있는 지점이 , 재귀함수에서의 시간복잡도를 구하는데 어려움이 있습니다. 재귀함수의 시간복잡도를 생각할 때는 함수호출 횟수가 시간복잡도에 영향을 미친다고 생각했고, 함수호출 횟수는 절차지향적으로 생각하게 됩니다. 이 과정 그대로 구하는 게 맞을까요?

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

재귀에서 시간복잡도를 구하는게 원래 좀 까다롭습니다. 점화식을 세우거나 직접 함수 호출 횟수를 세어보는 방법이 있는데 수학에 친숙하지 않다면 그냥 직접 절차지향적으로 함수 호출 횟수를 세어보는게 낫습니다. 다만 대충 어림을 잡을 땐 예를 들어 함수가 최대 깊이 N까지 들어가고 매번 자기 자신을 2번 부르면 O(2^N)으로 어림잡는다거나 할 수 있습니다.

[@hwkfjjdsidjeje7746]

재귀문제는 귀납적으로 접근해야하는군요

[@minjunkim3516]

바킹독님 안녕하세요 지금까지 알고리즘문제 바킹독님덕분에 너무 기분좋게 생각하고있습니다. 질문이 있어서 문의드립니다. 파이썬으로 해당 알고리즘을 해결하고 있는데 하노이 탑 이동 순서 과정에서 print(a,b)라는 구문이 n번 원판을 a에서 b로 옮기는 과정이라고 씀하시더라구요 그러면 print문을 사용하여 남은 1개의 원판을 1번막대에서 3번막대로 옮기는것에 의문을 가지고있습니다 해당 원판을 옮기는 것이면.. 따로 return을 하거나 재귀를 사용한다고 사용해야하지만 print로 출력하는점이 상이하다고 생각이 들어서 질문드립니다. func(a,b,1) 해당방식을 이용하지않고 print으로 작성한것이 조금 이해가안갑니다.ㅠㅠ 감사합니다. 답변을 기다릴게용 좋은하루보내세요

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

문제에서 요구하는건 수행 과정을 출력하는 것입니다. print(a, b)을 하면 이것이 곧 원판을 a번막대에서 b번막대로 옮긴다는 의미입니다. 대충 어떤걸 헷갈려하시는지는 느낌이 오는데 더 쉽게 설명이 잘 안되네요..ㅠ 참고로 저걸 func(a,b,1)로 바꿔도 결과가 동일하긴 합니다. func 함수에서 base condition이 어떻게 적용되는지를 확인하시는것도 좋아보입니다

[@pervin2705-s1h]

안녕하세요! 강의를 보고 공부하다가든 질문이 있습니다.(질문 양식에 최대한 맞춰보려고 했으나 머릿속의 이해를 기반으로 쓰다보니 추상적으로 변질되네요... 죄송합니다.) Q) 강의에서 말씀해주신대로 절차지향적 사고가 아닌 귀납적 사고로 문제를 분석하는데까지는 이해한 것 같습니다만 막상 곱셈 문제를 코드로 작성하려 하니 결국 절차지향적 사고가 도입되지 않고서는 작성할 수 없는 것 아닌가? 하는 생각입니다. - a의 k승에 대해 계산할 수 있다면, a의 2k승은 (a^k * a^k) % c, 같은 방식으로 a의 2k+1승은 (a^k * a^k * a) % c를 구할 수 있다! - 모듈러 연산에 의해 a^k % c를 계산하게 되고, 이 과정을 k=1이 될 때까지 쪼개져 내려가야만 한다. -> 이 부분이 이해가 안되니 코드를 작성하기 어려웠습니다. - 따라서 재귀는 이전 단계인 k를 구할 수 있음을 기반으로 현재 단계 k+1의 연산을 [k+1에 대한 계산, 앞서 구한 k의 계산] 으로 분할하는 논리를 기반으로 한다. -> 제 생각입니다. - 결국 귀납적 사고는 값을 구하는 전체 과정을 압축, 요약한 것이다. 제가 정리한 건이러한데... 혹시 제가 강의해주신 내용을 잘못이해하고 있는건 아닌가 싶기도 하고 많이 혼란스럽네요ㅠ 매우 감사드립니당!

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

일단 곱셈 문제에서 쓰인 재귀적 사고는 아래와 같습니다. 1. a의 1승을 계산할 수 있다. 2. a의 k승을 계산할 수 있으면 2k, 2k+1승을 계산할 수 있다. 이 두가지만 생각하고 나면 재귀가 잘 동작한다고 생각하고 넘어갈 수 있습니다. 물론 그 생각의 바닥에는 계속 b승에서 출발해 b/2승, b/4승, ... 이렇게 절반씩 줄여나가면 언젠가는 1승에 도달하기 때문이라는 사실을 깔고있는거지만 2:50에서 언급한 것 처럼 저 두가지만 생각한 다음 더 들어갈 필요가 없습니다.

[@seunghyeon3003]

저는 int 오버플로우가 당연히 에러를 뿜을 줄 알았는데 잘못된 값이긴 해도 출력을 하긴 하는군요 ... 스택은 오버플로우 되면 바로 에러가 나오던데 변수는 출력이 되서 놀랐습니다 ..

[@SnackKillerCat]

이번엔 진짜 이해가 안되서 영상까지 찾아왔네요

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

많이 힘들어하는 부분이긴한데 헷갈리는 부분을 집어서 질문 주시면 답변드릴 수 있어요

[@SnackKillerCat]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog 지금은 스스로 고민을 해보고 문제를 많이 풀어봐야 하는 때인거 같아요! 좋은 공부자료가 있어서 뭘 해야할지는 알 것 같습니다. 길을 잃게 되면 오픈카톡이나 이런데서 질문해볼게요

[@Freejia823]

강의 감사합니다 바킹독님!!!

[@이범진-z6i]

진짜 재귀에 대한 통찰력이 대단하시네요 영상 필요한 부분. 보고 있는데 정말 많은 도움이됩니다

[@민장규-h9b]

안녕하세요! 항상 강의 잘 보고있습니다. 감사합니다. 18:14 에1629번 곱셈 문제의 시간복잡도가 O(log b)라고 하셨는데 어떻게 나온 계산인지 잘 이해가안됩니다. 직관적으로는 log라는 것은 알고있는데 나오는 과정을 잘 생각을 못하겠습니다. 이해하기 위해 for (int i = 1; i < N; i * 2) 의 시간 복잡도 계산은 2^k = N => klog2 = logN => k = log_2 N ===> O(n) = logN 으로 알고 있습니다. 위의 문제를 일반화하면 아래와 같다고 생각합니다. for (int i = b; i >= N; i / 2) 의 시간 복잡도 계산을 해봐도 논리적으로 맞는 식을 세우지도 못하겠습니다... (아래가 맞는지 틀리다면 수정 부탁드려도될까요?) b * (1/2)^k = N => logb + k log1/2 = log N => k =(logN - logb)/log1/2 ===> O(n) = logN 조금만 도와주실 수 있을까요? (추가) 아니면 N = 1로 해서 나오는 이게 맞나요? for (int i = b; i >= 1; i / 2) b * (1/2)^k = 1 => log b + k * log(1/2) = log1 => k = log b / log2; ===> O(n) = log b

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

댓글에 적어놓으신 식을 잘 이해못하겠긴 한데, f(n)을 b = n일 때의 연산 횟수라고 하면 f(n) = f(n/2) + 1이라는 식을 얻을 수 있기 때문에 n = 2^k라고 할 때 f(n) = f(n/2)+1 = f(n/4)+2 = ... = f(1) + k = k가 되어 O(k) = O(lg n)입니다.

[@민장규-h9b]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog 감사합니다... 덕분에 이해했습니다!

[@mwk2373]

안녕하세요 바킹독님 강의를 듣고 궁금한 점이 있는데 수학적 귀납법에서는 k번째가 참이라고 가정하고 k+1번째를 증명하는데, 재귀가 가능한지 판단할 때는 1번째, k번째가 가능한지 직접 확인을 해보고, k+1번째도 가능한지 직접 확인을 하여 알 수 있는 것인가요?

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

아뇨 마찬가지로 1번째가 가능한지 / k번째가 가능하다고 가정할 때 k+1번째가 가능한지를 확인하면 됩니다.

[@mwk2373]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog 감사합니다!!

[@user-oortcloud]

항상 감사합니다! 이해는 가지만, 다른 문제에 적용하려면 조금 더 익숙해져야 할 것 같습니다ㅋㅋㅋ 절차적 지향이 아닌 귀납적 방식으로 재귀에 접근하니 훨씬 수월한 것 같습니다!

[@재현임-b9t]

설명은 진짜 잘해주시는데 제가 따라가질 못하네요 재귀는 여러번 봐야할거같네요.. 아무튼 항상 감사합니다 킹갓독님

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

재귀 많이 어렵읍니다,,, 이해 안가는 부분 언제든 편하게 질문 주세요

[@수민-g6i7l]

재귀를 이해하면 재귀가 완벽히 이해됐다는 생각이 드나요? 제가 이해가 된건지 안된건지 모르겠네요 ㅋㅋ 되게 찜찜한 기분

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

뭔가 그 찜찜한 느낌을 안은채로 문제가 잘 풀리면 제대로 이해한게 맞습니다

[@담다-b5u]

하.. 백준 풀때마다 재귀 넘겼는데 피보네 하..

[@김동호-y8h]

재귀는 결국 규칙을 잘 찾으면 되는 문제인 거 같네요. 그런데 처음 거듭제곱 문제에서 힌트가 조금 더 헷갈리는 거 같아요ㅜㅜ 차라리 module의 규칙을 설명해주시면서 12^116에서 12^1까지 갔다가 다시 올라오는, recursion의 순서도를 글이나 그림으로 설명해주시면 바로 와닿을텐데요. 그래도 덕분에 한 단계 발전했다고 생각합니다. 감사합니다!

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

12^116에서 12^1까지 갔다가 다시 올라오는건 절차지향적인 이해여서,,, 그래도 조언 감사하고 참고하겠습니다!

[@hyki1297]

유익한 글 감사합니다.

[@bogo4064]

재귀 빡시네요 ㅜ 1074번도 여러번 반복해서 보겠습니다 흑흑

[@롯룻]

선생님 좋은 강의 감사드립니다. 재귀 이해가 갈듯 말듯 한데 BOJ 다른 재귀 문제들 풀면서 공부하면 될까요?ㅜ

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

네 근데 완벽하게 이해가 가지 않은 것 같다고 하더라도 문제집에 있는 문제만 다 풀 수 있다면 충분히 능력이 길러진걸꺼에요

[@hoony30]

혹시 왜 12^58 mod 67 이 4인것을 알면 12^116 mod 67 은 자동적으로 16이 되는지 알 수 있을까요?? 지수가 2배가 되면 뭔가가 변하는 공식같은게 있는건가요?

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

먼저 a^b * a^b = a^2b 입니다. 예를 들어 5의 6승은 5를 6개 곱한 것(5*5*5*5*5*5)이기 때문에 5*5*5*5*5*5 = (5*5*5) * (5*5*5) = 5^3 * 5^3 으로 생각할 수 있겠습니다. 그러면 12^116 = 12^58 * 12^58이기 때문에 12^58 = 4란걸 알면 12^116 = 4*4 = 16임을 알 수 있습니다.

[@hoony30]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog ㅇㅎ 감사합니다 바로 이해가 됐네요

[@동동-o7w]

역시 재귀 어렵네요 Z문제 좀 이해되는데 한시간 바라봤씁니다 ,, ㅜㅜ 좋은강의 감사합니다

[@kundol]

맴찣ㅋㅋㅋㅋ사랑합니다 바킹덕님

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

어우 오랜만이에요 잘 계신가요??

[@kundol]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog 저야 머 그냥저냥 삽니다ㅎㅎ

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

@@kundol 앗 그렇군여.. 유튜브 좋아요 꼬박꼬박 누를게여^___^

[@kundol]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog 왈왈!

[@창무-j5w]

백준 n,m 순열 문제 풀다가 막혀서 권오흠교수 알고리즘이랑 이 동영상 듣고 갑니다. 도움이 많이 됩니다~

[@zero2vec]

17:14 에서 val = a^6 mod m 라는 것과, 저 상황에선 함수에서 a^7 mod m 값을 반환해야 하니까 결론적으로 11번째 줄에서 a^6 mod m을 a^7 mod m로 만드는 동작인 것까지 이해가 갑니다. 그런데 11번째 줄 동작이 잘 이해가 안가서 모듈러 연산의 특성을 찾아보니까, (A*B)%C = (A%C * B%C) % C 라는 성질을 찾았습니다. 이를 11번째 줄에 적용하면 (a^6 * a^1) % m = (a^6%m * a^1%m) % m인데, 11번째 줄은 (a^6 * a^1) % m = (a^6%m * a^1) % m 으로 해석이 되더군요.. 이렇게 a^1을 m으로 나누지 않아줘도 정답인 이유를 잘 모르곘어서 질문드립니다.

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

val * (a%m) % m과 val * a % m의 결과는 똑같습니다. 10으로 나눈 나머지에서 끝자리만 생각하는 비유를 들었는데 비슷하게 생각해서 3 * 1616을 계산한 후 10으로 나눈 나머지를 구하는거랑 3 * 6을 계산한 후 10으로 나눈 나머지를 구하는거랑 똑같다는 관점에서 생각해보면 좋을 것 같습니다.

[@hj-br8cn]

바이킹독님 강의로 알고리즘 공부를 시작했는데 너무 어려워 질문드립니다ㅠㅜ - 1승을 계산할 수 있다. - k승을 계산 했으면 2k승과 2k+1승도 O(1)에 계산할 수 있다. 강의 내용에서 >>위의 두 문장이 참이기 때문에 a의 임의의 지수승을 귀납적으로 계산할 수 있다

[@hj-br8cn]

하노이법에서도 n=k일때 잘 동작한다치면 n=k+1 도 잘 동작하는게 참인걸 알아보려면 절차적으로 생각하게 되지 않나요..? 참인지 어떻게 판단하는건가요? 써보니 질문이 같은 맥락이라 댓글로 씁니다..

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

1:20부터 시작하는 도미노 관련 내용은 제대로 숙지를 하셨나요?

[@seungjunyoo8739]

바킹독님, 하노이탑이랑 Z는 점화식을 이용해 푸는 수학적인 아이디어가 필요하고 나머지 문제집의 문제들은 꽤 정형적인 풀이인데(범위를 축소시키며 시작점마다 재귀호출, 조건 충족되면 재귀 미호출, divide and conquer) 이 정형적인 풀이만으로도 기업 코딩테스트는 준비가 가능할까요?? 수학적인 아이디어가 필요한것은 솔직히 자신이 없습니다

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

그런 문제가 절대 안나온다고 단언할수는 없지만 백트래킹을 풀어내는데 무리가 없는 정도로만 재귀를 이해하고 있으면 된다고 생각합니다.

[@dongwooklee4733]

플래시 게임을 이용해서 이해하기 더 쉬웠어요 ㅎㅎ 굿입니다! 교육 쪽에서도 재능이 정말로 많으신것 같네요 부럽습니다 ㅎㅎ

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

재귀가 포인터랑 더불어서 사람들이 프로그래밍을 접게 만드는 큰 고비중 하나여서 특히 이 파트는 심혈을 기울여 만들었는데 이해가 잘 가신다니 다행입니다ㅎㅎ

[@daw2able]

바킹독센세의 귀여운목소리 설명으로 재귀가쏙쏙~

[@BalanceGamers]

바킹독님은 하노이탑 재귀를 스스로 파악하셨나요?.. 아니라면 쉽게 익히신건가요?... 게임 수십번을 해도 재귀로 표현 엄두도 못내겠네요.. 하노이탑을 보고 점화식 유추는 전혀 하지 못했구요

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

하노이탑 문제를 풀어본게 너ㅓㅓㅓㅓㅓ무 옛날이라 사실 잘 기억은 안나네요,,, 근데 저도 처음 프로그래밍 할 때 재귀를 되게 어려워했던 기억이 있어요ㅋㅋ

[@SUCY35]

15:39

[@손현준-z4z]

1번 들었는데 역시 절자적 사고는 버리는 게 쉽지 않네요 ㅎㅎ 말씀대로 반복해서 재귀에 익숙해진 뒤 백트레킹에 들어가야겠습니다.

[@__-dc8mj]

1629번 곱셈에서 코드를 짜고 바킹독님 정답이랑 비교해봤을 때 크게 다른 부분이 없는데 왜 틀렸는지 모르겠어요.. 제가 뭔가 잘못알고 있는게 있나요? 너무 수업 잘 듣고 있습니다. 미리 답변 감사드립니다. #include using namespace std; using ll = long long; ll func(ll a, ll b, ll c) { ll ans; if (b == 1) return a % c; ans = func(a, b / 2, c); if (b % 2 == 1) // 홀수라면 ans = ans * ans * a % c; else ans = ans * ans % c; return ans; } int main() { ios::sync_with_stdio(0); cin.tie(0); ll a, b, c; cin >> a >> b >> c; cout

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

ans = ans * ans * a % c; 에서 overflow가 발생해요 반례 10000000 3 10000001

[@박건희-s4d1p]

재귀가 진짜 어렵네요 ㅠ

[@이규열-n8u]

12^58≡4(mod67) -> 12^116≡16(mod67) 이 뜻하는게 무엇이죠? 왼쪽 항을 2제곱하면 똑같은 수로 mod 연산을 하면 나머지가 2제곱이 된다는 건가요? 이 공식대로 하면 12^28≡2(mod67) -> 12^14≡√2(mod67)이렇게 된다는 건가요?

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

SeungHun Yim님도 비슷한 질문을 남겨주셨는데 거기에 남겼던 답글을 그대로 다시 공유합니다. 먼저 a^b * a^b = a^2b 입니다. 예를 들어 5의 6승은 5를 6개 곱한 것(5*5*5*5*5*5)이기 때문에 5*5*5*5*5*5 = (5*5*5) * (5*5*5) = 5^3 * 5^3 으로 생각할 수 있겠습니다. 그러면 12^116 = 12^58 * 12^58이기 때문에 12^58 = 4란걸 알면 12^116 = 4*4 = 16임을 알 수 있습니다. 12^28≡56(mod67) -> 12^14≡49(mod67)이고 49*49 ≡ 56(mod 67)입니다.

[@이규열-n8u]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog 12^116 = 12^58 * 12^58이기 때문에 12^58 = 4란걸 알면 12^116 = 4*4 = 16임을 알 수 있습니다. 이 말을 인용해서 바킹독님이 12^28≡56(mod67)이란걸 알려주셨으니 12^58=12^28*12^28이기 때문에 12^28=56이란걸 알면 12^58=56*56=3136이다란 말은 말이 되지않습니다.

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

@@이규열-n8u 죄송한데 댓글 의미를 잘 파악 못했습니다. "바킹독님이 12^28≡56(mod67)이란걸 알려주셨으니 12^58=12^28*12^28이기 때문에 12^28=56이란걸 알면 12^58=56*56=3136이다란 말은 말이 되지않습니다." 이 부분이 무슨 의미인지 다시 설명해주실 수 있으신가요?

[@이규열-n8u]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog 12^116 = 12^58 * 12^58이기 때문에 12^58 = 4란걸 알면 12^116 = 4*4 = 16임을 알 수 있습니다. 이렇게 말씀을 하셔서 똑같은 방식으로 숫자만 바꿔서 증명해본 것입니다 12^28≡56(mod67) -> 12^14≡49(mod67)이고 49*49 ≡ 56(mod 67)입니다. 바킹독님이 이렇게 말씀하셧으니 12^116 = 12^58 * 12^58이기 때문에 12^58 = 4란걸 알면 12^116 = 4*4 = 16임을 알 수 있습니다 라고 하면 숫자를 바꿔서 12^58 = 12^28 * 12^28이기 때문에 12^28=56란걸 알면(12^28≡56(mod67) 이므로) 12^58=56*56=3136라고 계산을 해버리면 말이 안되지 않습니까? 그래서 바킹독님이 하신 증명이 이해가 안되서 질문드립니다

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

@@이규열-n8u 일단 28*2 = 56이니 "12^58 = 12^28 * 12^28이기 때문에 12^28=56란걸 알면(12^28≡56(mod67) 이므로) 12^58=56*56=3136라고 계산을 해버리면 말이 안되지 않습니까? " 이 문장은 "12^56 = 12^28 * 12^28이기 때문에 12^28=56란걸 알면(12^28≡56(mod67) 이므로) 12^56=56*56=3136라고 계산을 해버리면 말이 안되지 않습니까? " 으로 바뀌어야 하고, 12^56 ≡ 12^28 * 12^28 ≡ 56 * 56 ≡ 3136 맞습니다. 그리고 3136은 67로 나눈 나머지가 54이어서 최종적으로 12^56 ≡ 12^28 * 12^28 ≡ 56 * 56 ≡ 3136 ≡ 54(mod 67)입니다.

[@bogo4064]

아 1074번 half를 계속해서 더해주는게 만약에 44번째 칸을 방문했다는 것은 그 전 큰 사각형인 1, 2를 지나왔기 때문에 2*half*half를 해주는거 맞나요?

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

네네 정확합니다

[@빠스야빠스-g4y]

항상 강의 잘보고있습니다! 재귀가 처음에는 이해가 잘안되서 비슷한 방식이긴 하지만 저는 하노이탑을 A(n) = 2*A(n-1) + 1로 구현하였는데 재귀적으로 생각하니 더 간단하네요!

[@aigsmusic]

안녕하세요! 하노이탑 문제에서 6-a-b 대신 a+b-2를 넣어줬더니 0이 출력되는등 결과가 달라지는데, 똑같이 2를 의미하는 값인데 왜 결과가 달라지는지 궁금합니다! (좋은강의 감사드립니다! 나머지 영상들도 방학때 봐야겠네요 ㅠㅠ)

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

6-a-b 로 쓴 이유가 a와 b가 기둥 1, 2, 3 중 하나일 때 a도 b도 아닌(=비어있는) 기둥의 번호를 구하기 위해서였잖아요. 그러면 a = 1, b= 2일 때 기둥 3을 계산해내야 하는데 a+b-2는 잘못된 결과를 주죠.

[@aigsmusic]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog 아하! 그 부분을 생각 못했네요 ㅠㅠ a=1, b=2 일때도 고려하기 위함이군요!! 감사합니다!👍👍

[@han-hb1kw]

~8:40

[@bogo4064]

하노이의 탑 base condition에서 cout

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

문제의 출력 조건이 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. 이어서 자명하게 cout

[@bogo4064]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog 감사합니다 ㅎ

[@박희재-k2p]

boj 1629번(곱셈) 코드 7번에 if(b==1)을 if(b

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

코드 링크를 주시면 확인해볼게요. 아마 다른 오류가 있을거에요

[@박희재-k2p]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog 링크를 어떻게 드리면 될까요??ㅠㅠ github이런 링크드리면 되나요??

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

​@@박희재-k2p 그래도 되고 그냥 제가 강의자료에서 링크 제공하는 것 처럼 코드 공유하기를 눌러서 url을 주세요(ex : www.acmicpc.net/source/share/a9f89b45ac624c2a8d13f27a01dd78d1 )

[@박희재-k2p]

@@BaaaaaaaaaaaaaaaaaaaaarkingDog 지금 링크보내신거에 if(b==1)을 if(b

[@BaaaaaaaaaaaaaaaaaaaaarkingDog]

@@박희재-k2p base condition을 b == 1로 두면 a의 1승을 반환해야하니 return a % m이고 b == 0으로 두면 a의 0승을 반환해야 하니 return 1을 해야합니다ㅎㅎ 코드 : boj.kr/78d012315cd64eaa9448e15abbc77c06

[@dddddd15926]

while(true) { cout