맛있는 데이터

간편 조합

{A,B,C,D} 4개의 원소중 3개를 뽑을 조합은 어떻게 될까?

조합은 뽑은 원소가 중복되면 안되기 때문에 앞에서부터 차례대로 원소를 뽑아본다.

단순하게 for 를 3번 돌면 된다.

// 4개중 3개를 뽑을경우

int n = 4;

for(int i=0;i<n;i++)

for(int j=i+1;j<n;j++)

for(int k=j+1;k<n;k++){

System.out.print(array[i]+" "+array[j]+" "+array[k]);

System.out.println();

}

결과

A B C

A B D

A C D

B C D

2개를 뽑을땐 for를 2번 반복, 4개를 뽑을땐 for를 4번 반복한다. 몇 개를 뽑을지 모르는데 매번 이렇게 할 수 없다. 또한 for 문이 비슷하게 반복되지 않는가.

코드를 잘 보면 for 한번이 원소 하나를 고르는 행위를 하는 것임을 알 수 있다.

그렇다면 for문으로 원소 한개를 고르고 다시 자기 자신을 호출해 남은일을 넘기는 재귀를 구성해본다. 

위 for 문이 몇개를 뽑을지에 따라 반복된다. 즉 n개중 r개를 뽑는다면 for 는 r만큼 반복되어야 한다.

하나를 뽑으면 그다음에 뽑을 수 있는 개수는 한개 줄어든다. 그렇게 뽑다가 뽑을 수 있는 개수가 0이 되면 r개만큼 뽑은것이다. 더이상 뽑지 않고 출력한다.

이후에는 마지막에 뽑았던 것을 빼놓고 다음에 뽑을 수 있는 것을 뽑는다. 다음것도 뽑을 것이 없다면 다음것을 뽑을 수 있을때까지 마지막을 뺀다. 

조합의 작업을 다음 입력들의 집합으로 정의한다.

1. 원소들의 총 개수

2. 더 골라야 할 원소들의 개수

3. 지금까지 고른 원소들의 번호

위 3가지를 고려해 for 반복 for 문 작업을 하는 재귀함수로 구성한다.

import java.util.Stack;

public class Combination_1 {

static char array[] = {'A','B','C','D'};

public static void main(String[] args) {

Stack<Integer> st = new Stack<Integer>();

for(int i=1; i<=array.length; i++){

System.out.println(i+"개 뽑을경우 조합");

pick(array.length, st, i);

}

}

static void pick(int n,Stack<Integer> st,int r){

if(r==0)

printPick(st);

int smallest = st.isEmpty() ? 0 : st.lastElement() + 1; 

for(int next = smallest; next < n; next++){

st.push(next);

pick(n,st,r - 1);

st.pop();

}

}

static void printPick(Stack<Integer> st){

for(int i:st)

System.out.print(array[i]+" ");

System.out.println();

}

}

결과 

1개 뽑을경우 조합

A 

B 

C 

D 

2개 뽑을경우 조합

A B 

A C 

A D 

B C 

B D 

C D 

3개 뽑을경우 조합

A B C 

A B D 

A C D 

B C D 

4개 뽑을경우 조합

A B C D 

위상정렬 Topological sort

일의 순서가 정해져 있을때 순서대로 정렬하는 것. (예: 수강신청시 선수과목, 스타크래프트 빌드 테크트리)

순서를 정해야하기 때문에 그래프에서 cycle이 존재하면 안된다. 또한 순서가 있기 때문에 방향이 있어야 한다.

DAG(Directed Acyclic Graph) 가 되어야 위상정렬을 할 수 있다.

즉, 방향이 있으며 사이클이 없는 그래프여야 한다.

위상정렬 구현 방법 (BFS 탐색)

1. 이 그래프가 사이클이 있는지 확인한다.

(보통의 경우 문제를 해결하는 경우에는 이 과정이 있다면 위상 정렬 자체를 시도하지 않을 것이지만) 

2. 현재 정점에 들어오는 간선이 없다면 BFS라면 큐에 담아준다.

3. 큐에서 front원소를 빼고 front에 연결되어있는 정점들 간의 간선을 모두 삭제해준다. 

