완전 검색 - 순열

순열

Permutation

서로 다른 것들 중 몇 개르 뽑아서 한 줄로 나열하는 것
서로 다른 n개 중 r개를 선택하는 순열 : nPr
nPr = n * (n-1) * (n-2) * … * (n-r+1)
nPn = n!이라고 표기하며 Factorial이라 부른다.

순열을 생성하는 방법

PermutationTest1.java
PermutationTest2.java
예) {1, 2, 3}을 포함하는 모든 순열을 생성하는 함수
재귀 호출을 통한 순열 생성

numbers[] : 순열 저장 배열
isSelected[] : 인덱스에 해당하는 숫자가 사용 중인지 저장하는 배열
perm(cnt) // cnt : 현재까지 뽑은 순열 수의 개수
  if cnt == 3
    순열 생성 완료
  else
    for i from 1 to 3
      if isSelected[i] == true then continue
      numbers[cnt] <- i
      isSelected[i] <- true
      perm(cnt+1)
      isSelected[i] <- false
    end for

예) N개의 원소를 포함하는 모든 순열을 생성하는 함수(1<=N<=10)
재귀 호출을 통한 순열 생성

input[] : 숫자배열, numbers[] : 순열 배열
isSelected[] : 인덱스에 해당하는 숫자가 사용 중인지 저장하는 배열
Perm(cnt) // cnt : 현재까지 뽑은 순열 수의 개수
  if cnt == N
    순열 생성 완료
  else
    for i from 0 to N-1
      if isSelected[i] == true then continue
      numbers[cnt] <- input[i]
      isSelected[i] <- true
      perm(cnt+1)
      isSelected[i] <- false
    end for

완전 검색 - 조합

조합

combination

서로 다른 n개의 원소 중 r개를 순서 없이 골라 낸 것
nCr = n!/(n-r)!r! ; (n>=r)
nCr = n-1Cr-1 + n-1Cr ; 재귀적 표현
nC0 = 1

조합을 생성하는 방법

CombinationTest.java
예) {1, 2, 3, 4}중 원소 3개를 포함하는 모든 조합을 생성
반복문을 통한 조합 생성

for i from 1 to 4
  for j from i+1 to 4
    for k from j+1 to 4
      print i, j, k
    end for
  end for
end for

재귀 호출을 이용한 조합 생성 알고리즘

nCr -> n개의 원소 중 r개 원소를 갖는 조합 생성
input[] : n개의 원소를 가지고 있는 배열
numbers[] : r개의 크기의 배열, 조합이 저장될 배열

comb(cnt, start) // cnt : 현재까지 뽑은 조합 원소 개수, start : 조합 시도할 원소의 시작 인덱스
  if cnt == r
    조합 생성 완료
  else
    for i from start to n-1
      numbers[cnt] <- input[i];
      comb(cnt+1, i+1);
    end for
end comb()

완전 검색 활용 - 주사위 던지기

DiceTest.java

주사위를 3번 던져서 나올 수 있는 모든 경우 - 중복 가능, 순서 고려 : 중복 순열(nπr = n^r)
주사위를 3번 던져서 모두 다른 수가 나올 수 있는 모든 경우 - 중복 x, 순서 고려 : 순열(nPr)
주사위를 3번 던진 결과가 다음과 같이 중복 되는 경우를 제외하고 나올 수 있는 모든 경우 - 중복 가능, 순서 x : 중복 조합(nHr = n+r-1Cr)
주사위를 3번 던져서 모두 다른 수가 나올 수 있는 모든 경우 - 중복 x, 순서 x : 조합(nCr)

완전 검색 - 부분집합

부분 집합

집합에 포함된 모든 원소들을 선택하는 것이다.
다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 것이다.
- 예) knapsack
부분 집합의 수
- 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개 이다.
- 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다.

부분 집합 생성하는 방법

SubSetTest.java</br> 예) {1, 2, 3} 집합의 모든 부분집합(Power Set)생성
반복문을 통한 부분집합 생성

For i in 1 -> 0
  selected[1] <- i  // 원소1
  For j in 1 -> 0
    selected[2] <- j  // 원소2
    For k in 1 -> 0
      selected[3] <- k  // 원소3
      For m in 1 ->3  // 생성된 부분 집합 출력
        if selected[i] == 1 then
          print i

입력된 숫자로 구성된 집합의 모든 부분집합(Power Set) 생성
재귀적 구현을 통해 생성하는 방법

각 원소를 부분집합에 포함/비포함의 형태로 재귀적 구현을 함

input[] : 숫자 배열
isSelected[] : 부분집합에 포함/비포함 여부를 저장한 배열

