Gpt도 틀릴때많음

본인이 체크해봐야함

보통 언어가 바뀌면 call by value, call by reference를 맞추는게 중요해요.

1. 알고리즘은 스스로 짰으니까 꼭 python 문법은 몰라도 되지 않느냐는 질문 같은데, 꼭 백준 가이드라인 따라가야 할 필요가 없다면, 자신이 결정하는 문제 같아. 뒤에 따라오는 말을 보니 딱히 파이썬 공부할 생각도 없어 보이는데 그냥 하고 싶은 데로 하면 되는 거라고 생각함

2. ChatGPT를 기술적으로 해석하면 컴퓨터가 이해하는 방식의 의역 덩어리기 때문에, 검증은 반드시 이루어져야 함. 대충 읽어보면 맞게 짜져 있다고 생각하는 게 거의 틀리지 않을 거 같긴 한데, 코드가 좀 복잡해지면 대충 맞게 짜준다

그래도 개괄적으론 문제 없을 거 같음. gpt 파이썬 코드 잘 짜니까.

1번은 잘모르겠고

2번은 레벨 2-3쯤가면 틀리기시작할거임 그때부턴 코드 좀 제대로 봐야함

이전 글에 동적계획법과 백트래킹에 대한 논지를 달아둠. 니가 알고리즘 패러다임 자체를 잘못 이해하고 있음

부가설명을 하면 피보나치 수열은 백트래킹 방식과 동적 계획법 둘 다 써서 해결이 가능한 문제임.

그러나 fn = fn-1 + n의 형태로 피보나치 수열은 점화식을 만들 수가 있음

식이 구성된다는 말은 최적 해가 있다는 뜻이 됨. 그래서 메모이제이션, 즉 이전 값을 메모해서 저장해두면 다음 값을 계산 하는 것에 이용할 수 있는 수열이 됨 피보나치 수열은.

그러므로 재귀를 쓰지 않고 메모리를 소모해서 이전 값을 “저장” 하면 계산 횟수를 급격히 감소시킬 수 있음

(n 이전 값인 fn-1 계산 값을 저장하는 순간 1부터 n-1번까지 계산 해야하는 함수콜 전체를 줄일 수 있음. 이게 우습게 보이나 총합을 계산하면 (n-1)(n-2)/2 번임. O(n^2) 계산이라 존나 Big-O관점에서 계산 횟수가 매우 큰 거임)

예전에는 메모리가 더 귀하기 때문에 메모리가 적은 환경에서는 피보나치 수열의 경우 어쩔 수 없이 재귀가 더 빠를 수 밖에 없지 물리적인 환경이 안 되니까.

근데 현재처럼 메모리가 넉넉한 환경에선 빅O 판별할 때 시간자원이 공간자원보다 더 중요하게 됨.(공간비용 < 시간비용)

그래서 메모리를 상대적으로 잡아 먹음에도 불구하고 동적계획법을 쓰면 재귀를 쓰는 백트래킹보다 속도가 빠름. 그래서 피보나치 수열 계산할 때 동적 계획법을 쓰는 거임.

하노이의 탑이 대표적 재귀문제인데 하노이의 탑 문제를 수학적 수식으로 표현할 수 있음?

불가능하지? 인간처럼 반복 동작이 있긴 있으나 이걸 뭐 수식으로 표현하는 건 불가능 하잖아. 그러니 저장할 수치가 없어서 하노이의 탑은 인간이 하는 것처럼 반복 행동을 할 수 밖에 없음. 그런 고로 재귀인 백트래킹을 쓰는 거임.

말이 길어졌다만

수학적인 어떤 식(대표적으로 점화식)으로 표현이 가능한 문제 = 동적계획법

표현이 불가능하고 인간이 하는 것처럼 단순한 반복행동을 통해 찾음 = 백트래킹(재귀)

이렇다고 생각하면 된다

이해가 안 된다면 전공 서적 급 알고리즘 책 사서 읽어라