Algorithm/기타6 DFS / BFS 1. DFS - 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘입니다. - 재귀 함수를 이용하므로 스택 오버플로에 유의 - ex. 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 - 작동 원리 - 예제 코드 public class BJ_11724 { static ArrayList[] A; static boolean visited[]; static void DFS(int v) { if (visited[v]) { return; } visited[v] = true; for (int i : A[v]) { if (!visited[i]) { DFS(i); } } } public static vo.. 2024. 1. 22. 스택과 큐 1. 스택 - 삽입과 삭제 연산이 후입선출로 이뤄지는 자료구조 2. 큐 - 삽입과 삭제 연산이 선입선출로 이뤄지는 자료구조 3. 스택과 큐 코드 구현 public class Example { public static void main(String[] args) { Stack st = new Stack(); Queue q = new LinkedList();//Queue의 인터페이스 구현체인 LinkedList를 사용 st.push("0"); st.push("1"); st.push("2"); q.offer("0"); q.offer("1"); q.offer("2"); System.out.println("=== Stack ==="); while(!st.isEmpty()) { System.out.println(s.. 2024. 1. 17. 투 포인터 1. 투포인터 - 2개의 포인터를 가진 알고리즘 - 시간복잡도 O(N) 2. 알고리즘 1) 시작, 끝 포인터 초기화 2) 투 포인터 이동 3. 슬라이딩 윈도우 - 투 포인터를 유지한 채 고정된 범위를 이동시키는 알고리즘(배열 크기 변화) - 시간 복잡도 O(N) 2024. 1. 16. 구간 합 1. 구간 합 - 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 - 합 배열 : 기존의 배열을 전처리한 배열 - 합 배열을 사용하면 시간 복잡도를 O(N)에서 O(1)로 줄일 수 있다. - 합 배열 S를 만드는 공식 S[i] = S[i-1] + A[i] - A[2] ~ A[5] 구간 합을 배열로 구하는 과정 S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]; S[1] = A[0] + A[1]; S[5] - S[1] = A[2] + A[3] + A[4] + A[5]; 2024. 1. 15. 이전 1 2 다음
