요르딩딩

이번문제는 사이클 개수를 구하는 문제이다. 이는 DFS를 이용하여 자기자신이 나오면 사이클인것으로 간주하기로 했다. 여기서 주의할 점은 방문하지 않은 노드들을 기준으로 DFS를 거쳐 사이클 유무를 판단해야한다는거다. 방문한 노드들은 이미 전 사이클에 포함되는 노드이므로, 방문하지 않은 노드들에 대해서만 DFS(사이클 판별)를 거치도록한다. 1,3,5,7은 하나의 사이클이므로 첫 DFS에서 모두 방문 처리돼있다. 방문하지않은 2를 기준으로 DFS(사이클 판별) 한다. 방문하지 않은 4 ... (반복) import java.util.*; /* * 자기자신이 나오면 사이클 완성 */ class Main { static int n, nodeCnt, start2, resultCnt; static boolean[]..

이번문제는 가장 기본적인 DFS와 BFS문제인거 같다. 여기서 주의해야 할점은 1. 방문할 수 있는 노드가 여러개이면, 작은 노드부터 방문한다 -> 정렬필요 2. 노드를 순서대로 출력 -> 방문표시시 출력한다. 3. DFS는 방문처리 1번, BFS는 방문처리 2번 import java.util.*; class Main { static int n, m, s; static boolean[] visited; static ArrayList graph; static ArrayList dfsList; static ArrayList bfsList; public static void dfs(int now) { visited[now] = true; // 방문표시 dfsList.add(now); // 출력(방문시만 출력*..

이번문제는 간단한 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는 스택함수를 기초로 ..

MVC model2 방식의 변화 : Dispatcher를 집중화하기 전의 모델 -> Dispatcher를 집중의 모델 Dispatcher덕에 controller를 편하게 사용가능하다. Dispatcher와 controller의 결합력을 낮춰준다. -> (실행환경이 바뀌어도 사용이 가능하다.) Spring에서 Dispacher 만드는것을 제공해준다. Spring.io : Spring framwork 제공 (eclipse.spring tool 제공) 압출풀기 (jar -> zip으로 수정) contentes.zip -> sts-4.8.0 release tomcat 다운 : 스프링 부트는 내장톰캣을 사용 스프링부트 : spring에 부트를 얹어서 사용하는 개념 install버전은 서비스개발할때 사용하는 용도 ..

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