탕구리's 블로그

오늘의 주제 오늘의 주제는 BOJ 4963번 섬의개수 입니다. 문제는 아래와 같습니다. 이 문제를 보고 첫번째로 "연결된 섬을 찾기 위한 탐색하기", 두번째로 "탐색을 지속적으로 이루어가면서 섬이 아닌 위치, 이미 방문을 했던 위치는 건너뛰고 탐색"을 진행하면 될 것 이라 생각했습니다. 제가 작성한 코드는 다음과 같습니다. public class boj_4963 { static int[][] result; static int[][] arr; static int row; static int col; static int cnt; // 상하좌우, 대각선 4방향 static int[] dx = {0,0,1,-1,-1,-1,1,1}; static int[] dy = {1,-1,0,0,-1,1,-1,1}; publ..

오늘의 주제오늘의 주제는 백준 알고리즘 11403번 경로찾기 입니다. 경로찾기는 방향 그래프 탐색에 관한 문제입니다.저는 깊이 우선 탐색(DFS)를 통해서 문제를 해결했지만, 너비 우선 탐색 및 워셜 알고리즘을 통해서도 해결이 가능합니다. 우선 문제를 살펴보도록 하죠 가중치 없는 방향 그래프가 방문할 수 있는 모든 정점을 찾아 행렬로 표시하는 문제입니다.테스트 데이터는 다음과 같습니다. 예제 입력1의 인접행렬의 경우 문제를 해결하기 위해 각 정점(편하게 A,B,C)을 시작점으로 잡을 수 있습니다. 정점 A를 시작점으로 잡을 경우는 A->B->C->A정점 B를 시작점으로 잡을 경우는 B->C->A->B정점 C를 시작점으로 잡을 경우는 C->A->B->A 위와 같이 총 3가지의 순환 구조를 갖습니다. 각각의..

시작하기 전에 해당 블로그에 작성되는 글은 주인장의 지극히 주관적인 생각이 다수이며, 대부분의 지식은 구글링을 통해 얻고 있기 때문에 옳지않은 정보가 있습니다. 잘못된 부분이나 수정해야 하는 부분이 있다면 과감히 덧글을 남겨주세요! 모르는게 많은 새싹입니다 오늘의 주제그래프 중에서도 방향성을 갖는 방향 그래프(Directed Graph)에 대해서 정리를 해놓으려 합니다 :0 요즘 간간히 알고리즘도 다시 풀고 있기 때문에(취준 신세로 돌아왔기 떄문에) 조금이라도 정확히 몰랐던 부분에 대해서는 정리를 하겠습니다. 방향 그래프방향 그래프는 지금까지 바왔던 그래프와 다르게 정점과 간선사이에 방향성을 띄고 있는 그래프를 말합니다. 정점 A,B에 대해 방향성을 띄고 있고 A->B 의 방향을 갖는 경우 로 표시합니다..

그냥, 규칙을 찾으면 되는 문제! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * Created by idongsu on 2017. 7. 30.. */ public class num_9461 { static public void main(String args[]) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(in.readLine()); long dp[] = new long[101]; dp[1] = 1; dp[2..

동적계획법(Dynamic Programming) 말 그대로 파일을 합치기 위해 가장 최소가되는 비용을 찾는 문제이다 예시 처럼 40,30,30,50 일경우 방법 1. 40,{30,30,50} 방법 2. 40,{{30,30},50} 방법 3. 40.{30,{30,50}} 방법 4. {40,30},{30,50} 방법 5. {40,30,30},{50} 방법 6. {{40,30},30},{50} 방법 7. {40,{30,30}},{50} 이런 식으로 문제를 해결하되 이중 최소의 값을 출력 값으로 선택한다. (소스와 위의 방법의 예제와는 순서가 다를 수 있습니당) 사실, 인터넷을 통해 참고 했지만 소스를 이해하는데도 내것으로 만드는데도 많은 시간과 어려움이 있었다. 아직 너무 실력이 없기 때문에 다른 분들도 슬퍼..

동적계획법(Dynamic Programming) Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] d = new int[1001]; d[0] = 1; d[1] = 1; for (int i=2; i

동적계획법(Dynamic Programming) 타일을 구성할 수 있는 방법에 대해 재귀를 이용하여 Dp배열을 완성 항상 기준은 1,2, ... N 일때 i 번째를 기준으로 앞 쪽에 저장된 Dp값을 이용하면 된다. static public void main(String args[]) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(in.readLine()); long[] dp = new long[N+1]; System.out.println(solve(N,dp)%10007); } static long solve( int N, long[] dp..

동적계획법(Dynamic Programming) LIS라는 기법(?) 방식을 통해 Dp를 이용하여 해결! BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int N = Integer.parseInt(in.readLine()); int[] arr = new int[N+1]; int[] dp = new int[N+1]; int max =0; st = new StringTokenizer(in.readLine()); int last=0; for(int i=1; i dp[i]) { dp[i] = dp[j] + 1; } } max = Math.max(max,dp[i]); } System.out.p..

동적계획법(Dynamic Programming) DP를 이용하여 모든 경로를 탐색하되 지난적 있는 경로에 대해서는 Dp배열의 값을 이용하는 방법으로 해결 재귀를 이용하여 문제를 해결하였다. BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; String[]k = in.readLine().split(" "); int row = Integer.parseInt(k[0]); int col = Integer.parseInt(k[1]); int[][] arr = new int[row+1][col+1]; int[][] dp = new int[row+1][col+1]; int result = 0; for..