KnowRob 설치

KnowRob의 설치
필요조건: Ros의 설치

1. 환경설정 => wiki.ros.org/ROS/Tutorial/InstallingandConfiguringROSEnvironment

2. Rosjava 설치 => http://wiki.ros.org/rosjava/Tutorials/indigo/Source%20Installation

3.

rosdep update cd ~/catkin_ws/src wstool merge https://raw.github.com/knowrob/knowrob/indigo/rosinstall/knowrob-base.rosinstall wstool update rosdep install --ignore-src --from-paths stacks/ cd ~/catkin_ws catkin_make

%% wstool merge https://raw.github.com/knowrob/knowrob/indigo/rosinstall/knowrob-base.rosinstall

이 부분에서 에러가 날 때가 있다.

이럴 경우에는 wstool init ~/catkin_ws/src 로 catkin을 초기화해보자!!!

rosbridge

rosbridge 설치
sudo apt-get install ros-<rosdistro>-rosbridge-suite
환경 변수 설정
source /opt/ros/<rosdistro>/setup.bash
running
roslaunch rosbridge_server rosbridge_websocket.launch

TopCoder 알고리즘 트레이닝 (1)

알고리즘에 필요한 것
if else
for
배열
정렬 => Array.sort(array);  => import java.util.*;
문자열 처리
ex)
String s = "abc";
//동일 판정
if(s.equals("abc")) System.out.println("equal");
//문자 하나 추출
char c = s.charAt(1); // 'b'
//문자열 연결
s = "def" + s + "ghi"; // "defabghi"
//문자열 잘라내기
s = s.substring(3, 3); // "abc"
연관 배열(순서대로 데이터를 관리하지 못함)
ex) import java.util.*;
void countStrings(String[] s)
{
      Map<String, Integer> hm=new HashMap<String, Integer>();
      for(int i=0; i < s.length; i++) {
          if(!hm.containskey(s[i])) hm.put(s[i], 0);
          hm.put(s[i], hm.get(s[i]+1);
           }
       for(String key : hm.keySet()) {
        System.out.println(key + " " + hm.get(key));
     }
}

우분투 node.js 설치

우분투 14.04 에 node.js 설치
NVM(Node.js version manager) 이용. node.js 를 여러개 설치 가능
# apt-get update

# apt-get install build-essential libssl-dev

nvm 홈페이지에서 최신 버전 확인 후 설치 (https://github.com/creationix/nvm)

# curl https://raw.githubusercontent.com/creationix/nvm/v0.18.0/install.sh | bash

~/ .bashrc 파일이 수정되므로 다시 로그인 한다.

node.js 버전 확인
# nvm ls-remote

....
v0.11.15
v0.11.16
v0.12.0
v0.12.1
v0.12.2
v0.12.3
v0.12.4
v0.12.5
v0.12.6
v0.12.7

최신 버전설치
# nvm install 0.12.7
 
node.js 버전 확인
# node -v

설치된 node.js 확인
# nvm ls

node.js alias 설정
# nvm alias default 0.12.7

alias 사용
# nvm use default

npm(Node.js package manager) 이용해서 express 설치. 현재 디렉토리 아래에 node_modules 라는 디렉토리를 만들고 그 아래에 설치
# npm install express

현재 node.js 버전에서 전역적으로 패키지를 사용하도록 설치할려면 -g 옵션을 사용한다.
# npm install -g express

~/.nvm/v0.12.7/lib/node_modules/express 와 같이 nvm 아래에 node.js 버전별로 설치가 된다.

# npm link express
현재 디렉토리의 node_modules 아래에 express 라는 이름으로 아래의 전역 패키지로 심볼릭 링크가 걸린다.

환경변수 설정법

1. 환경변수 설정

1.1 환경변수를 command line으로 현재 터미널에만 적용하는 방법

JAVA_HOME이라는 환경변수명에 값은 /usr/lib/jvm/java-7-openjdk-amd64/ 으로 설정하고자 하면 아래 명령어를 사용
 export JAVA_HOME=/usr/lib/jvm/java-7-openjdk-amd64/

      env | grep JAVA_HOME   으로 제대로 환경변수가 올라갔는지 확인해보면

      JAVA_HOME=/usr/lib/jvm/java-7-openjdk-amd64/
      으로 나오면 제대로 설정된 것
   
   현재 터미널에만 적용되고, 다음 로그인시에 또 쓰고 싶은 환경변수라면 반복해서 작성해야 함
      계속 사용하고 싶은 환경변수는 1.2를 참고해서 설정하기

     

1.2 환경변수를 앞으로 계속 적용하는 방법
   
      1.1과 유사한데요. 모든 사용자가 사용하고 계속 사용할 수 있는 환경변수를 적용하고자 하시면 /etc/bash.bashrc
      (bash 쉘만 해당, zsh, csh은 다른 파일에...)
      위 파일의 마지막에 export JAVA_HOME=/usr/lib/jvm/java-7-openjdk-amd64/ 를 작성해주시면 됩니다.
      바로 환경변수가 적용되지 않는다.
      source /etc/bash.bashrc 을 통해서 환경변수를 적용하고, 이제부터 누구나 로그인해도 JAVA_HOME이라는 환경변수명을 사용할 수 있습니다.

혹시나 특정 사용자에게만 환경변수를 적용하려 한다면 /home/userName/.bashrc

예를 들어서 mmm이라는 사용자에게만 JAVA_HOME 환경변수를 적용하고자 하시면 /home/mmm/.bashrc 를 열어서
맨 마지막에 export JAVA_HOME=/usr/lib/jvm/java-7-openjdk-amd64/ 

2. 환경변수 해제

      unset 환경변수명
      ex) unset JAVA_HOME

Ontology(2)

RDF = 주어 + 동사 + 목적어

URIref : 절대로 중복될 수 없는 유일성을 가진 referenece

RDF Schema : 클래스 상속 지원


주요 어휘
rdfs:Class   = 클래스를 정의하는 요소, rdf : about 애트리뷰트에 URIef를 써 줌
rdfs:label    = 사람이 이해할 수 있는 라벨을 붙인다.
rdfs:subClassOf = 한 클래스가 다른 기존 클래스의 하위 클래스임을 명시
rdfs:Property = 클래스의 속성을 정의하는 요소값
rdfs:domain = 한 속성이 어떤 클래스에 속하는 지 알려주는 요소
rdfs:range = 한 속성이 취할 수 있는 값의 범위를 정의하는 요소
rdfs:Literal = 상수값

rdf 코딩의 예
<rdf : RDF
       xmlns : rdf="htttp://www.w3.org/1999/02/22-rdf-syntax-nx#"
       xmlns : ontbook="http://Ontology.snu.ac.kr/ont-book#">

      <rdf : Description rdf : about="&ontbook : LeeSY">
              <ontbook : owns>
                         <rdf : Description rdf : about="&ontbook : OntologyTech">
                                       <ontbook : hasHompage rdf : resource =
                                                "http://www.Ontology.com/~ont"/>
                          </rdf: Description>
              </ontbook : owns>
              <ontbook : majorsln rdf : resource="&ontbook ; Electronic"/>
              <ontbook : age rdf : datatype="&xsd ; Integer">22</ontbook : age>
      </rdf : Description>
</rdf : RDF>                  
                         

OWL
1. Class
동일한 속성을 지니고 있어하나의 부류로 모아지는 개체들의 그룹
<owl : Class rdf : ID="레이저 프린터">
      <rdfs : subClassOf rdf : resource= "#프린터"/>
</owl : Class>

2. 속성
클래스와 클래스의 관계
    1. ObjectProperty: 클래스의 인스턴스를 다른 클래스에 속한 인스턴스와 연결
    2. DatatypeProperty: 클래스의 인스턴스를 특정한 데이터타입과 연결
<owl : ObjectProperty rdf : ID="제조하다">
            <rdfs : domain rdf : resource="#프린터"/>
            <rdfs : range rdf : resource="#제조회사"/>
</owl : ObjectProperty>

 속성도 클래스와 마찬가지로 계층적 관계를 나타낼 수 있다.
<owl : ObjectProperty rdf : ID="isADaughterOf">
            <rdfs : subProperty rdf : resource="#isAChildOf"/>
</owl : ObjectProperty>

OWL의 새로운 기능
1. 클래스의 bool 연산
      owl : intersectionOf , owl : unionOf, owl : complementOf
<owl: Class rdf : ID="사람">
       <owl : unionOf>
                 <owl : Class rdf : ID="여성"/>
                 <owl : Class rdf : ID="남성">
                           <owl : complementOf rdf : resource="#여성"/>
                  </owl : Class>
       </owl : unionOf>
</owl : Class>

2. 열거형 클래스
      owl : oneOf
<owl : Class rdf : ID="요일">
    <owl : oneOf rdf : parseType="Collection">
              <owl : Thing rdf : about="#월요일"/>
              <owl : Thing rdf : about="#화요일"/>
              <owl : Thing rdf : about="#수요일"/>
              <owl : Thing rdf : about="#목요일"/>
              <owl : Thing rdf : about="#금요일"/>
              <owl : Thing rdf : about="#토요일"/>
              <owl : Thing rdf : about="#일요일"/>
    </owl : oneOf>
</owl : Class> 

3. 클래스의 비접합성(교집합이 없는 경우)
     owl : disjointWith
<owl : Class rdf : ID="레이저 프린터">
      <owl : disjointWith rdf : resource="#잉크젯 프린터"/>
</owl : Class>
 
4. 속성에 대한 다양한 범위 지정
       제약이 있는 속성에 대한 정의 : onProperty
        속성 값의 제한 : allValueFrom, someValueFrom, hasValue
ex)
<owl:Class rdf : ID = "초식 동물">
        <rdfs : subClassOf>
         <owl : restriction>   
                <owl:onProperty rdf : resource="#먹다"/>
                <owl:allValuesFrom rdf : resource="#풀"/>
          </owl : Restriction>
          </rdfs : subClassOf>
