범범스의 코딩놀이터

다익스트라 알고리즘은 그래프에서 출발점에서 목표점까지의 최단거리를 구할 때 사용하는 알고리즘 입니다. 다익스트라를 사용할 때 사용하는 변수는 두개가 있습니다. int distance[] = new int[n+1]; //최단 거리를 저장할 변수 boolean[] check = new boolean[n+1];//해당 노드를 방문했는지 체크할 변수 distance 변수에는 각각의 노드까지의 최단거리가 저장됩니다.check 변수에는 각각의 노드를 방문했는지를 표시할 예정입니다. 다익스트라 알고리즘의 순서는 이렇습니다. 1. distance는 처음에 나올 수 있는 가장 큰 값으로 초기화 해줍니다. 여기서는 Integer.MAX_VALUE 값으로 초기화 하겠습니다.(문제에서 100000만 이상의 값은 안나온다 하면..

백트래킹 알고리즘이란 모든 경우의 수를 검색하는 알고리즘 입니다."특정조건"을 만족하는 모든 경우의 수를 찾고 싶을 때 사용하면 유용해요. 백트래킹을 활용해서 풀 수 있는 대표적인 알고리즘 문제로 N Queens 문제가 있습니다. N-Queens Problem문제를 간단하게 설명하자면 N*N 체스판에 N개의 Queen들이 "서로 공격 받지 않게" 놓는 위치를 구하는 것 입니다! 공격받지 않는 위치에 놓는 다는게 무슨 말일까요?퀸 하나를 놓았을 때입니다.퀸은 자신의 상하좌우를 공격할 수 있고, 대각선 방향도 공격할 수 있습니다. 만약에 퀸을 하나 더 놓아서 서로 공격 받지 않게 놓으려면 어떻게 해야 할까요? 그림처럼 체크한 곳중 한 곳에 퀸을 놓으면 서로 공격받지 않게 되겠죠? 이제 문제의 의도는 알았으니..

: n개 중에서 r개를 선택하는 방법의 수. 가령 집합 { A, B, C, D } 에서 2명을 순서와 상관없이 선택하는 방법은 어떤 경우가 있을까요? {A, B}{A, C}{A, D}{B, C}{B, D}{C, D} 위와 같이 총 6가지가 있습니다. 지금부터 이런 부분집합을 구하는 방법에 대해서 알아보겠습니다.아래와 같은 점화식을 이용해 재귀함수로 구현해 볼 것입니다. 일단 점화식에 대해서 알아보자면 n 개중 r 개를 뽑는 방법은 i) 어떤 특정한 원소를 포함하고 뽑았을 때 ii) 어떤 특정한 원소를 포함하지 않고 뽑았을 때 두가지로 나뉘어 집니다. i) 어떤 특정한 원소를 포함하고 뽑았을 때는이제 그특정한 놈 1개는 이미 뽑혔고 제외한 나머지 n-1 개에서 r-1개만 뽑으면 되니깐 경우의 수는 이고 i..

안녕하세요. 오늘은 DFS(깊이우선 탐색)을 이용하여 "출발점에서 "목적지"까지 도달하는 모든 경로를 구하는 법에 대해 알아보겠습니다. 위의 사진처럼 있을때 1 노드에서 4 노드로 가는 모든 경우의 수는 어떻게 구할까요? 일단 깊이우선 탐색(DFS) 을 구현해보겠습니다. class DFSAlgorithm{ private int maps[][] = new int [6][6];//DFS 인접행렬 private boolean visit[] = new boolean[6];//방문했나 안했나 판단할 변수 public DFSAlgorithm(){ //클래스 생성자 //스택을 초기화하고 //table 및 visit 변수를 할당 한다. for(int i=0;i