Jun's Development Journey

1. Flowd-Warshall - 변의 가중치가 음이거나 양인 가중 그래프에서 최단 경로를 찾는 알고리즘 - 경유지를 거쳐 갈 수 있는 경우를 체크하여 기록하고 활용하는 기법 2. 예시 문제 문제) www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이) import java.io.*; import java.util.*; public class Main { static int N; static int[][] map; public static void floyd_warshall() { for(int k..

1. DFS(Depth First Search) - 깊이 우선 탐색 - 그래프 전체를 탐색하는 방법 중 하나 - 시작점부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법 - 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방법 - 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 함 - 완전 탐색, 길찾기, 그래프 순회 등등에 사용 2. 예시 문제 문제) www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 ..

1. 이진 탐색(Binary Search) - 정렬 등과 함께 가장 기초인 알고리즘이다. - 검색 범위를 줄여 나가면서 원하는 데이터를 감색하는 알고리즘 - 순차 탐색에 비해 굉장히 빠르지만, 데이터가 미리 정렬이 되어 있어야 한다. 2. 예시 문제 문제) www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이) import java.io.BufferedReader; import java.io.IOException; import ..

1. 의미 정렬된 리스트를 두 개의 포인터를 이용해 순차적으로 접근하면서 두 포인터 구간의 값이 타겟 값과 같을 때 까지 포인터를 조작하는 기법을 말한다. 2. 활용 - 배열의 특정 연속된 구간을 처리하는 경우 1) 문제에서 연속된 데이터 구간을 처리하기 원한다면? 2) 다양한 접근 방법을 떠올려 보는 것이 중요 3) 자주 사용되는 기법들로는 어떤 것이 있을까? 3. 예시 1) 부분 수열의 합 수열 : 1, 2, 3, 2, 5 합이 5인 부분 연속 수열의 개수는? int[] arr = {1,2,3,2,5}; int len = arr.length; int end = 0, sum=0,d_sum = 5; int cnt=0; for(int st = 0;st