</owl : Class>
   => owl : Restriction 를 통해 임의의 클래스를 만들고 그 클래스 밑에 의미를 부여한 후
         클래스 '초식 동물'이 그 의미를 모두 상속한다.

%% allValuesFrom : 이 속성만을 가진다.
       someValuesFrom : 이 속성뿐만 아니라 다른 속성을 가질 수 있다.

5. 관계차수 표현
어떤 클래스의 인스턴스가 특정 속성을 통해 연결될 수 있는 값이 최소한 , 최대한 이 몇  개인지를 제한하는 것
owl:Cardinality : ==
owl:maxCardinality : 최대한 n개
owl:minCardinality : 최소한 n개
<owl : Restriction>
        <owl : onProperty rdf : resource="#전공하다"/>
        <owl : minCardinality rdf : datatype="&xsd ; nonNegativeInteger">
         1
         </owl:minCardinality>
</owl : Restriction>

특별한 속성을 통한 추론 기능의 활성화
<rdf : type rdf : resource = "&owl; ________________" />
1. 이행속성(TransitiveProperty)
     A - P - B && B - P - C  => A - P - C
<owl:ObjectProperty rdf : ID="isMoreExpensiveThan">
      <rdf : type rdf : resource="&owl; TransitiveProperty>
</owl : ObjectProperty>

<owl:Class rdf : ID="프린터1">
      <isMoreExpensiveThan rdf : resource="#프린터2"/>
</owl : Class>

<owl:Class rdf : ID="프린터2">
      <isMoreExpensiveThan rdf : resource="#프린터3"/>
</owl : Class>
2. 대칭속성(SymmetricProperty)
    주어 와 목적어를 바꿔도 같은 의미일 때
<owl: ObjectProperty rdf : ID="대체하다">
       <rdf: type rdf : resource="&owl; SymmetricProperty"/>
</owl:ObjectProperty>

<owl:Class rdf : ID="레이저 프린터">
<대체하다 rdf:resource="#잉크젯 프린터"/>
</owl:Class>
 
3. 함수속성(FunctionalProperty)
    주어 와 목적어가 하나의 동사에 대하여 1:多 대응 일때
<owl: ObjectProperty rdf: ID="전공하다">
      <rdf: type rdf : resource="&owl; FunctionalProperty"/>
       <rdfs :domain rdf : resource="#학생"/>
       <rdfs : range rdf : resource="#전공"/>
</owl : ObjectProperty>

4. 역함수속성(InverseFunctionalPropety)
     주어 와 목적어가 하나의 동사에 대하여 1:1 대응 일때
<owl: ObjectProperty rdf: ID="학번을 가지다">
      <rdf: type rdf : resource="&owl; InverseFunctionalProperty"/>
      <rdf: type rdf : resource="&owl; FunctionalProperty"/>
       <rdfs :domain rdf : resource="#학생"/>
       <rdfs : range rdf : resource="#학번"/>
</owl : ObjectProperty>

5. 역의 관계에 있는 속성(InverseOf)
     ex) ~의 부모이다 <=> ~의 자식이다
<owl : ObjectProperty rdf : ID="isParentOf">
       <owl : inverseOF rdf : resource="#isChildOf"/>
</owl : ObjectProperty>

6. 클래스와 속성 간의 동치성과 비동치성 표현
equivalentClass equivalentProperty sameAs differentFrom Alldifferent
Why? 동음이의어 혹은 동의이음어 때문
<owl : Class rdf : ID="PrintingPaper">
      <owl:equivalentClass rdf : resource="&사무용품; CopyPaper">
</owl : Class>

토픽맵의 개념
1. 자원 : 컴퓨터 상에서 URI와 같이 주소를 가짐으로서 식별이 가능한 정보
2. 토픽 : 현실세계의 주제를 상징하는 컴퓨터 내의 자원
3. 어커런스 :  주제에 대한 정보자원의 위치
4. 관계 : 토픽들 간의 연관성

주제와 토픽의 관계
주제: '어떠한 것'
토픽: '그 어떠한 것을 컴퓨터가 이해하고 처리할 수 있는 형태로 표현한 것'

주제식별
하나의 토픽이 여러 개의 주제를 표현하거나 여러 개의 토픽이 동일한 주제를 표현하는 모호함을 없애기 위해 필요
1. 주제가 컴퓨터상에 존재하는 경우
=> 컴퓨터상의 주소를 통해 식별
2. 주제가 현실세계에 존재하는 경우
 => 컴퓨터에 식별가능한 주소가 존재하지않기 때문에 주제 지시자를 사용한다.