이때 해당하는 다음 정점에 들어오는 간선이 없다면 큐에 담아준다.

이 과정을 정점의 개수만큼 반복한다.

4. 결국 이 과정을 반복하는 동안 큐에서 빠지는 front 순서대로가 위상 정렬의 결과이다.

출처: http://www.crocus.co.kr/716 [Crocus]

- Java 구현 소스 -

import java.io.BufferedReader;

import java.io.FileInputStream;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.Collections;

import java.util.LinkedList;

import java.util.Queue;

import java.util.StringTokenizer;

public class TopologicalSort {

static int Ts, V, E, edgecount[];

static String answer;

static ArrayList<Integer> graph[];

public static void main(String args[]) throws Exception {

// System.setIn(new FileInputStream("sample_input.txt"));

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = new StringTokenizer(br.readLine());

Ts = Integer.parseInt(st.nextToken());

for(int T=1;T<=Ts;T++){

// init

answer = "";

st = new StringTokenizer(br.readLine());

V = Integer.parseInt(st.nextToken());

E = Integer.parseInt(st.nextToken());

graph = new ArrayList[V+1];

edgecount = new int[V+1];

for(int i=1;i<=V;i++)

graph[i] = new ArrayList<Integer>();

// input

for(int i=1;i<=E;i++){

int s,e;

st = new StringTokenizer(br.readLine());

s = Integer.parseInt(st.nextToken());

e = Integer.parseInt(st.nextToken());

graph[s].add(e);

edgecount[e]++;

}

// Sort 같은레벨일경우 오름차순으로 정렬한다.

for(int i=1;i<=V;i++)

Collections.sort(graph[i]);

// set start point

ArrayList<Integer> root = new ArrayList<Integer>();

for(int i=1;i<=V;i++){

if(edgecount[i]==0)

root.add(i);

}

// call topological sort

ArrayList<Integer> result = topologicalSort(root);

// make output

for(int vertax:result)

answer += vertax+" ";

// print screen

System.out.println("#"+T+" "+answer);

}

}

// 위상정렬

static ArrayList<Integer> topologicalSort(ArrayList<Integer> root){

ArrayList<Integer> result = new ArrayList<Integer>();

Queue<Integer> que = new LinkedList<Integer>();

boolean visited[] = new boolean[V+1];

// set root

for(int vertax:root)

que.add(vertax);

while(!que.isEmpty()){

int vertax = que.poll();

result.add(vertax);

if(!visited[vertax]){

visited[vertax] = true;

for(int next:graph[vertax]){

edgecount[next]--; // 간선 차감

if(edgecount[next]==0) // 간선이 0인것은 다음 root 이므로 queue add

que.add(next);

}

}

}

return result;

}

}

