백수연

N-Queens Problem 이란? - N개의 Queen이 서로 상대방을 공격하지 않도록 NxN 체스판에 위치시키는 문제 (Queen은 왼쪽,오른쪽,위,아래,대각선의 모든 방향으로 원하는 만큼 이동할 수 있다.) - 서로 공격하지 않기 위해서는 : 같은 행 or 열 or 대각선 상에 위치하지 않아야 한다. - 백트래킹(Back Tracking) 대표 문제 예) N=4일 때, 4-Queens 문제 해결 과정 (1,1)~(4,4) 의 모든 위치를 탐색하며 퀸의 위치를 결정하는 DFS를 이용하면, 각 행마다 4가지의 경우를 각각 확인해야 하므로 4x4x4x4=256 가지의 경우를 탐색해야 한다. 모든 경우를 탐색해 결과를 찾아야 하기때문에 비효율적이므로, 각 행마다 퀸의 위치로 불가능한 위치는 탐색하지 않고..

그래프 표현 - ① 인접행렬 - 정점 두 개의 관계가 v1->v2, v1-v2 와 같이 연결되어 있는 경우(인접해있는 경우) 간선의 가중치를 배열로 표현한다. - 장점 : 구현이 용이하고, v1->v2 의 가중치와 연결 여부를 한 번에 탐색할 수 있다. (v1->v2의 가중치==arr[v1][v2]이므로) - 단점 : 임의의 정점에 연결된 정점을 알기 위해서 정점의 개수만큼 탐색해야 하고, 인접관계를 저장하기 위한 배열의 크기가 nXn 만큼 필요하다. -> 간선 개수가 적을 경우 비효율 코드 구현 - ① 인접행렬 /* 입력 예시: 5 6 (정점 개수, 간선 개수) 0 1 (정점0 - 정점1 인접) 0 2 0 4 1 3 2 3 2 4 */ public static void main(String[] args..

외판원 순회 문제 (Traveling Salesperson Problem) 이란? - 임의의 정점에서 출발해 모든 정점을 모두 거쳐 다시 원래의 정점으로 돌아오는 순회 경로 중 최소 비용을 구하는 문제 - 한 번 거쳐간 길은 재방문이 불가하다. - 비트마스크 이용하는 대표 문제 코드 구현 (백준 2098번) import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int MAX = 16*1000000; // ① static int n; static int[][] map; static int[][..

Floyd's Algorithm 이란? - 그래프의 각 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘 (모든 정점에 대하여 각 정점의 최단거리를 모두 구한다.) - i -> j 로 가는 최단거리를 구하기 위해 ① i->j ② i -> k -> j 의 두 가지 경우의 최소값을 최단거리로 정한다. 즉, 거쳐가는 정점을 기준으로 최단거리를 구한다. - 시간복잡도 : O(n^3) - DP 이용 Floyd's Algorithm 이용 - 1) 최단거리 배열 D 구하기 public static void main(String arg[]){ int n = 4; int[][] W = {{0,10,15,20},{5,0,9,10},{6,13,0,12},{8,8,9,0}; // 가중치 배열 int[][] D = ne..

예) 21, 72 의 최대공약수 & 최소공배수 구하기 ① 최대공약수 72 % 21 = 9 21 % 9 = 3 9 % 3 = 0 ∴ 최대공약수 = 3 ② 최소공배수 (21 * 72) / 최대공약수 = (21*72)/3 = 504 ∴ 최소공배수 = 504 코드구현 public static void main(String[] args){ int x = 21; int y = 72; int gcd = makegcd(x,y); System.out.println("최대공약수 : " + gcd); int lcd = (x*y) / gcd; System.out.println("최소공배수 : " + lcd); } private int makegcd(int x, int y){ while(x>0){ int temp = y%x; ..

① 조합 : 순서X, 중복X ('중복'은 자기자신 포함 여부를 의미) 예) 1,2,3,4 중 2개 뽑는 경우 (1,2) (1,3) (1,4) (2,3) (2,4) (3,4) /* N : 총 숫자 개수(num.length) R : 숫자 중에서 뽑는 개수 (nCr에서 r을 의미) int[] num : 숫자 집합 int[] ans : 조합(nCr) 결과를 담는 베열 int num_index : num[]의 인덱스 int ans_index : ans[]의 인덱스 int cnt : 숫자가 포함될 경우 카운트하는 변수 1. 숫자를 포함하는 경우 기존의 num[]배열의 인덱스 증가 / 결과 ans[]배열의 인덱스 증가 / 카운트 증가 2. 숫자를 포함하지 않는 경우 기존의 num[]배열의 인덱스 증가 / 결과 ans..

① 순열 : 순서O, 중복X ('중복'은 자기자신 포함 여부를 의미) 예) 1,2,3,4 중 2개 뽑는 경우 (1,2) (1,3) (1,4) (2,1) (2,3) (2,4) (3,1) (3,2) (3,4) (4,1) (4,2) (4,3) /* N : 총 숫자 개수(num.length) R : 숫자 중에서 뽑는 개수 (nPr에서 r을 의미) int[] num : 숫자 집합 boolean[] checked : num[]의 숫자 사용 여부 List ans : 순열(nPr) 결과를 담는 리스트 1. 숫자 사용X 1) 사용표시(checked[i]=true), 결과리스트에 추가, 재귀 2) 사용표시 원상복귀(checked[i]=false), 결과리스트에서 삭제, i++ 2. ans.size()==M 이면 출력 후 ..

부분집합을 구하는 방법 중 재귀함수와 비트연산자를 이용하는 방법은 다음과 같다. ① 재귀함수 이용 예: 집합 {a, b, c, d}에서 {a,b}는 a,b는 포함되어 있고 c,d는 포함되어 있지 않다. 포함안될 때와 될 때 두 가지 경우를 checked[]배열에 표시하고, 재귀함수로 돌린다. 즉, 각 원소에 대하여, (포함X, 포함X, 포함X, 포함X) ~ (포함O, 포함O, 포함O, 포함O) 까지를 모두 탐색한다. public static void main(String[] args) { String[] arr = {"a", "b", "c", "d"}; boolean[] checked = new boolean[arr.length]; //포함여부 체크 makeset1(arr, checked, 0); // ..

Counting Sort - 원소 간 비교 과정을 거치지 않고 정렬하는 방법 - 시간복잡도 = O(n) - O(nlogn)의 Quick Sort(퀵 정렬)보다 빠르지만, 사용할 수 있는 경우가 제한적이다. : 배열을 이용해 정렬을 수행하기 때문에 - 불필요한 메모리를 많이 잡아먹는다. - 배열 인덱스를 기반으로 정렬을 수행하기 때문에, 음수/소수 일 경우에는 특정 값을 더하거나 곱해서 사용한다. 예시 - {5, 2, 3, 1, 4, 2, 3, 5, 1, 7} 을 카운팅 정렬 해보자. 1. input[] 배열의 최댓값 만큼의 countint[] 배열을 생성한다. 2. input[] 배열을 하나씩 읽어가며, 숫자가 나온 횟수를 카운팅하여 counting[] 배열에 저장한다. 3. counting[i] += ..

소수를 구하는 방법에는 세 가지가 있다. ① (2부터 자기자신-1) 까지의 모든 수로 나누어보기 소수의 정의 = 1과 자기자신으로 나누어떨어지는 수 를 이용하는 방법! 모든 수로 나누어 보는 과정을 거쳐야하기 때문에, 시간초과 위험 + 비효율적이다. public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); //2부터 num-1 까지의 모든 수를 체크 for(int i=2; i