토픽의 특성
1. 이름
인간이 토픽을 쉽게 이해하도록 만든 것
2. 어커런스(Occurrence)
주제와 관련된 자원을 연결해준다.
3. 관계(Association)
하나 이상의 토픽 간의 연관성을 표현
%% 관계를 정의하기 전에 관계 타입을 먼저 정의해야 한다.

토픽맵 기타 구성 요소
1. 범위
2. 토픽맵병합(동일한 주제식별을 가지고 있거나, 동일한 범위 내에서 동일한 기본이름을 가질때)

네트워크 (3)

연결 지향 소켓 =>  TCP
TCP의 네가지 계층

Application 영역

Transport 영역 =>   TCP  ----------------  UDP

Network 영역

Physical 영역


TCP 기반 서버의 구현
1) 서버에서의 기본적인 함수 호출 순서
  1. socket() -- 소켓 생성
  2. bind() -- 소켓에 주소 할당
---------------------------------------------------------------------------------
  3. listen() -- 연결 요청 대기 상태
  4. accept() -- 연결 허용
  5. read() & write() -- 데이터 송수신
  6. close() -- 연결 종료

2) '연결 요청 대기 상태' 로의 진입
int listen(int s, int backlog);
s: '연결 요청 대기 상태' 에서 클라이언트의 연결 요청을 받아들이는 역할을 하게 될 소켓의 파일 디스크립터
backlog : '연결 요청 대기 큐'의 크기를 나타낸다. 인자로 5가 들어오면, 큐의 크기가 5가 되어 클라이언트의 연결 요청을 5개까지 대기시킬 수 있게 된다.

3) 연결 요청 수락하기
int accept(int s, struct sockaddr *addr, int *addrlen);
s : 서버 소켓의 파일 디스크립터
addr : 연결 요청을 수락할 클라이언트의 주소 정보를 저장할 변수의 포인터
addrlen : 함수 호출 시 인자로 전달된 addr 포인터가 가리키는 구조체의 크기를 저장하고 있는 변수의 포인터( == 리턴 받은 클라이언트의 주소 정보 길이 )
*accept 함수는 호출 성공 시 내부적으로 클라이언트와의 데이터 입출력을 하기 위해 사용될 소켓을 생성하고, 그 소켓의 파일 디스크립터를 리턴해준다.

TCP 기반 클라이언트의 구현

1) 클라이언트의 기본적인 함수 호출 순서

  1. socket() -- 소켓 생성

  2. connect() -- 연결 요청

  3. read() & write() -- 데이터 송수신

  4. close() -- 연결 종료

int connect(int sockfd, struct sockaddr *serv_addr, int addrlen);

sockfd : 미리 생성해 놓은 소켓의 파일 디스크립터

serv_addr : 연결 요청을 보낼 서버의 주소 정보를 지닌 구조체 변수의 포인터

addrlen : serv_addr 포인터가 가리키는 주소 정보 구조체 변수의 크기가 된다.

* connect 함수가 리턴되는 시점은, 연결 요청이 서버에 의해 수락되거나, 오류가 발생해서 연결 요청이 중단되는 경우이다. 만약에 연결 요청이 바로 이루어지지 않고 서버의 대기 큐에서 대기하고 있는 상태라면 connect 함수는 리턴되지 않고 블로킹 상태에 있게 된다.

TCP 클라이언트 서버 함수 호출 관계

Iterative 서버의 구현

에코 서버/클라이언트의 구현

에코 클라이언트 서버 모델

1) 에코 서버의 구현

클라이언트가 전송해 주는 데이터를 읽어서 버퍼에 저장한 후에 버퍼에 있는 데이터를 그대로 클라이언트에게 전송해 주게 된다.

while( (str_len = read(clnt_sock,message,BUFSIZE)) != 0) {

write(clnt_sock, message, str_len);

write(1, message, str_len);

}

close(clnt_sock);

return 0;

}

2) 에코 클라이언트의 구현
에코 클라이언트의 구현 단계에서는 데이터를 보낼 서버에 연결 요청을 보내고 수락되는 일반적인 클라이언트의 과정을 거치게 되고, 연결이 완료되면 서버로 데이터를 전송하고 에코되어 돌아오는 데이터를 수신하는 과정을 거치게 된다.
while(1) {
   // 메시지 입력, 전송
   fputs("전송할 메시지를 입력하세요 (q to quit) : ", stdout);
   fgets(message, BUFSIZE, stdin);

   if(!strcmp(message, "q\n")) break;
   write(sock, message, strlen(message));

   // 메시지 수신, 출력
   str_len = read(sock, message, BUFSIZE-1);
   message[str_len] = 0;
   printf("서버로부터 전송된 메시지 : %s \n", message);
  }
   close(sock);
   return 0;
}

에코 클라이언트!   TCP 기반에서의 완벽 구현

비연결 지향 소켓 => UDP

bash에 대해서

Bash은 Bourne Again Shell 의 축약어이다. 이것은 원래의 Bourne 쉘과 호환이 가능하며 명령 라인 편집과 같은 몇 가지 점에서 기능이 향상되었다[역자 주: Bash 쉘은 Bourne 쉘에서 작성된 프로그램을 수행할 수 있으며, Bourne 쉘 보다 더 많은 기능을 제공한다]. 또한 Bash 쉘은 리눅스 쉘이며 리눅스에서 가장 널리 사용되는 쉘이다. 쉘이 무엇인지 모르는 사람이 있을지도 모르니 설명하기로 하자. 쉘이란 사용자와 커널 사이의 매개체 역할을 하는 프로그램이다[역자 주: 쉘은 사용자로부터 명령을 받아서 그것을 프로세싱하기 위해 커널에게 넘겨주는 일을 하는 프로그램이다]. 대부분의 리눅스 소프트웨어같이, bash도 상세한 부분까지 설정할 수 있다.

설정 파일들 bash는 다섯 개의 공통된 설정 파일들을 가지고 있다. 모든 리눅스 배포본에서 이들을 찾아볼 수 있지는 않지만, 이 파일들을 만드는 것은 어렵지 않다. 이 설정  파일들은 다음과 같다:

• /etc/profile

• /etc/bashrc

• ~/.bash_profile

• ~/.bashrc

• ~/.bash_logout
  

이 파일들은 전역적인 것과 지역적인 것의 두 개 그룹으로 나누어질 수 있다. bash를 사용하는 모든 사용자에게 영향을 주는 설정 내용을 담고 있는 파일들은 전역적이다. 일반적으로 전역적인 파일은 /etc 디렉토리에 위치한다. 지역적인 파일은 사용자 개개인을 위한 설정 내용을 담고 있어서 그 파일을 사용하는 특정 사용자에게만 영향을 끼치는 파일들을 뜻한다. 이들은 대개 사용자의 홈 디렉토리에서 찾아 볼 수 있는 숨김 파일이다[역자 주: 숨김 파일은 ~/.bashrc와 같이 '.' 으로 시작한다]. 만일 여러분이 이들 파일을 갖고 있지 않다고 해도, 걱정하지 말아라. 이 NHF를 읽은 다음에 여러분 자신이 작성할 수 있을 테니까. 이제 각 설정 파일에 대한 설명을 시작하도록 하자.

