Unique Life

출처: http://unix.stackexchange.com/questions/122676/how-to-mount-an-remote-filesystem-with-specifying-a-port-number

http://devanix.tistory.com/257

방법1)

sshfs -p 42224 -C user@server:/ ~/sshfs/

방법2)

 sudo mount -o port=1122 -t nfs 11.11.11.111:/some_directory /mnt/test/

출처:http://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Backtracking-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9

백트래킹

정의 : 여러 해들 중에 조건에 맞는 모든 해를 찾는 알고리즘.

알고리즘

1. 후보 해를 선택한다.

2. 조건에 따라 후보 해에 적절성 검사를 시행한다. 통과하지 못하면 지금 현재 선택한 후보 해를 버리고 1로 돌아가 후보 해를 다시 선택한다.

3. 적설성 검사가 통과한 경우 이 후보 해가 문제의 해가 되는지 검사한다. 검사를 통과하면 이것이 문제의 해이고, 검사를 통과하지 못하면 1로 돌아가 후보 해를 계속해서 선택한다.

백트래킹의 활용

1. 미로 탈출로 찾기

재귀함수를 통해 백트래킹으로 미로 탈출로를 찾아보자. 

알고리즘

1. 시작점을 현재 위치로 지정하고, 이동방향을 북으로 설정한다.

2. 현재 위치에서 가고자 하는 이동 방향으로 이동이 가능한지 확인한다. 벽과 이미 지나온 길은 이동가능한 길이 아니다.

3. 현재 가고자 하는 이동 방향으로 이동이 가능하면 그곳으로 이동한다. 이동이 불가능하면 방향을 바꾸어 다시 2번을 수행한다. 모든 방향으로 이동이 불가능하면 이전 위치로 되돌아간다.

4. 출구에 다다르거나 미로 내의 모든 길을 방문할때까지 2, 3단계를 반복한다.

3번 과정에서 이동하는 부분을 재귀함수로 구현하면 될 것이다. 이동이 가능하면 재귀함수를 통해 그곳으로 이동하면 모든 방향으로 이동이 불가능하면 반환을 통해 재귀함수를 탈출하여 이전 상태로 돌아가면 될 것이다.

2. N개의 퀸

체스에서 퀸은 모든 방향으로 거리 제한없이 움직일 수 있는 말이다. N개의 퀸 문제는 N × N 크기의 체스판에서 N개의 말들이 서로 공격이 불가능하게 배치하는 모든 경우를 구하는 문제이다. 

알고리즘

1. 첫 행, 첫 열을 시작점으로 지정한다.

2. 현재 지점에서 퀸을 놓으면 다른 퀸에게 위협을 받는지 검사한다. 이전 단계에서 놓은 퀸들 중에 현재 지점에서의 퀸의 행 값이 같으면 수평방향으로 위협을 받는 것이고, 열 값이 같으면 수직방향으로 위협을 받는 것이다. 행의 차와 열의 차가 같으면 대각선 방향으로 위협을 받고 있는 것이다.

3. 위협을 받고 있지 않다면 행의 값을 증가시키고 열의 첫번째 값으로 가서 2를 수행한다. 위협을 받고 있다면 열의 값을 증가시켜서 2를 수행한다. 열의 마지막 값에서도 위협을 받고 있다면 이전 단계의 퀸의 위치로 되돌아간다.

4. 마지막 행, 마지막 열에 다다르면 종료한다.

과정 3을 재귀함수로 구현하면 될 것이다.

출처:http://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Dynamic-Programming-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95

동적 계획법

정의 : 어떤 문제가 반복적이고 최적 하위구조로 이루어질때, 하위구조에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법

최적 하위구조(Optimal Substructure)란 전체 문제의 답이 부분 문제의 답으로부터 만들어지는 구조를 말한다. 예를 들어 어떤 문제를 7개의 하위문제로 나눌 수 있을때, 7개의 하위문제의 답을 모두 얻어야 이 문제의 답을 구할 수 있다면 이 문제는 최적 하위구조를 갖추었다고 할 수 있다.

분할정복과 비슷해 보이지만, 분할정복은 문제를 큰부분에서 작은부분으로 나누는데반해(Top-Down), 동적 계획법은 제일 작은 부분부터 큰 문제로 풀어 올라간다(Bottom-Up). 또한 분할정복은 나눈 문제들을 완전히 새로운 하나의 독립된 새로운 문제로 보지만, 동적 계획법은 이전 단계의 답에 의존적이다. 그래서 한번 푼 적 있는 문제는 다시 푸는 일이 없도록 테이블 등에 저장해둔다.

알고리즘

1. 문제를 부분 문제로 나눈다.

2. 가장 작은 부분의 문제부터 답을 구한 뒤 테이블에 저장한다.

3. 테이블에 저장되어 있는 부분 문제의 답을 이용하여 점차적으로 상위 부분의 문제의 답을 구한다.

동적 계획법의 활용

1. 피보나치 수열 (Fibonacci Sequence)

피보나치 수열은 다음과 같이 정의할 수 있다.

이것을 그냥 코드로 옮기면 다음과 같이 작성된다.

이 알고리즘의 수행시간은 으로 상당히 비효율적이다.

동적 계획법을 이용하여 이 알고리즘을 재구성해보자.

먼저 문제를 부분 문제로 나눈다.

은  과 의 합이다. 은 와 의 합이다.

그리고 은 과 의 합이다. 이로부터 이라는 문제를 ,, …, , , 의 하위구조로 나눌 수 있는 것을 알 수 있다.

