코딩테스트13 [그래프] 유니온 파인드 & 위상 정렬 그래프의 표현 그래프를 구현하는 방법에는 3가지가 있다. 1. 에지 리스트로 가중치 있는 그래프 표현하기 : 에지 중심 표현 방법, S - E - V 2. 인접 행렬로 가중치 없는 그래프 표현하기 : 바둑판처럼 2차원 배열을 자류구조로 이용해 그래프로 표현한다. (가중치가 있다면 가중치를 2차원 배열에 넣어주면 됨), 에지를 탐색하려면 N번 접근해야 하므로 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어짐 3. 인접 리스트로 가중치 없는 그래프 표현하기 : ArrayList[]로 선언. 가중치가 있는 경우에는 Node라는 클래스를 만들어 ArrayList[]를 선언한다. 유니온 파인드는 일반적으로 여러 노드가 있을 때, 특정 2개의 노드를 연결해 3개의 집합으로 묶는 union연산과 두 노드가 같.. 2024. 3. 5. [정수론] 백준 1929 에라토스테네스의 체 원리 1. 주어진 범위까지 배열을 생성하고 2부터 탐색 시작. 2. 선택한 수의 모든 배수를 삭제한다. 3. 다음 지워지지 않는 수를 선택하여 배수를 모두 삭제한다. 3. 앞의 과정을 반복한다. 시간 복잡도는 일반적으로 O(nlogn)이다. 뒤로 갈 수록 삭제된 데이터가 많아 탐색할 수가 적어지기 때문이다. 백준 1929에서 에라토스테네스의 체 적용해보기 public class 소수_구하기 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); int[] a = new int[n+1]; for (int i = 1; i 2024. 3. 1. [그리디 알고리즘] 백준 11047, 백준 1541 그리디 알고리즘이란 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 수행 과정 1. 해 선택 : 최선의 선택지를 해로 선택한다. 2. 적절성 검사 : 전체 문제의 제약 조건에 벗어나지 않는지 검사한다. 3. 1~2 반복 백준 11047에서 그리디를 적용하기 위해 살펴보면, 최대한 큰 금액의 동전으로 구성하는 것이 최선의 선택지임을 알 수 있다. public class 동전개수의_최솟값_구하기 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int a[] = new int[n]; .. 2024. 2. 29. [너비 우선 탐색 BFS] 백준 2178 [너비 우선 탐색 BFS] 도 그래프를 완전 탐색하는 방법 중 하나로 시작 노드에서 출발해 시작노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘(FIFO) 입니다. 선입선출 방식으로 탐색하므로 큐를 이용해 구현합니다. 너비 우선 탐색의 핵심 이론 1.BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화 하기 (DFS와 동일하지만 스택대신 큐를 사용한다는 점에서 다름) 2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기 3. 큐 자료구조에 값이 없을 때 까지 반복 백준 2178 미로 찾기 문제에 적용해보기 public class 미로탐색 { static int[] dx = {0,1,0,-1}; static int[] dy = {1,0,-1,0}; //각각 위, 오른쪽,.. 2024. 2. 28. [이진 탐색] 백준 1920 이진 탐색은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘으로 시간 복잡도는 nlogn이다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터 크기를 절반씩 줄이면서 대상을 찾는다. 탐색 방법 1. 데이터에서 중앙값(median)을 선택한다. 2. 중앙값>타깃 데이터 라면, 중앙값을 기준으로 왼쪽 데이터셋을 선택한다. 3. 반대인 경우라면 오른쪽 데이터셋을 선택한다. 4. 1~3을 반복하면서 중앙값 == 타깃 데이터를 찾는다. 더보기 내가 찾고자 하는 데이터 = 55 3 7 13 15 23 35 38 41 46 49 55 57 68 72 77 68 -> 오름차순으로 배열 되어있는 상태, 중앙값을 41로 설정 41과 55 비교 -> 55가 더 크므로 오른쪽 데이터 셋 선택 46 49 5.. 2024. 2. 28. [깊이 우선 탐색 DFS] 백준 11724 [깊이 우선 탐색 DFS]은 그래프 완전 탐색 기법 중 하나로 그래프의 시작 노드에서 출발해 탐색할 한 쪽 분기를 정해 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동해 다시 탐색하는 알고리즘이다. 깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로를 유의해야 한다! 깊이 우선 탐색은 단절점 찾기, 사이클 찾기, 위상 정렬 등에 응용하여 문제를 풀 수 있다. 깊이 우선 탐색의 핵심 이론 DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프는 인접 리스트로 표현하겠다. 그리고 DFS의 탐색 방식은 후입선출 특성을 가지므로 스택을 사용하여 설명하겠다. 1.DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기 원본 그래프를 인접리스.. 2024. 2. 27. 이전 1 2 3 다음