/etc/profile
/etc/profile은 환경 변수와 bash가 수행될 때 실행되는 프로그램을 제어하는 전역적인 시스템 설정과 관련된 파일이다[역자 주: /etc/profile은 변수와 bash를 실행하는 모든 사용자가 수행하는 프로그램을 포함한다]. 만일 여러분이 MS-DOS 사용자라면, /etc/profile이 autoexec.bat과 같은 역할을 한다고 설명하면 더 알아듣기 쉬울 것이다.

/etc/bashrc
/etc/bashrc는 별칭(alias)과 bash가 수행될 때 실행되는 함수를 제어하는 전역적인 시스템 설정과 관련된 파일이다[역자 주: /etc/bashrc에는 별칭(긴 명령어에 대한 "바로 가기")은 물론 불려질 때 실행되는 짤막한 코드도 포함하고 있다]. 때때로 /etc/bashrc는 생략되기도 하며 그 내용은 /etc/profile에 함께 포함되기도 한다.

~/.bash_profile~/.bash_profile 은 환경 변수와 bash가 수행될 때 실행되는 프로그램을 제어하는 지역적인 시스템 설정과 관련된 파일이다. 이들 환경 변수들은 오직 그 사용자에게만 한정되며, 그 이외의 다른 사람에게는 영향을 미치지 않는다. 이 파일은 전역적인 설정 파일인 /etc/profile이 수행된다음 바로 수행된다[역자 주:  모든 사용자에게 영향을 주는 /etc/profile과는 달리, ~/.bash_profile는 오직 bash를 실행하는 그 사용자에게만 영향을 준다]. 

~/.bashrc~/.bashrc는 별칭(alias)과 bash가 수행될 때 실행되는 함수를 제어하는 지역적인 시스템 설정과 관련된 파일이다. 이들 별칭과 함수들은 오직 그 사용자에게만 한정되며, 그 이외의 다른 사람에게는 영향을 미치지 않는다. 이 파일은 전역적인 설정 파일인 /etc/bashrc이 수행된 다음 바로 수행된다[역자 주: 모든 사용자에게 영향을 주는 /etc/bashrc와는 달리, ~/.bashrc 는 오직 bash를 실행하는 그 사용자에게만 영향을 준다].

~/.bash_logout~/.bash_logout 은 사용자가 로그 아웃하기 바로 직전에 실행하는 프로그램에 관한 bash의 지역적인 시스템 설정과 관련된 파일이다. 이들 프로그램은 오직 그 프로그램을 실행하는 사용자에게만 영향을 끼치지 다른 사람에게는 아무런 영향을 주지 않는다.

Ros 나만의 정리(2)

Ros package 만들어보기
  1. manifest 파일 만들기
recommended format      
<package format="2">  
<name>foo_core</name> 
<version>1.2.4</version> 
<description> This package provides foo capability. </description> 
<maintainer email="ivana@osrf.org">Ivana Bildbotz</maintainer> <license>BSD</license> 
</package>

여러개의 패키지를 하나로 묶는 태그
<export> <metapackage /> </export>

2. CMakeList.txt 만들기
  structure
   1.version => cmake_minimum_required(VERSION 2.8.3)
   2. package name => project(robot_brain)
   3. 필요한 패키지 => find_package(catkin REQUIRED)
   4. catkin_package(
               INCLUDE_DIRS include
                 => The exported include paths (i.e. cflags) for the package
               LIBRARIES ${PROJECT_NAME}
                 => The exported libraries from the project 
               CATKIN_DEPENDS roscpp nodelet
                 => Other catkin projects that this project depends on
                DEPENDS eigen opencv)
                 => Non-catkin CMake projects that this project depends on
     5. set_target_properties(
               rviz_image_view
               PROPERTIES OUTPUT_NAME image_view
               PREFIX "")
     6. path
include_directories(include ${Boost_INCLUDE_DIRS}${catkin_INCLUDE_DIRS})
link_directories(~/my_libs)
     7. executable target을 정해준다.
add_executable(myProgram src/main.cpp src/some_file.cpp src/another_file.cpp)

     8.
add_library(${PROJECT_NAME} ${${PROJECT_NAME}_SRCS})
     9.
 target_link_libraries(<executableTargetName>, <lib1>, <lib2>, ... <libN>)
 
 System dependency 관리
Ros package가 운영체제에 있는 라이브러리를 쓰고자 할 때 System Dependency를 추가해줘야한다.
How? rosdep install package

ROS 나만의 정리(1)

ROS의 설치

필요조건: 우분투(영어 버전으로 설치)

 

software & updates 화면이 이와 같아야 한다.

확인점: main, universe, restricted, multiverse checked

           Download from:  Main server

http://wiki.ros.org/indigo/Installation/Ubuntu(Indigo)따라하기

설치하기 전에 버전 확인하기 (ROS 버전과 Ubuntu 버전)

Ros 위키에 있는 내용을 나에게 맞게 정리

rospack find  package_name : 패키지의 경로 반환

roscd package_name : 폴더 이동

roscd log : Ros의 로그파일이 저장되있는 폴더로 이동

rosls package_name : package 안의 list를 보여줌

catkin에서 작업공간 만들기
1. mkdir -p ~/catkin_ws/src
2. cd ~/catkin_ws/src
3. catkin_init_workspace
4. cd ~/catkin_ws/
5. catkin_make

catkin_make : Ros package build

roscore : Ros를 사용할 때 가장 먼저 하는 일

rosnode 명령어 : node에 대한 정보를 알고 싶을 때

rosrun package_name    node : node를 직접 실행


publish : 주는 것             subscribe : 받는 것

rqt_graph 사용
$ sudo apt-get install ros-<distro>-rqt $ sudo apt-get install ros-<distro>-rqt-common-plugins
<distro>는 자기 버전에 맞게 바꾸기 ex) indigo, hydro

rostopic 명령어 : topic을 다룰 때 사용

rostopic -h 를 통해 자세한 기능을 알아볼 것

rostopic pup topic msg_type args : 현재의 topic에 publish data
 ex)
rostopic pup
-1 : 하나의 메시지만 publish
/turtle/cmd_vel : publish 하고 싶은 topic의 이름
geometry_msgs/twist : publish 할 내용이 담겨있는 메시지
-- : option
rosrun rqt_plot rqt_plot : topic에 publish된 data를 시간에 따라 plot에 표현

rosservice : Ros의 client나 service에 쉽게 attach 가능

rosservice -h로 커맨드에 대해 알아볼 것

rosparam : Ros parameter server에 있는 data를 저장하고 조작하는 데 쓰인다.

rosparam -h로 커맨드에 대해 알아볼 것

rosed package_name filename : package_name으로 파일 수정

Ontology (1)

Ontology의 주요 구성 요소
1. 논리적 추론
2. 추상적 사고
3. 개념과 언어를 이해
4. 유사한 개념이나 사물을 분류


개념화


















1. 인식한 것들을 구분하고 구분된 영역을 무엇이라고 부르는 지 배운다.


 2. 영역안에서 객체들을 분리한다.


3. 다른 구성원들이 영역을 어떻게 분류하고 부르는 지 안다.


4. 영역안에서 분류된 각 객체들간의 관계와 고유의 속성을 정의합니다.

알고리즘 문제 해결 전략(4)

