컴퓨터 기초11 깊이 우선 탐색법(with. kotlin) 이런 그래프가 있다 가정해보자(발편집 ㅈㅅ) 이 그래프를 깊이 우선으로 찍으려고 하면 어떻게 해야할까?애초에 깊이 우선이란 무엇인가? 한번 딥하게 끝까지 갔다가 다시 돌아오는걸 뜻한다.이걸 일단 말로 풀어보자. 1번 노드부터 돈다. 1번 노드에는 2 4 5번이 연결되어있다.일단 5번부터 가보자. 5번에는 8번이 연결되어있다.8번을 가보자. 8번은 6번과 연결되어 있다. 6번을 가보자. 6번은 3번과 연결되어 있다.3번을 가보자. 3번은 2번과 연결되어 있다.2번은 1 5 번이 연결되어있다. 그런데 1 5번은 먼저 탐색한 전적이 있지 않은가? 그럼 돌아간다? 어디까지? 노드가 갈라지는 지점까지 ^-^ ..2번은 방문한 전적이 있다. 그럼 2번도 빼버리고 다시 돌아가 1번 노드로 다시 돌아간다.4번은 7번과.. 2024. 5. 23. 동적 계획법(Dynamic Algorithm)(with. Kotlin) 동적 계획법은 정확하게는 알고리즘.. 이라는 느낌보다는 문제 해결 방법론에 가깝다. 동적 계획법은 같은 계산을 계속 반복하는 최적 부분 구조 알고리즘에 가장 편안한 방법이다. 동적 계획법의 경우 이전에 계산해둔 값을 저장해두고 다음 계산을 위해 재활용해서 사용하는 방식이기 때문이다. 동적 프로그래밍은 크게 상향식 접근의 타뷸레이션과 하향식 접근의 메모이제이션이 방법론으로 제기된다. 동적 계획법의 예시인 피보나치 수열을 타뷸레이션과 메모이제이션의 예시로 확인한다. 피보나치 수열을 동적 계획법을 사용해야하는 이유는 다음과 같다. 피보나치 수열은 다음과 같은 계산법을 가진다. f(n) = f(n-1) + f(n-2) 이제 여기에 1 2 3 4... 순서대로 숫자를 넣어보자. f(0) = 1 f(1) = 1 f.. 2024. 4. 5. Java, Kotlin] 에라토스테네스의 체 에라토스테네스의 체는 소수를 구하는 아주 기본적인 알고리즘이다. 알고리즘은 다음과 같다 1. 내가 원하는 수 만큼의 숫자를 깔아놓는다. 2. 0과 1은 소수가 아니므로 뺀다. 3. 2는 소수이고, 2의 배수부터는 소수가 아니므로 2를 제외한 2의 배수는 모두 빼버린다. 4. 3은 소수이고, 3의 배수부터는 소수가 아니므로 3을 제외한 3의 배수는 모두 빼버린다. 4. 4는 소수가 아니므로 넘어간다. 5. 5는 소수이므로 5의 배수부터는 ... 이걸 반복한다. 근데 가만히 생각해보자? 2의 소수라서 2*2 -> 2*3 -> 2*4를 뺐다. 3의 소수에서 3*2 .. 는 2의 배수에서 2*3으로 빼버렸지 않나. 그러므로 3*3부터, 즉 3^2부터 시작해도 된다. 5도 마찬가지로 5*2는 2의 배수에서, 5*.. 2024. 4. 1. Kotlin 예시 작성] 유클리드 호제법(Euclidean Algorithm) 유클리드 호제법은 최대공약수와 최소공배수를 구할 수 있는 알고리즘이다. 그니까.. 말은 이건데... a와 b의 최대공약수는 a와 b를 나눈 나머지 r 이 존재할 때, b와 r의 최대공약수와 같다.. 라는건데(???) 그래서 나머지가 0이 나오면, 그 시점의 b가 최대공약수가 된다는거다(?????) 예를 들어 742와 854의 최대 공약수를 구해보자. 일반적인 방식으로 구해보면... 약수집합 = [2], 371 427 -> 약수집합 = [2, 7], 53 61 최대공약수가 2*7 = 14 가 나오는 것을 알 수 있다. 유클리드 호제법은 다음과 같이 구한다. 854 = 742 * 1 + 112 742 = 112 * 6 + 70 112 = 70 * 1 + 42 70 = 42 * 1 + 28 42 = 28 * .. 2024. 3. 26. 이전 1 2 3 다음 반응형