generateSubset(cnt) // cnt : 현재까지 처리한 원소 개수
  if(cnt == N)
    부분집합 완성
  else
    isSelected[cnt] <- true
    generateSubSet(cnt+1)
    isSelected[cnt] <- false
    generateSubSet(cnt+1)
end generateSubSet()

완전 검색 - 부분집합의 합

부분집합의 합 문제

유한개의 정수로 이루어진 집합이 있을 대, 이 집합의 부분집합 중에서 그 집합의 원소를 모두 더한 값이 0이 되는 경우가 있는지를 알아내는 문제
완전검색 기법으로 부분집합 합 문제를 풀기 위해서는, 우선 집합의 모든 부분집합을 생성한 후에 각 부분집합의 합을 계산해야한다.

스택(Stack)

Stack의 특성

자료를 쌓아 올린 형태의 자료구조이다.
스택에 저장된 자료는 선형 구조를 갖는다.
- 선형구조: 자료간의 관계가 1대1의 관계를 갖는다.
- 비선형구조: 자료간의 관계가 1대N의 관계를 갖는다.(예: 트리)
스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다.
후입선출구조 (LIFO, Last In First Out)
- 마지막에 삽입한 자료를 가장 먼저 꺼낸다.

주요 연산

push : 저장소에 자료를 저장한다.(삽입)
pop : 저장수에서 자료를 꺼낸다.(삭제), 꺼낸 자료는 삽입한 자료의 역순으로 꺼낸다.
peek : 스택의 top에 있는 item(원소)을 반환한다.
isEmpty
size

스택 응용1 : 괄호 검사

괄호의 종류 : [], {}, ()
조건
1. 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야한다.
2. 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
3. 괄호 사이에는 포함 관계만 존재한다.

알고리즘

문자열에 있는 괄호를 차례대로 조사하면서 왼쪽 괄호를 만나면 스택에 삽입하고, 오른쪽 괄호를 만나면 스택에서 top 괄호를 삭제한 후 오른쪽 괄호와 짝이 맞는지를 검사한다.
이 때, 스택이 비어 있으면 조건1 또는 조건2에 위배되고 괄호의 짝이 맞지 않으면 조건3에 위배된다.
마지막 괄호까지 조사한 후에도 스택에 괄호가 남아 있으면 조건 1에 위배된다.

스택 으용2 : function call

Function call

프로그램에서의 함수 호출과 복귀에 따른 수행 순서를 관리
- 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조이므로, 후입선출 구조의 스택을 이용하여 수행순서 관리
- 함수 호출이 발생하면 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임(stack frame)에 저장하여 시스템 스택에 삽입
- 함수의 실행이 끝나면 시스템 스택의 top원소(스택 프레임)를 삭제(pop)하면서 프레임에 저장되어 있던 복귀주소를 확인하고 복귀
- 함수 호출과 복귀에 다라 이 과정을 반복하여 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 된다.

스택 활용 - 계산기

문자열로 된 계산식이 주어질 때, 스택을 이용하여 이 계산식의 값을 계산할 수 있다.
문자열 수식 계산의 일반적 방법
step1. 중위 표기법의 수식을 후위 표기법으로 변경한다.(스택 이용)
중위표기법(inifix notation) : 연산자를 피연산자의 가운데 표기하는 방법
A+B

수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.
각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다.
괄호를 제거한다.

step2. 후위 표기법의 수식을 스택을 이용하여 계산한다.

연산자를 피연산자 뒤에 표기하는 방법
AB+

피연산자를 만나면 스택에 push한다.
연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고, 연산결과를 다시 스택에 push한다.
수식이 끝나면, 마지막으로 스택을 pop하여 출력한다.

스택 활용 - 브라우저

표준 웹 브라우저는 방문한 페이지들 내에서 이전, 이후 페이지를 방문하는 기능이 있다.
V(isit) : url로 방문
B(ack) : 뒤로
F(orward) : 앞으로

큐(Queue)

Queue의 특성

스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조
- 큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조
선입선출구조(FIFO: First in First Out)
- 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입(First in)된 원소는 가장 먼저 삭제(First Out) 된다.

큐의 구조 및 기본연산

선입선출 구조

큐의 기본 연산

삽입 : enQueue

삭제 : deQueue

Queue API

java.util.Queue

큐에 필요한 연산을 선언해 놓은 인터페이스
LinkedList 클래스를 Queue 인터페이스의 구현체로 많이 사용

주요 메소드

offer()
poll()
isEmpty()
size()

큐 활용 - 버퍼

버퍼

데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역
버퍼는 일반적으로 입출력 및 네트워크와 관련된 기능에서 이용된다.
순서대로 입력/출력/전달되어야 하므로 FIFO 방식의 자료구조인 큐가 활용된다.

완전 검색(순열, 조합, 부분집합)