분할 정복
주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부문 문제의 답으로부터 전체 문제의 답을 계산한다.
세 가지 구성 요소
문제를 더 작은 문제로 분할하는 과정(divide)
각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)
더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)
수열의 빠른 합과 행렬의 빠른 제곱
fastSum(n) = 2*fastSum(n/2)+(n^2/4)
//필수 조건: n은 자연수
//1 + 2 + ... + n을 반환한다.
int fastSum(int n) {
   //기저 사례
   if(n == 1) return 1;
   if(n % 2 == 1) return fastSum(n-1) + n;
   return 2*fastSum(n/2) + (n/2)*(n/2);
}
행렬의 거듭제곱
A^m = (A^(m/2))*(A^(m/2))
//정방행렬을 표현하는 SqureMatrix 클래스가 있다고 가정하자.
class SquareMatrix;
// n*n 크기의 항등 행렬(identity matrix)을 반환하는 함수
SquareMatrix identity(int n);
//A^m을 반환한다.
SquareMatrix pow(const SqureMatrix& A, int m) {
   //기저 사례: A^0 = 1
   if(m == 0) return identity(A.size());
   if( m % 2 > 0) return pow(A, m-1) * A;
   SquareMatrix half = pow(A, m /2);
   //A^m = (A^(m/2))*(A^(m/2))
   return half * half;
}
나누어 떨어지지 않을 때의 분할과 시간 복잡도
같은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다.
Why? 여러 번 중복되어 계산되면서 시간을 소모하는 부분 문제들이 있다.

병합 정렬과 퀵 정렬

병합 정렬 알고리즘
1. 주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬한다.
2. 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻습니다.

퀵 정렬 알고리즘
1. 병합 과정이 필요 없도록 한쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열을 분할
=> 퀵 정렬은 파티션이라고 부르는 단계를 도입하는데, 배열에 있는 수 중 임의의 '기준 수(pivot)'를 지정한 후 기준보다 작거나 같은 숫자를 왼쪽, 더 큰 숫자를 오른쪽으로 보낸다.

일반적인 곱셈 알고리즘
//num[]의 자릿수 올림을 처리한다.
void nomalize(vector<int>& num) {
num.push_back(0);
//자릿수 올림을 처리한다.
for (int i = 0; i < num.size(); ++i) {
if (num[i] < 0) {
int borrow = (abs(num[i]) + 9) / 10;
num[i + 1] -= borrow;
num[i] += borrow * 10;
}
else {
num[i + 1] += num[i] / 10;
num[i] %= 10;
}
}while (num.size() > 1 && num.back() == 0) num.pop_back();
}
// 두 긴 자연수의 곱을 반환한다.
// 각 배열에는 각 수의 자릿수가 1의 자리에서부터 시작해 저장되어 있다.
vector<int> multiply(const vector<int>& a, const vector<int>& b) {
vector<int> c(a.size() + b.size() + 1, 0);
for (int i = 0; i < a.size(); ++i)
for (int j = 0; j < b.size(); ++j)
c[i + j] += a[i] * b[j];
nomalize(c);
return c;
}


예제: 카라츠바의 빠른 곱셈 알고리즘
카라츠바의 빠른 곱셈 알고리즘은 두 수를 각각 절반으로 쪼갠다. a와 b가 각각 256자리 수라면 a1 과 b1은 첫 128자리, a0 과 b0은 그 다음 128자리를 저장하도록 하는 것이다.
a =  a1 * 10^128 + a0
b =  b1 * 10^128 + b0
a*b =  (a1 * 10^128 + a0)*(b1 * 10^128 + b0)
      = a1 * b1 * 10^256 + (a1 * b0 + a0 * b1) * 10^256 + a0 * b0
            z2                                z1                               z0

z2 = a1 * b1;
z0 = a0 * b0;
z1 = (a0 + a1) * (b0 + b1) - z0 - z2;
=> 곱셈을 세 번밖에 쓰지 않는다.

// a += b * (10 ^ k)
void addTo(vector<int>& a, const vector<int>& b, int k);
// a -= b; a>=b를 가정
void subFrom(vector<int>& a, const vector<int>& b);
// 두 긴 정수의 곱을 반환한다.
vector<int> karatsuba(const vector<int>& a, const vector<int>& b) {
int an = a.size(), bn = b.size();
// a가 b보다 짧을 경우 둘을 바꾼다.
if (an < bn) return karatsuba(b, a);
// 기저 사례: a나 b가 비어 있는 경우
if (an == 0 || bn == 0) return vector<int>();
// 기저 사례: a가 비교적 짧은 경우 O(n^2) 곱셈으로 변경한다.
if (an <= 50) return multiply(a, b);
int half = an / 2;
// a 와 b를 밑에서 half 자리와 나머지로 분리한다.
vector<int> a0(a.begin(), a.begin() + half);
vector<int> a1(a.begin() + half, a.end());
vector<int> b0(b.begin(), b.begin() + min<int>(b.size(), half));
vector<int> b1(b.begin() + min<int>(b.size(), half), b.end());
//z2 = a1 * b1
vector<int> z2 = karatsuba(a1, b1);
//z0 = a0 * b0
vector<int> z0 = karatsuba(a0, b0);
//a0 = a0 + a1; b0 = b0 + b1
addTo(a0, a1, 0); addTo(b0, b1, 0);
//z1 = (a0*b0) - z0 - z2
vector<int> z1 = karatsuba(a0, b0);
subFrom(z1, z0);
subFrom(z1, z2);
//ret = z0 + z1 * 10^half + z2 * 10^(half*2)
vector<int> ret;
addTo(ret, z0, 0);
addTo(ret, z1, half);
addTo(ret, z2, half + half);
return ret;
}

쿼드 트리 뒤집기
대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 하나
주어진 공간을 항상 4개로 분할해 재귀적으로 표현함
검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현
1. 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림과 관계없이 b가 된다.
2. 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니다.
3. 모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 그림을 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축합니다. 이때 전체 그림의 압축 결과는 x(왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과)(왼쪽 아래 부분의 압축 결과)(오른쪽 아래 부분의 압축 결과)가 된다.

쿼드 트리 압축 풀기
char decompressed[MAX_SIZE][MAX_SIZE];
// s를 압축 해제해서 decompressed[y..y+size-1][x..x+size-1] 구간에 쓴다.
void decompress(const string& s. int y , int x, int size);

압축 문자열 분할하기
s의 나머지 부분을 넷으로 쪼개기가 어렵다
why?  각 부분의 길이가 일정하지 않다.
solution
1. 주어진 위치에서 시작하는 압축 결과의 길이를 반환하는 함수를 만든다.
ex) s[0]이 x라고 할 때, 왼쪽위==s[1]이면 getChunkLength(s,1)이 해당 부분의 길이를 반환
     getChunkLength(s, 1)이 4를 반환한다고 할 때, 다음 조각은 s[5]부터 시작
2. s를 미리 쪼개는 것이 아닌 decompress()함수에서 '필요한 만큼 가져다 쓰도록' 한다.
  decompress() 함수에 s를 통째로 전달하는 것이 아닌, s의 한 글자를 가리키는 포인터를 전달한 후 함수 내에서 한 글자를 검사할 때마다 이 포인터를 앞으로 한 칸씩 옮긴다.
