요르딩딩

이번문제는 간단한 DFS로 풀수 있는 문제였습니다. 다만, 시간초과 이슈로 계속 틀려 찾아보고 여러가지 수정하여 정답이 맞았으나.. 맞은 정답의 원인을 찾고자 다시 맞은답을 실행해 보니... 틀렸다는... 무슨일인가... 원인을 어떻게 찾으란 밀인가.. 일단 내가 생각한 시간문제를 해결하는 방법을 적어보겠습니다. 1. Scanner 대신 BufferedReader, StringTokenizer 사용하기 2. public class Main 대신 class Main 사용하기 3. 불필요한 import문 제거 정도인것 같다. 이문제의 핵심 역시 dfs를 각 노드별로 반복해서 수행한다는 점이다. 그리고 감염되는 컴퓨터수를 조건에 맞게 증가하면 끝!!! 보다 명확한 시간초과문제 해결방법이 나오게되면 참고해봐야겠..

이번문제도 DFS를 사용하면 되는 문제입니다. 문제를 풀면서 주의해야 할점에 대해 적어보도록 하겠습니다. 입력하는 그래프가 양방향인지, 단방향 그래프인지 꼭!!! 확인해야한다. -> 양방향인줄 알고 조금 시간이...지체... 젠자..ㅇ 각, 시작점(i)/목표점(j)을 기준으로 두고 DFS를 반복적으로 한다. 단, 반복적으로 진행할때 방문배열은 초기화해야합니다. 목표에 도달하면, 플레그를 변경하여 도달확인 노드는 1번부터 시작하므로, 노드번호 주의 (모드 노드를 -1해서 생각하면 쉽다.) package com.controller; import java.util.*; public class Main { static int n; static boolean[] visited ; static ArrayList g..

가장 기본적인 DFS 문제인것 같습니다. 카운트, 무방향 간선, 인덱스 확인 이렇게 3가지 정도면 잘 확인하면 풀 수 있는 문제입니다. import java.util.*; public class Main { static int n,m; static boolean[] visited; //노드 수 만큼생성 static ArrayList graph = new ArrayList(); static int result = 0; public static void dfs(int now) { // DFS(재귀) visited[now] = true; //방문표시 for(int i =0; i< graph.get(now).size(); i++) { int tmp = graph.get(now).get(i); if(visited..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 나는 처음에 재귀를 통해서 문제를 풀었다. 재귀로 풀게된 이유는 해당 입력값을 각각 1, 2, 3으로 한번씩 빼고, 거기서 나온 값을 또 1, 2, 3을 뺴는 식으로 반복한 뒤, 마지막으로 0이 나온것들의 카운트를 세면 된다고 생각했기 때문이다. 4 - 1 =3 여기서 또 1 ,2, 3 각각 빼기 반복 4 - 2 =2 여기서 또 1 ,2, 3 각각 빼기 반복 4 - 3 =1 여기서 또 1 ,2, 3 각각 빼기 반복 그러면 DFS 모양과 비슷한 모습을 찾을 수 있었다. DFS는 스택함수를 기초로 ..

다이나믹프로그래밍 메모리공간을 약간 더 사용하면서 연산속도를 비약적으로 증가 시킬 수 있는 방법 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 조건 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 메모제이션 (캐싱) 다이나믹프로그래밍을 구현하는 방법 중 한 종류로, 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 단순히, 한 번 구한 정보를 리스트에 저장하는 것이다. 다이나믹프로그래밍과 분할 정복의 차이점 다이나믹프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다. 분할 정복은 한번 변경된 정보는 더 이상 변경되지 않는다. 탑..

다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. '음의 간선'이 없을때 정상적으로 동작한다. 그리디 알고리즘으로 분리된다. (매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다.) '방문하지 않은 노드중에서 가장 최단 거리가 짧은 노드를 선택'하는 과정을 반복한다. 다익스트라 알고리즘이 진행되면서 '한 단계당 하나의 노드에 대한 최단거리를 확실히 찾는 것으로 이해 마지막 노드는 확인할 필요 없음 간단한 다익스트라 알고리즘의 시간복잡도 : O(V^2), V는 노드의 개수 개선된 다익스트라 알고리즘의 시간복잡도 : O(ElogV), E는 간선의 개수, V는 노드의 개수 우선순위 큐 사용 -> 우선순위가 높은 데이터를 ..

DFS (Depth-First Search) : 깊이 우선 탐색 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 동작원리 : 스택 자료구조에 기초한다. 구현방법 : 재귀함수 이용 시간복잡도 :O(N) import java.util.*; public class Main { public static boolean[] visited_Node = new boolean[7]; // 방문했던 노드를 체크하기 위한 변수 public static ArrayList graph = new ArrayList(); // 그래프 변수 // 같은 Depth가 있을 경우, 작은 숫자를 먼저 방문(add를 작은 숫자 먼저 했기 때문) public static void dfs(int num) { visited_Node[num..

1. 선택정렬 매번 가장 작은 것을 선택한다. 시간복잡도 : O(N^2) 동작 7 5 9 0 3 ... 7(선택) 5 9 0 3 ... > 나머지 중에서 가장 작은것 선택해서 (7)과 교환 특징 스와프 이용 import java.util.*; public class Main { public static void main(String[] args) { int n = 10; int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; for (int i = 0; i arr[j]) { min_index = j;..