자료구조 및 알고리즘23 [알고리즘] 자바에서의 그리디(탐욕) 알고리즘 그리디(탐욕) 알고리즘 - 다익스트라 알고리즘과 같은 고급 그래프 탐색 알고리즘에서 그리디(탐욕) 알고리즘을 사용하고 있기 때문에 미리 익혀놓고 넘어가는 것이 좋다. - 최적의 해에 가까운 값을 구하기 위해 사용된다. - 여러 경우 중 하나를 결정해야 할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식이다. - 전체에서 가능한 경우의 수를 모두 따져가며 최적의 해를 찾는 것이 아니라, 각 단계를 거칠 때마다 현재 단계를 기준으로 가장 최적의 경우가 무엇인지를 판별해서 선택하는 것이다. - 그렇기 때문에 최적의 해에 가까운 값을 구할수는 있겠지만, 그것이 반드시 최적의 해라고 말할 수는 없다. 탐욕 알고리즘의 한계 - 탐욕 알고리즘은 근사치 추정에 활용된다.. 2021. 12. 10. [알고리즘] 자바에서의 BFS 와 DFS BFS(Breadth-First-Search) 와 DFS(Depth-First-Search) BFS 와 DFS 는 대표적인 그래프 노드 탐색 알고리즘이다. - 너비 우선 탐색(BFS) : 정점들과 같은 레벨에 있는 노드들(형제 노드들) 을 먼저 탐색하는 방식 - 깊이 우선 탐색(DFS) : 정점의 자식들을 먼저 탐색하는 방식 - 둘 다 트리와 같은 그래프 구조(사이클이 없는 그래프) 에서 데이터를 탐색하는 방식이다. 위와 같은 트리의 경우 BFS 와 DFS 는 각각 어떻게 동작할까? * BFS 방식 : A - B - C - D - G - H - I - E - F - J - 한 단계씩 내려가면서 해당 노드와 같은 레벨에 있는 노드들(형제 노드들)을 먼저 순회한다. * DFS 방식 : A - B - D - .. 2021. 12. 7. [알고리즘] 자바에서의 그래프 - 기초 그래프(Graph) 그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node) 와 간선(Edge) 로 표현하기 위해 사용한다. 관련 용어 * 중요 용어 - 노드(Node) : 현재 위치를 말한다. 정점(Vertex) 라고도 한다. - 간선(Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선 이라고 보면 된다.(link 또는 branch 라고도 한다.) * 참고 용어 - 인접 정점(Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드) - 정점의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 진입 차수(In - Degree) : 방향 그래프에서 외부에서 오는 간선의 수 - 진출 차수(Out - Degree) : 방향 그래프에서.. 2021. 12. 6. [알고리즘] 자바에서의 이진 탐색 이진 탐색(Binary Search) - 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법이다. * 분할 정복과 알고리즘과 이진 탐색 - 분할 정복 - 문제를 하나 또는 둘 이상으로 나눈다. - 나눠진 문제가 충분히 작고 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다. - 이진 탐색 - 리스트를 2개의 서브 리스트로 나눈다. - 검색할 숫자 > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다. - 검색할 숫자 < 중간값 이면, 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다. - 이진 탐색은 데이터가 정렬되어 있는 상태에서 진행한다. 자바 코드로 직접 작성해보자., - BinarySearch.java import java.util.ArrayList; import.. 2021. 12. 4. 이전 1 2 3 4 5 6 다음