char decompressed[MAX_SIZE][MAX_SIZE];
void decompressed(string::iterator& it, int y, int x, int size) {
// 한 글자를 검사할 때마다 반복자를 한 칸 앞으로 옮긴다.
char head = *(it++);
// 기저 사례: 첫 글자가 b 또른 w인 경우
if (head == 'b' || head = 'w') {
for (int dy = 0; dy < size; ++dy)
for (int dx = 0; dx < size; ++dx)
decompressed[y + dy][x + dx] = head;
}
else {
// 네 부분을 순서대로 압축 해제
int half = size / 2;
decompressed(it, y, x, half);
decompressed(it, y, x + half, half);
decompressed(it, y + half, x, half);
decompressed(it, y + half, x + half, half);
}
}

압축 다 풀지 않고 뒤집기
string reverse(string::iterator& it) {
char head = *it;
++it;
if (head == 'b' || head == 'w')
return string(1, head);
string upperLeft = reverse(it);
string upperRight = reverse(it);
string lowerLeft = reverse(it);
string lowerRight = reverse(it);
// 각각 위와 아래 조각들의 위치를 바꾼다.
return string("x") + lowerLeft + lowerRight + upperLeft + upperRight;
}

울타리 잘라내기
분할 정복 알고리즘의 설계
가장 큰 직사각형을 왼쪽 부분 문제에서만  잘라낼 수 있다.
가장 큰 직사각형을 오른쪽 부분 문제에서만 잘라낼 수 있다.
가장 큰 직사각형은 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐 있다.

//각 판자의 높이를 저장하는 배열
vector<int> h;
// h[left..right] 구간에서 찾아낼 수 있는 가장 큰 사각형의 넓이를 반환한다.
int solve(int left, int right) {
//기저 사례:판자가 하나밖에 없는 경우
if (left == right) return h[left];
// [left, mid], [mid + 1, right]의 두 구간으로 문제를 분할한다.
int mid = (left + right) / 2;
// 분할한 문제를 각개격파
int ret = max(solve(left, mid), solve(mid + 1, right));
// 부분 문제 3: 두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는다.
int lo = mid, hi = mid + 1;
int height = min(h[lo], h[hi]);
// [mid, mid+1]만 포함하는 너비 2인 사각형을 고려
ret = max(ret, height * 2);
// 사각형이 입력 전체를 덮을 때까지 확장해 나간다.
while (left < lo || hi < right) {
//항상 높이가 더 높은 쪽으로 확장
if (hi < right && (lo == left || h[lo - 1] < h[hi + 1])) {
++hi;
height = min(height, h[hi]);
}
else {
--lo;
height = min(height, h[lo]);
}
// 확장한 후 사각형의 넓이
ret = max(ret, height * (hi - lo + 1));
}
return ret;
}

정당성
양쪽 부분 문제에 걸쳐있는 직사각형을 찾을 때, 각 단계마다 더 높은 판자를 택하는 것이 항상 옳다.
알고리즘에서는 너비가 2인 사각형에서 시작해서 한 칸씩 사각형의 너비를 늘려가므로,
우리가 고려한 사각형들 중 R과 너비가 같은 사각형(R')이 반드시 하나 있다.
너비가 같으면 높이가 높은 쪽이 크기가 크다.

팬미팅
int hugs(const string& members, const string& fans) {
int N = members.size(), M = fans.size();
vector<int> A(N), B(M);
for (int i = 0; i < N; i++) A[i] = (members[i] == 'M');
for (int i = 0; i < M; i++) B[M - 1 - i] = (fans[i] == 'M');
//karatsuba 알고리즘에서 자리 올림은 생략한다.
vector<int> C = karatsuba(A, B);
int allHugs = 0;
for (int i = N - 1; i < M; i++)
if (C[i] == 0)
++allHugs;
return allHugs;
}

알고리즘 문제 해결 전략(3)

무식하게 풀기 - 완전 탐색

재귀 호출과 완전 탐색
재귀 함수
자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고,
나머지를 자기 자신을 호출해 실행하는 함수
모든 재귀함수는 '더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 한다.
쪼개지지 않는 가장 작은 작업 == 기저 사례
for(int i = 0; i < n; ++i)
for(int j = i+1; j < n; ++j)
for(int k = j+1; k < n; ++k)
for(int l = k+1; l < n; ++l)
cout << i << " " << j << " " << k << " " << l << endl;

n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘
// n: 전체 원소의 수
// picked: 지금까지 고른 원소들의 번호
// toPick: 더 고를 원소의 수일때, 앞으로 toPick개의 원소를 고르는 모든 방법을 출력한다.
void pick(int n, vector<int>& picked, int toPick) {
//기저 사례: 더 고를 원소가 없을 때 고른 원소들을 출력한다.
if(toPick == 0) {printPicked(picked); return;}
//고를 수 있는 가장 작은 번호를 계산한다.
int smallest = picked.empty() ? 0 : picked.back() + 1;
//이 단계에서 원소하나를 고른다.
for(int next = smallest; next < n; ++next) {
picked.push_back(next);
pick(n, picked, toPick - 1);
picked.pop_back();
}
}

ex) 보글게임
상하좌우 / 대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것
hasWord(y, x, word) = 보들 게임판의 (y, x)에서 시작하는 단어 word의 존재 여부를 반환
문제의 분할
hasWord()가 하는 일을 가장 자연스럽게 조각내는 방법은 각 글자를 하나의 조각으로 만드는 것이다. 함수 호출시에 단어의 시작 위치를 정해 주기 때문에, 문제의 조각들 중 첫 번째 글자에 해당하는 조각을 간단하게 해결할 수 있다. 그 이후에는 시작위치와 인접한 여덟 칸을 모두 시도하면서 답을 찾으면 된다.
기저 사례의 선택
1. 위치 (y, x)에 잇는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패
2. (1번 경우에 해당하지 않을 경우)원하는 단어가 한글자인 경우 항상 성공
Tip: 입력이 잘못되거난 범위에서 벗어난 경우도 기저 사례로 택해서 맨 처음에 처리
const int dx[8] = {-1, -1, -1, 1, 1, 1, 0, 0};
const int dy[8] = {-1, 0, 1, -1, 0, 1, -1, 1};
//5X5의 보글 게임 판의 해당 위치에서 주어진 단어가 시작하는 지를 반환
bool hasWord(int y, int x, const string& word) {
// 기저 사례 1: 시작 위치가 범위 밖이면 무조건 실패
if(!inRange(y,x)) return false;
// 기저 사례 2: 첫 글자가 일치하지 않으면 실패
if(board[y][x] != word[0]) return false;
// 기저 사례 3: 단어 길이가 1이면 성공
if(word.size() == 1) return true;
// 인접한 여덟 칸을 검사한다.
for(int direction = 0; direction < 8; ++direction) {
int nextY = y + dy[direction], next = x + dx[direction];
//다음 칸이 범위 안에 있는지, 첫 글자는 일치하는지 확인할 필요가 없다.
if(hasWord(nextY, nextX, word.substr(1)))
return true;
}
return false;

}

완전 탐색 레시피
1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에
정확히 비례한다. 그러므로 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지를 가늠한다.
2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다.
3. 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성
4. 조각이 하나밖에 남지 않으 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 그섯을 기저 사례로 선택해 처리한다.

이론적 배경 : 재귀 호출과 부분 문제


문제 : 소풍 (문제 ID: PICNIC, 난이도: 하)
         int n;