두번째로 작은 부분의 답을 구한뒤 테이블에 저장한다.

인덱스	저장된 값
0	0
1	1
2	1
3	2
4	3
5	5
6	8
...	...
n-2
n-1
n

과 는 이미 정의되어 있는 값을 저장하면 되고, 부터는 테이블에 저장된 값을 이용하여 답을 구해 나간다. 이렇게 계속 구해나가면 의 값을 구할 수 있다.

이렇게 구한 피보나치 수의 시간 복잡도는 이다.

분할정복으로 구한 시간 복잡도는 이였지만 동적 계획법으로 구한 시간 복잡도는 로써 분할정복보단 떨어진다. 더 나은 기법을 알기 위해서가 아니라 알고리즘 설계 기법의 이해를 위한 것이므로 뭐가 더 우수한지는 논외로 하기로 한다.

출처:http://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Divide-and-Conquer-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5

분할정복

정의 : 분할정복 알고리즘은 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘이다.

알고리즘을 설계하는 요령

(1) Divide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다.

(2) Conquer : 나누어진 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 푼다.

(3) Combine : Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다.

• 문제를 제대로 나누면 Conquer하는 것은 쉽기 때문에 Divide를 제대로 하는 것이 가장 중요하다.
• 분할정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할정복 알고리즘의 효율성을 깎아내릴 수 있다.

분할정복의 응용

1. 병합 정렬 (Merge Sort)

헝가리 출신 미국인 수학자인 존 폰 노이만이 1945년에 개발한 알고리즘이다. 시간복잡도는 이고, 공간복잡도는 이다.

알고리즘

1. 정렬할 데이터 집합의 크기가 0또는 1이면 이미 정렬된 것으로 보고, 그렇지 않으면

2. 데이터 집합을 반으로 나눈다.

3. 원래 같은 집합에서 나뉘어져 나온 데이터 집합 둘을 병합하여 하나의 데이터 집합으로 만든다. 단, 병합할 때 데이터 집합의 원소는 순서에 맞춰 정렬한다.

4. 데이터 집합이 다시 하나가 될 때까지 3을 반복한다.

예를 들어 다음과 같은 데이터 집합이 있다고 해보자.

알고리즘의 1~2 과정을 반복하여 나눈다. 색칠한 부분은 나눈 기준이 되는 부분이다.

분할을 했으니 정복을 할 차례다. 3~4과정을 반복해서 수행한다.

조각난 데이터 집합을 정렬해가면서 병합하면 결국 완전히 정렬된 하나의 데이터 집합을 얻는 알고리즘이다.

그런데 병합이 어떻게 정렬하면서 합칠 수 있는 것일까.

두 데이터 집합을 정렬하면서 합치는 방법

1. 두 데이터 집합의 크기의 합만큼의 크기를 가지는 빈 데이터 집합을 만든다.

2. 두 데이터 집합의 첫 번째 요소들을 비교하여 작은 요소를 빈 데이터 집합에 추가한다. 그리고 새 데이터 집합에 추가한 요소는 원래 데이터 집합에서 삭제한다.

3. 원래 두 데이터 집합의 요소가 모두 삭제될 때 까지 2를 반복한다.

예를 들어 다음과 같은 데이터 집합 A, B와 이 두 데이터 집합의 크기의 합만큼의 크기를 가지는 빈 데이터 집합인 C가 있다고 하자.

두 데이터 집합의 첫 번째 요소를 비교한다. A의 첫 번째 요소는 2, B의 첫번째 요소는 1이므로 B의 것이 더 작다. C에 1을 추가하고 B에서 1을 삭제한다.

그 다음 A의 2와 B의 3을 비교한다. 2가 작으니 C에 2를 추가하고 A에서 2를 삭제한다.

A의 5와 B의 3을 비교한다. 3이 작으니 C에 3을 추가하고 B에서 3을 삭제한다.

이렇게 데이터 A와 B의 요소들을 비교해서 C에 넣고 A와 B의 각 요소들을 삭제해나가다보면, A에 9하나만 남게된다. B에는 비교할 요소가 남아 있지 않으므로 그냥 9를 C에 추가하고 A에서 9를 삭제한다. 이로써 A와 B의 요소들이 모두 삭제되었고 C는 정렬된 데이터 집합이 되었다.

2. 거듭 제곱 (Exponentiation)

n거듭 제곱은 자신을 n번 곱해야 함으로 의 시간이 소요된다. 이것을 개선하기 위해서 연산방법을 조금 바꾸어보자.

은 다음과 같이 정의되지만,

다음과 같이 표현할 수도 있다.

을 구할 때 C를 8번 곱하지 않고 를 구한 뒤 제곱을 두 번 더 반복하면 결국 세번의 연산만으로 같은 결과를 얻을 수 있다.

지수가 짝수일때는 지수를 반으로 나눠서 곱한다.

지수가 홀수일때는 지수에서 1을 빼고 반으로 나누어서 곱하고 밑을 한번 더 곱하면 된다.

이렇게 지수를 반으로 나눠가는 거듭 제곱 알고리즘의 수행 시간은 이다.

3. 피보나치 수열 (Fibonacci Sequence)

피보나치 수열은 다음과 같이 정의된다.

이 알고리즘으로는 걸리는 시간은 이다.

연산을 줄이기 위해 2차 정사각행렬을 이용한다.

 이므로 n제곱을 하게 되면

  이렇게 거듭제곱 알고리즘때와 비슷하게 나타낼 수 있다.

수행 시간 또한 거듭 제곱 알고리즘과 똑같은 이 걸리게 된다.