Computer Science/Algorithm8 [Algorithm] 완전탐색 - DFS DFS 이란 ? Depth-First-Search의 약어로, 깊이를 우선적으로 탐색하는 알고리즘이다. 그래프 알고리즘에서 기초가 되는 탐색 방식이다. DFS 특징 ? DFS의 특징 몇 가지를 알아보자. 문제의 유형에 따라 데이터 저장 방법이 인접 행렬과 인접리스트로 나뉜다. 문제의 유형에 따라 데이터의 접근 방법이 달라진다. 최대한 깊숙한 곳부터 먼저 탐색을 진행한다. 스택의 자료구조를 이용하거나 재귀를 통해 구현한다. 백트래킹, 단절선 찾기, 단절점 찾기, 위상 정렬, 사이클 찾기에 활용된다. DFS 구현 순서 ? 구조상 Stack Overflow에 주의하며, 구현 순서를 알아보자. 시작 노드를 스택에 삽입 후 방문 처리한다 스택의 최상단 노드에 방문하지 않은 인접한 노드 확인한다. 인접한 노드 발견 .. 2023. 8. 8. [Algorithm] 완전탐색 - BFS BFS 이란 ? Breadth-First-Search의 약어로, 가까운 곳부터 우선적으로 탐색하는 알고리즘이다. 그래프 알고리즘에서 기초가 되는 탐색 방식이다. BFS 특징 ? BFS의 특징 몇 가지를 알아보자. 문제의 유형에 따라 데이터 저장 방법이 인접 행렬과 인접리스트로 나뉜다. 문제의 유형에 따라 데이터의 접근 방법이 달라진다. 인접한 곳부터 먼저 탐색을 진행한다. 큐의 자료구조를 이용하여 구현한다. 가중치가 없는 최단 경로, 위상 정렬에 활용된다. BFS 구현 순서 ? 시작점과 방문 순서를 주의하며, 아래와 같은 순서를 잘 따르자. 시작 노드를 큐에 삽입 후 방문 처리한다. 큐에서 노드를 꺼낸다. 꺼낸 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 후 방문 처리한다. 큐가 빌 때.. 2023. 8. 8. [Algorithm] 완전탐색 - 부분집합 부분집합이란 ? 부분집합이란 집합에 포함된 원소들을 부분적으로 선택하는 것을 뜻한다. 예) { 1, 2 } 집합은 { 1, 2, 3, 4 } 집합의 부분집합이다. 부분집합 특징 ? 부분집합 구현 순서 ? 부분집합 시간복잡도 부분집합의 시간복잡도 : O(2^n) 부분집합 그림으로 살펴보기 소스코드 // 부분 집합 - 기본 import java.util.Scanner; public class PowerSet { // 전체 원소 개수 public static int totalCnt; // 원소 요소 저장 배열 public static int input[]; // 원소 포함 여부 배열 public static boolean isSelected[]; // 숫자 포함 여부 결정 메서드 (부분 집합 구하기 메서드) .. 2023. 8. 8. [Algorithm] 완전탐색 - 조합 조합이란 ? 조합이란 서로 다른 n개의 원소 중 r개를 순서 없이 일렬로 나열하는 경우의 수이다. 예) 주사위를 2번 던졌을 때 서로 다른 숫자가 순서 상관없이 조합할 수 있는 경우의 수 조합 특징 ? 조합은 선택에 중복 없이 순서 상관없이 결과를 가져온다. 매 자리마다 이전 원소의 다음 원소부터 확인한다. 대표적인 구현 방법은 재귀 구현이다. 재귀의 깊이는 선택된 원소의 개수와 일치한다. 조합 구현 순서 ? 재귀 호출 시 현재 깊이 정도 (원소 선택 현황)과 탐색을 시작할 인덱스 값을 잘 확인하며 아래를 수행하자. 재귀를 호출하며, 깊이 정도와 탐색을 시작할 인덱스 값을 넘겨준다. 깊이 정도로 원소를 다 선택했는지 확인한다. 원소를 다 선택했다면 원하는 동작 후 메서드를 종료한다. 덜 선택한 경우 전달.. 2023. 8. 8. 이전 1 2 다음