bool areFriends[10][10];

    // 아직 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝짓는 경우의 수를      // 계산하라.
int countPairings(bool taken[10]) {
//기저 사례: i번째 학생이 짝을 이미 찾았으면 true, 아니면 false
bool finished = true;
for (int i = 0; i < n; i++) if (!taken[i]) finished = false;
if (finished) return 1;

int ret = 0;
// 서로 친구인 두 학생을 찾아 짝을 지어준다.
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (!taken[i] && !taken[j] && areFriends[i][j]) {
taken[i] = taken[j] = true;
ret += countPairings(taken);
taken[i] = taken[j] = false;
}
return ret;
}


int n;
bool areFriends[10][10];

// Wrong의 해결 방안: 각 단계에서 남아 있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아 주도록 하면 된다.
// 아직 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝짓는 경우의 수를 계산하라.
int countPairings(bool taken[10]) {
// 남은 학생들 중 가장 번호가 빠른 학생을 찾는다.
int firstFree = -1;
for (int i = 0; i < n; ++i) {
if (!taken[i]) {
firstFree = i;
break;
}
}
//기저사례: 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
int ret = 0;
// 서로 친구인 두 학생을 찾아 짝을 지어준다.
for (int pairWith = firstFree + 1; pairWith < n; ++pairWith) {
if (!taken[pairWith] && areFriends[firstFree][pairWith]) {
taken[firstFree] = taken[pairWith] = true;
ret += countPairings(taken);
taken[firstFree] = taken[pairWith] = false;
}
}
return ret;
}

#include <vector>
//주어진 칸을 덮을 수 있는 네가지 방법
//블록을 구성하는 세칸의 상대적 위치
const int coverType[4][3][2] = {
{{0,0},{1,0},{0,1}},
{{0,0},{0,1},{1,1}},
{{0,0},{1,0},{1,1}},
{{0,0},{1,0},{1,-1}}
};
//게임판 밖으로 나가거나, 겹치거나, 검은 칸을 덮을 때 false를 반환
bool set(vector<vector<int>>& board , int y, int x, int type, int delta) {
bool ok = true;
for (int i = 0; i < 3; ++i) {
const ny = y + coverType[type][i][0];
const nx = x + coverType[type][i][1];
if (x < 0 || ny > board.size() || y < 0 || nx > board[0].size())
ok = false;
}

return ok;
}
//board의 모든 빈 칸을 덮을 수 있는 방법의 수를 반환한다.
//board[i][j] = 1 이미 덮인 칸 혹은 검은 칸
//board[i][j] = 0 아직 덮이지 않은 칸
int cover(vector<vector<int>>& board) {
//아직 채우지 못한 칸 중 가장 윗줄 왼쪽에 있는 칸을 찾는다.
int y = -1, x = -1;
for (int i = 0; i < board.size; ++i) {
for (int j = 0; j < board[i].size(); ++j) {
if (board[i][j] == 0)
y = i;
x = j;
break;
}
if (y != -1) break;
}
}
//기저 사례: 모든 칸을 채웠으면 1을 반환한다.
if (y == -1) return 1;
int ret = 0;
for (int type = 0; type < 4; ++type) {
//만약 board[i][j]를 type형태로 덮을 수 있으면 재귀 호출한다.
if (set(board, y, x, type, 1))
ret += cover(board);
//덮었던 블록을 치운다.
set(board, y, x, type, -1);
}
return ret;
}

최적화 문제
문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은' 답을 찾아내는 문제 -- n개의 사과 중에서 r개를 골라서 무게의 합을 최대화하는 문제
최적화 문제를 해결하는 방법:
동적계획법, 조합 탐색, 최적화 문제를 결정 문제로 바꿔 해결하는 기법


int n; // 도시의 수
double dist[MAX][MAX]; // 두 도시 간의 거리를 저장하는 배열
//path: 지금까지 만든 경로
//visited: 각 도시의 방문 여부
//currentLength: 지금까지 경로의 길이
//나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.
double shortestPath(vector<int>& path, vector<bool>& visited, double currentLength) {
//기저 사례: 모든 도시를 다 방문했을 때는 시작 도시로 돌아가고 종료한다.
if (path.size() == n)
return currentLength + dist[path[0]][path.back()];
double ret = INF; // 매우 큰 값으로 초기화
// 다음 방문할 도시를 전부 시도해 본다.
for (int next = 0; next < n; ++next) {
if (visited[next]) continue;
int here = path.next();
path.push_back();
path.push_back(next);
visited[next] = true;
//나머지 경로를 재귀 호출을 통해 완성하고 가장 짧은 경로의 길이를 얻는다.
double cand = shortestPath(path, visited, currentLength + dist[here][next]);
ret = min(ret, cand);
visited[next] = false;
path.pop_back();
}
return ret;
}

const int INF = 9999, SWITCHES = 10, CLOCKS = 16;
//linked[i][j] = 'x': i번 스위치와 j번 시계가 연결되어 있다.
//linked[i][j] = '.': i번 스위치와 j번 시계가 연결되어 있지 않다.
const char linked[SWITCHES][CLOCKS + 1] = {
"xxx............",
"...x...x.x.x...",
"....x.....x...xx",
"x...xxxx........",
"......xxx.x.x...",
"x.x...........xx",
"...x..........xx",
".xxxxx..........",
"...xxx...x...x.."
};
//모든 시계가 12시를 가리키고 있는지 확인한다.
bool areAligned(const vector<int>& clocks);
//swtch번 스위치를 누른다.
void push(vector<int>& clocks, int swtch) {
for (int clock = 0; clock < CLOCKS; ++clock)
if (linked[swtch][clock] == 'x') {
clocks[clock] += 3;
if (clocks[clock] == 15) clocks[clock] = 3;
}
}
//clocks: 현재 시계들의 상태
//swtch: 이번에 누를 스위치의 번호가 주어질 때, 남은 스위치들을 눌러서 clocks를 12시로 맞출 수 있는 최소 횟수를 반환한다.
//만약 불가능하다면 INF 이상의 큰 수를 반환한다.
int solve(vector<int>& clocks, int swtch) {
if (swtch == SWITCHES) return areAligned(clocks) ? 0 : INF;
//이 스위치를 0번 누르는 경우부터 세 번 누르는 경우까지를 모두 시도한다.
int ret = INF;
for (int cnt = 0; cnt < 4; ++cnt) {
ret = min(ret, cnt + solve(clocks, swtch + 1));
push(clocks, swtch);
}
//push(clocks, swtch)가 네 번 호출되었으니 clocks는 원래와 같은 상태가 된다.
return ret;

}

알고리즘 문제 해결 전략(2)

선형 시간 알고리즘
다이어트 현황 파악: 이동 평균 계산하기
//실수 배열 A가 주어질 때, 각 위치에서의 M-이동 평균 값을 구한다.
vector<double> movingAverage1(const vector<double>& A, int M) {
vector<double> ret;
int N = A.size();
for(int i = M-1; i < N; ++i) {
//A[i]까지의 이동 평균값을 구하자.
double partialSum = 0;
for(int j = 0; j < M; ++j)
partialSum += A[i-j];
ret.push_back(partialSum / M);
               //push_back: vector의 메소드로 마지막에 원소 추가
}
return ret;
}