/* input example

1

5 6

2 1

2 3

3 4

3 1

1 4

5 4

Binary Search 이진탐색

// int 배열 

int list[] = {1,3,5,10,2,11, 13,14,15,18};

System.out.println();

// int 배열 정렬

Arrays.sort(list);

for(int a:list)

System.out.print(a+" ");

// 구현된 binary search

int findindex = binarySearch(list, 11);

System.out.println();

System.out.println("index"+findindex);

System.out.println("value"+list[findindex]);

// lo : low open , hi : high interval, arr 는 항상 오름차순 정렬되어 있다는 전제하에 수행

public static int binarySearch(int[] arr, int x){

int lo = -1; int hi = arr.length; int mid;

while(lo + 1 < hi){   // lo + 1 = hi 일때 종료됨 정의에 의해 항상 lo < hi 가 성립됨

mid = (lo + hi)/2;    // 중간값 index    

if (x==arr[mid]) return mid; // 찾았을경우 index 리턴

if (arr[mid] < x) 

   lo = mid;    // 중간값이 찾고자 하는 값보다 적을때 low 값을 mid 로 설정

else

hi = mid; // 중간값이 찾고자 하는 값보다 클때 high 값을 mid 로 설정

}

return -1; // 찾지 못하였을경우(없을경우) -1 리턴

}

재귀호출

재귀함수는 하위작업을 수행하도록 자기 자신을 호출하여 작업을 수행한다. 어느 단계에 이러러서는, 자기 자신을 호출하지 않고도 수행할 수 있는 기본 단위를 수행합니다. 함수가 자기 자신을 호출해서 하위 작업을 수행하는 것을 재귀 경우라고 합니다. 모든 재귀 함수는 아래의 형식으로 쓰여질 수 있다.

if (기본 경우인지 확인)

return 기본 값

else if (또 다른 기본경우인지 확인)

return 또 다른 기본 값

else

(어떤 작업)

return (재귀호출)

재귀호출 될때마다 메서드의 복사본(실제로는 변수만)이 메모리에 만들어지고 메서드가 종료될때 복사본이 메모리에서 삭제된다. 

재귀와 반복 비교

재귀

1. 기본 경우에 도달하면 종료한다.

2. 각 재귀 호출은 스택에 공간을 필요로 한다.

3. 무한루프에 들어가면 메모리 용량을 초과해서 스택 오버플로우가 발생한다.

4. 어떤 문제의 답은 재귀적인 수식으로 만들기 쉽다.

반복

1. 조건이 거짓일 때 종료한다.

2. 각 반복이 별도 공간을 필요로 하지 않는다.

3. 무한 루프는 추가 메모리가 필요하지 않아 무한히 반복한다.

4. 반복 해법은 재귀 해법에 비해 간단하지 않을 때가 있다.

재귀 참고사항

재귀적 알고리즘에는 2가지, 재귀적 경우와 기본경우가 있다.

모든 재귀함수는 기본경우에 종료해야한다.

일반적으로 반복해법이 재귀해법보다 효율적이다. 반복은 추가 메모리를 필요로하지 않는다.

재귀적으로 풀 수 있는 문제는 반복적으로 풀 수도 있다.

어떤 문제들의 경우엔 눈에 띄는 반복적 알고리즘이 없을 수도 있다.

어떤 문제는 재귀적 해법이 최적이고, 어떤 문제는 그렇지 않다.

재귀알고리즘 예

피보나치 수열, 팩토리얼 구하기, 병합 정렬, 퀵 정렬, 이진 검색, 트리탐색, 중위, 전위, 후위 등 트리문제, 그래프 탐색, 깊이우선탐색(DFS), 너비우선탐색(BFS)

백트래킹

분할 정복을 이용한 완전검색 기법이다.

백트래킹 알고리즘 예

이진문자열, k-ary문자열 만들기, 배낭채우기, 문자열 일반화, 해밀턴 사이클, 그래픽 색칠

문제 : n 비트의 모든 문자열을 생성하라.

import java.io.*;

public class Binary {

static int[] A;

static void binary(int n){

if(n<1){

for(int i:A)

System.out.print(i);

System.out.println();

}

else{

A[n-1] = 0;

binary(n-1);

A[n-1] = 1;

binary(n-1);

}

}

public static void main(String[] args) throws Exception{

int N;

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

N = Integer.parseInt(br.readLine());

A = new int[N];

binary(N);

}

}

입력 / 출력

3

000

100

010

110

001

101

011

111

문제 : 0..k-1 사이에서 고른 길이가 n인 모든 문자열을 생성하라

import java.io.*;

import java.util.*;

public class Recursive {

static int N,K;

static int[] A;

public static void rec(int n,int k){

if(n<1){

for(int i:A)

System.out.print(i);

System.out.println();

}

else{

for(int j=0;j<k;j++){

A[n-1] = j;

rec(n-1,k);

}

}

}

public static void main(String[] args) throws Exception{

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = new StringTokenizer(br.readLine());

N = Integer.parseInt(st.nextToken());

K = Integer.parseInt(st.nextToken());

A = new int[N];

rec(N,K);

}

}

3 3

000

100

200

010

110

210

020

120

220

001

101

201

011

111

211

021

121

221

002

102

202

012

112

212

022

122

222

삼각형의 넓이를 구하는 알고리즘

먼저 수학적으로 평면상의 삼각형의 넓이를 구하는 방법을 알아보자.

출처 : http://blog.naver.com/dalsapcho/20131270309

S: 삼각형의 넓이, a,b,c: 삼각형 각 변의 길이, h: 삼각형의 높이, R:삼각형 외접원의 반지름, r:삼각형 내접원의 반지름, x1,y1,x2,y2,x3,y3: 삼각형 꼭지점의 좌표

1번 공식은 삼각형 넓이의 정의이며 2번 공식이 기본식으로 나머지식들이 유도된다. 유도되는 과정에서 코사인제2법칙, 정점과 직선사이의 거리, 직선의 방정식이 활용된다. 3번은 헤론의 공식이다.

위 출처의 6가지 공식을 정리해서 알고리즘에 적용할 수 있는 수학적 공식은 이렇게 된다.

삼각형의 한변의 길이와 높이를 알때 : 1번 공식

삼각형의 두변의 길이와 끼인각을 알때 : 2번 공식

삼각형의 세변의 길이를 알때 : 3번 공식

삼각형 세변의 좌표를 알때 : 6번 공식

내접원과 외접원의 반지름을 알아도 3번공식이 있기 때문에 꼭 4,5번 공식을 알고리즘에 활용할 이유는 적어보인다.

특히 삼각형 세변의 좌표를 알때가 많이 사용될듯 한데 꼭지점중 하나를 원점으로 이동하여 삼각형을 평행이동시키면 넓이는 동일하기때문에 공식이 아래와 같이 간단해진다.

S = |(X1 * Y2) - (X2 * Y1)|/2

이를 자바로 구현해보면 아래와 같다.

입력 : X1 Y1 X2 Y2 X3 Y3 의 좌표를 공백으로 구분하여 한줄로 입력

import java.io.*;
import java.util.*;
public class Triangle {

 public static void main(String[] args) throws Exception{
  int o_x,o_y;
  int[][] dot = new int[3][2];
  float answer;

  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  StringTokenizer st = new StringTokenizer(br.readLine());

  for(int i=0;i<3;i++)
   for(int j=0;j<2;j++)
    dot[i][j] = Integer.parseInt(st.nextToken());

  o_x = dot[2][0]; // x3 
  o_y = dot[2][1]; // y3

  for(int i=0;i<3;i++) // 평행이동
   for(int j=0;j<2;j++){
    if (j==0)
     dot[i][j] -= o_x;
    else
     dot[i][j] -= o_y;
   }
  answer = (float)Math.abs((dot[0][0]*dot[1][1] - dot[1][0]*dot[0][1]))/2;
  System.out.println(answer);
 }
}

기본 사칙연산 이외에 나머지를 구하는 mod 연산자 % 가 여러 program language 에 많이 사용된다.

알고리즘을 보다가 (a+b)%c = (a%c+b%c)%c 가 맞는걸로 바로 넘어가서 저게 과연 맞는것일까 하는 의문이 들었다.

일단 mod 연산자에 대한 분배법칙은 성립하지 않는다.

즉, (a+b)%c != (a%c + b%c) 이다.

하지만 (a+b)%c = (a%c+b%c)%c 은 성립한다. 이를 입증할 수 있는 간단한 증명을 메모해둔다.

 증명대상 : (a+b)%c = (a%c+b%c)%c
 A = kc + n
 B = k'c + n' 로 치환한다.
 위 치환식을 좌우에 대입
 (kc+n + k'c + n')%c = ((kc+n)%c + (k'c+n')%c)%c
  (k+k') = m 로 정의하고 (XZ + Y)%Z = Y%Z 이므로 (mc + n + n')%c = (n+n')%c 이 성립한다.

단순 부분 문자열 찾기

import java.io.*;
public class Findsubstring {

 public static void main(String[] args) throws Exception{
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String A = br.readLine();
  String B = br.readLine();
  
  br.close();
  int num=0;
  String ans="";
  
  for(int i=0;i<=A.length()-B.length();i++){
   if (B.equals(A.subSequence(i,B.length()+i))){
    num++;
    if ("".equals(ans))
     ans = ans + Integer.toString(i+1);
    else
     ans = ans+" "+ Integer.toString(i+1);
   }
  }
  System.out.println(num);
  System.out.println(ans);
 }
}

입력

ABAABCCA
AA

출력

1
3

입력

AAAA
AA

출력

3
1 2 3