![]()
DFS? BFS? DFS와 BFS는 그래프를 탐색하는 방법의 일종이다. 그래프란 정점들과 그 정점들을 연결하는 간선들로 이루어진 자료구조이다. DFS는 깊이우선탐색으로, 그래프를 최대한 깊이 탐색한 후 옆으로 이동하여 똑같이 탐색하는 방법이다. BFS는 너비우선탐색으로, 그래프를 옆에서 옆으로 탐색한 후 점점 밑으로 내려가며 탐색하는 방법이다. DFS 예시 https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=csharp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위 문제는 ..
![]()
그리디 알고리즘이란? 그리디 알고리즘이란 우리말로 탐욕법, 탐욕 알고리즘, 욕심쟁이 알고리즘 등 여러가지 말로 불립니다. 이는 눈 앞에 있는 것이 더 좋아보이면 그것을 추구하는 알고리즘입니다. 대표적인 예시를 들어보겠습니다. : 상품에 대한 가격이 매개변수로 주어집니다. 그리고 서로 다른 금액의 동전이 들어있는 1차원 배열이 주어집니다. 상품을 주어진 배열의 동전으로 계산하려고 할 때 지불해야하는 동전의 개수의 최솟값을 리턴해야 합니다. void Start() { int[] coins = { 10, 500, 50, 100 }; Debug.Log(Greedy_Price(1990, coins)); } public int Greedy_Price(int price, int[] coins) { int answer..
![]()
동적 프로그래밍이란? 큰 문제를 작은 단위로 쪼개서 반복 분할하여 푸는 접근 방식입니다. 네 맞습니다. DFS와 같은 개념입니다. 기본적으로 DFS문제는 재귀함수를 사용해서 풀어가는 방식이 일반적입니다. 그럼 동적프로그래밍은 DFS와 같은 것인가?? 결론부터 말씀드리면, 답은 No입니다. 동적 프로그래밍은 작은 하위 문제의 해결 방법을 계산하여 저장하고, 이를 이용하여 큰 문제의 해결 방법을 도출합니다. DFS와 동적프로그래밍의 차이점!! 여기 숫자가 들어있는 정삼각형 구조가 있습니다. 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 리턴하는 문제입니다. 문제를 처음 접하게되면 기본적으로 DFS로 문제를 풀어야겠다는 생각이 들 것입니다. DFS로 접근하게 되면, 7+3+8+2+..
