Algorithm (4) 썸네일형 리스트형 DFS&BFS (이코테 2021 강의 몰아보기) 3. DFS & BFS그래프 알고리즘, 경로를 찾는 문제 시 상황에 맞게 활용탐색(Search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말함대표적인 그래프 탐색 알고리즘으로 DFS, BFS가 있음Stack선입후출(FILO) 구조의 자료구조입구와 출구가 동일한 형태로 스택을 시각화할 수 있음 DFS(Depth First Search)루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법깊이 우선 탐색이라고도 부르며, 깊은 부분을 우선적으로 탐색하는 알고리즘스택 & 재귀함수를 이용해 구현 → 모든 경로를 방문해야 할 경우에 사용그래프의 구성 요소, 사이클, 위상 정렬 등을 찾는데 유용함. 탐색 시작 노드를 스택에 삽입하.. 백트래킹, Back Tracking 백트래킹모든 경우의 수를 고려하는 알고리즘모든 경우의 수를 탐색하면서, 더 이상 진행할 필요가 없는 후보는 탐색 X, 뒤로 돌아감진행할 필요가 없는 경우는 따지지 않으므로 브루트포스에 비해 시간 절약탐색 알고리즘으로, DFS, BFS로 모두 구현 가능.재귀적으로 문제를 해결. 백트래킹 절차DFS 수행 - 재귀를 통해 DFS 수행노드 검토 - 진행이 필요한 노드인지 검토 필요( 더 이상 진행할 필요가 없을 시 백트래킹 수행)서브트리 이동 - 방문 노드위 하위로 이동(재귀를통해 DFS 수행)백트래킹 수행 - 유효하지 않은 노드일 경우 상위노드로 이동(백트래킹 수행) 백트래킹 유망성 판단백트래킹은 노드를 검토해 하위로 이동하거나, 백트래킹을 수행함.이를 유망성이라고 함.해가 될만한지 판단, 유망하다면 다음 노.. 동적 프로그래밍, Dynamic Programming(DP) DP란?기본적으로 DP란 recursion 을 활용한 최적화 방법문제를 여러 개의 부분 문제로 나누어 해결하고,이를 저장해 둠으로써 다시 계산할 필요 없이 사용할 수 있도록 하는 것! → 가장 작은 부분의 결과를 저장 후, 이를 이용해 상위 문제를 풀어가는 방식 다음과 같은 경우에서 DP를 사용할 수 있다. 반복을 시행하는 부분이 존재. 동일 한복 연산 결과가 일정해야 함. 대표적인 예로 피보나치 수열 문제가 있다!// recursion을 사용한 문제 해결// 이 경우 실행 단계에 따라 계산 횟수가 기하급수적으로 증가함.int fib(int n) { if (n 재귀함수를 사용한다면 동일한 연산을 계속 반복해야 함.DP를 사용하게 되면 연산 결과를 memoiaztion한 후, 저장 해 사용.. 17478_재귀함수가 뭔가요? 알고리즘 분류 구현, 재귀 문제 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대학교가 자신과 맞는가에 대한 고민을 항상 해왔다. 중앙대학교와 자신의 길이 맞지 않다고 생각한 JH 교수님은 결국 중앙대학교를 떠나기로 결정하였다. 떠나기 전까지도 제자들을 생각하셨던 JH 교수님은 재귀함수가 무엇인지 물어보는 학생들을 위한 작은 선물로 자동 응답 챗봇을 준비하기로 했다. JH 교수님이 만들 챗봇의 응답을 출력하는 프로그램을 만들어보자. 입력 교수님이 출력을 원하는 재귀 횟수 N(1 ≤ N ≤ 50)이 주어진다. 출력 출력 예시를 보고 재귀 횟수에 따른 챗봇의 응답을 출력한다... 이전 1 다음