//길이가 N인 실수 배열 A가 주어질 때, 각 위치에서의 M-이동 평균값을 구한다.
vector<double> movingAverage2(const vector<double>& A, int M) {
vector<double> ret;
int N = A.size();
double partialSum = 0;
for(int i = 0; i < M - 1; ++i)
partialSum += A[i];
for(int i = M-1; i < N; ++i) {
partialSum += A[i];
ret.push_back(partialSum / M);
partialSum -= A[i-M+1];
}
return ret;
}

선형 이하 시간 알고리즘 - 이진 탐색
입력의 크기가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘들을 선형 이하 시간 알고리즘이라 부른다.

 지수 시간 알고리즘 - 다항 시간 알고리즘 - 재귀 함수
음식 메뉴 정하기
const int INF = 987654321;
// 이 메뉴로 모두가 식사할 수 있는지 여부를 반환한다.
bool canEverybodyEat(const vector<int>& menu);
// 요리할 수 있는 음식의 종류 수
int M;
//food번째 음식을 만들지 여부를 결정한다.
int selectMenu(vector<int>& menu, int food) {
//기저 사례:모든 음식에 대해 만들지 여부를 결정했을 때
if(food == M) {
if(canEverybodyEat(menu)) return menu.size();
//아무것도 못 먹는 사람이 있으면 아주 큰 값을 반환한다.
return INF;
}
//이 음식을 만들지 않는 경우의 값을 계산한다.
int ret = selectMenu(menu, food+1);
//이 음식을 만드는 경우의 답을 계산해서 더 작은 것을 취한다.
menu.push_back(food);
ret = min(ret, selctMenu(menu, food+1));
menu.pop_back();
return ret;
}

지수 시간 알고리즘

소인수 분해의 수행 시간
//자연수 n의 소인수 분해 결과를 담은 정수 배열을 반환한다.
vector<int> factor(int n) {
if(n == 1) return vector<int>(1, 1); // n = 1인 경우는 예외로 한다.
vector<int> ret;
for(int div = 2; n > 1; ++div)
while(n % div == 0) {
n /= div;
ret.push_back(div);
}
return ret;
}

void selectionSort(vector<int>& A) {
for(int i = 0; i < A.size(); ++i) {
int minIndex = i;
for(int j = i+1;  j < A.size(); ++j)
if(A[minIndex] > A[j])
minIndex = j;
swap(A[i], A[minIndex]);
}
}

void insertionSort(vector<int> A) {
for(int i = 0; i < A.size(); ++i) {
 // A[0..i-1]에 A[i]를 끼워넣는다.
 int j = i;
 while(j > 0 && A[j-1] > A[j]) {
 swap(A[j-1], A[j]);
 --j;
 }
}
}

const int MIN = numeric_limits<int>::min();
//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(N^3)
int inefficientMaxSum(const vector<int>& A) {
int N = A.size(), ret = MIN;
for(int i = 0; i < N; i++)
for(int j = i; j < N; ++j) {
//구간 A[i, j]의 합을 구한다.
int sum = 0;
for(int k = i; k <= j; ++k)
sum += A[k];
ret = max(ret, sum);
}
return ret;
}


//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(N^2)
int betterMaxSum(const vector<int>& A) {
int N = A.size(), ret = MIN;
for(int i = 0; i < N; ++i) {
int sum = 0;
for(int j = i; j < N; ++j) {
//구간 A[i, j]의 합을 구한다.
sum += A[j];
ret = max(ret, sum);
}
}
return ret;
}

//A[lo, hi]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(nlogn)
int fastMaxSum(const vector<int>& A, int lo, int hi) {
//기저 사례: 구간의 길이가 1일 경우
if(lo == hi) return A[lo];
//배열을 A[lo, mid], A[mid+1, hi]의 두 조각으로 나눈다.
int mid = (lo, hi) / 2;
//두 부분에 모두 걸쳐있는 최대 합 구간을 찾는다.
//이 구간은 A[i, mid], A[mid+1, j] 형태를 갖는 구간의 합으로 이루어진다.
//A[i, mid] 형태를 갖는 최대 구간을 찾는다.
int left = MIN, right = MIN, sum = 0;
for(int i = mid, i >= lo; --i){
sum += A[i];
left = max(left, sum);
}
//A[mid+1, j] 형태를 갖는 최대 구간을 찾는다.
sum = 0;
for(int j = mid+1; j <= hi; ++j) {
 sum += A[j];
 right = max(right, sum);
}
//최대 구간이 두 조각 중 하나에만 속해 있는 경우의 답을 재귀 호출로 찾는다.
int single = max(fastMaxSum(A, lo, mid), fastMaxSum(A, mid+1, hi));
//두 경우 중 최대치를 반환한다.
return max(left + right, single);
}

//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(N)
int fastestMaxSum(const vector<int>& A) {
int N = A.size(), ret = MIN, psum = 0;
for(int i = 0; i < N; ++i) {
psum = max(psum, 0) + A[i];
ret = max(psum, ret);
}
return ret;

}

계산 복잡도 클래스: P, NP, NP-완비
P : 다항 시간 내에 풀 수 있는 문제
NP : 다한 시간 내에 풀 수 없는 문제

알고리즘의 정당성 증명 - 수학적으로 증명
수학적 귀납법
단계 나누기 : 증명하고 싶은 사실을 여러 단계로 나눈다.
첫 단계 증명 : 첫 단계에서 증명하고 싶은 내용이 성립한다.
귀납 증명 : 한 단계에서 증명하고 싶은 내용이 성립한다면 다음 단계에서도 성립함을 보임

반복문 불변식
//(*) 불변식은 여기에서 성립해야 한다.
while(condition) {
    //반복문 내용의 시작
    ..
    //반복문 내용의 끝
    //(**) 불변식은 여기에서도 성립해야 한다.
}

이진 탐색과 반복문 불변식
// 필수 조건: A는 오름차순으로 정렬되어 있다.
// 결과: A[i-1] < x <= A[i]인 i를 반환한다.
// 이때 A[-1] = 음의 무한대, A[n] = 양의 무한대라고 가정한다.
int binsearch(const vector<int>& A, int x) {
int n = A.size();
int lo = -1, hi = n;
//반복문 불변식 1: lo < hidden
//반복문 불변식 2: A[lo] < x < A[hi]
//(*) 불변식은 여기서 성립해야 한다.
while(lo + 1 < hi) {
int mid = (lo + hi) / 2;
if(A[mid] < x)
lo = mid;
else
hi = mid;
//(**) 불변식은 여기서 성립해야 한다.
}
}

삽입 정렬과 반복문 불변식
void insertionSort(vector<int> A) {
for(int i = 0; i < A.size(); ++i) {
// 불변식 a:A[0..i-1]은 이미 정렬되어 있다.
  // A[0..i-1]에 A[i]를 끼워넣는다.
  int j = i;
  while(j > 0 && A[j-1] > A[j]) {
   // 불변식 b: A[j + 1 .. i]의 모든 원소는 A[j]보다 크다.
   // 불변식 c: A[0 .. i]  구간은 A[j]를 제외하면 정렬되어 있다.
  swap(A[j-1], A[j]);
  --j;
  }
}
}

귀류법
내가 원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못됐음을 찾아내는 증명 기법

비둘기집의 원리

동전 뒤집기

순환 소수 찾기

구성적 증명

안정적 결혼 문제