백수연

① 메소드로 구현하기 십진수 9를 이진수로 바꾸는 과정은 아래의 그림과 같다. 바꾸고자하는 십진수 값을 2로 나누어, 몫이 1이 될때까지 모든 나머지값을 거꾸로 출력한다. 이 과정을 그대로 코드로 구현하면 다음과 같다. /* n : 비트 자리 수 (예: 9=1001(2)일때, 비트 자리 수 n=5 : 01001(2)) num : 십진수 */ public static int[] makeBinary(int n, int num){ int[] result = new int[n]; int i = n-1; while(num != 1){ result[i--] = num%2; num /= 2; } result[i] = num; //가장 마지막 num/2값 return result; } ② Integer.toBinary..

String -> Char[] String str = "Back-suyeon"; char[] charArr = str.toCharArray(); for(int i=0; i String char[] charArr = {'B','a','c','k','-','s','u','y','e','o','n'}; String str1 = new String(charArr); System.out.println(str1); //방법① 출력결과: Back-suyeon String str2 = String.valueOf(charArr); System.out.println(str2); //방법② 출력결과: Back-suyeon StringBuilder sb = new StringBuilder(); for(int i=0; i

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

Comparable 이란? - java.lang.Comparable 패키지에 속해 있으며, Comparable 인터페이스를 이용해 객체를 정렬할 수 있다. 구현 방법 1. 객체에 Comparable 인터페이스를 implements 한다. 2. compareTo() 메서드를 오버라이드 한다. 현재 객체 = this.x, 파라미터로 들어온 객체 = XY.x 라고 가정하면 - this.x > XY.x : 양수 리턴 -> 오름차순 정렬 (현재 위치(자리) 유지) - this.x == XY.x : 0 리턴 -> 오름차순 정렬 (현재 위치(자리) 유지) - this.x 내림차순 정렬 (두 객체 위치(자리) 변경) 코드 구현 class XY implements Comparable { ..

그래프 표현 - ① 인접행렬 - 정점 두 개의 관계가 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; ..

두 날짜 차이 구하기 public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); try{ String date1 = br.readLine(); String date2 = br.readLine(); SimpleDateFormat format = new SimpleDateFormat("yyyy/MM/dd"); Date first = format.parse(date1); Date second = format.parse(date2); long calDate = Math.abs(second.getTime() - first.getTime())..

① 조합 : 순서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..