• 운송장 확인 → 택배 프로세스 시작
  • 촬영 완료되었습니다.
  • 일치하는 사원을 찾을 수 없습니다.
• 목표 장소 출발/도착
  • %s 님께 출발하겠습니다
  • %s 님, 도착했습니다
• 얼굴인식
  • 화면을 정면으로 응시해주세요
  • %s 님과 일치하지 않습니다 : 3초 이상 no match 발생 시
  • 인증되었습니다 : 3초 이상 true
    • 물품을 수거해주세요
    • 저에게 물품을 주세요~

TTS publisher / subscriber

1. first_tts_pkg 생성
2. tts_publisher.py, tts_subscriber.py 생성
   1. publisher
      • spin_once 로 콜백함수를 한번만 실행시킴

        import rclpy
        from rclpy.node import Node
        from rclpy.qos import QoSProfile # 퍼블리셔의 QoS 설정
        from std_msgs.msg import String # 퍼블리시 메시지 타입

        class TTS_Publisher(Node): # Node 클래스 상속

            def __init__(self):
                super().__init__('TTS_Publisher') # 노드 이름 지정
                qos_profile = QoSProfile(depth=10) # 퍼블리시할 데이터를 버퍼에 10개까지 저장
                self.tts_publisher = self.create_publisher(String, 'tts_message', qos_profile)
                self.timer = self.create_timer(1, self.publish_msg) # 콜백함수 : n초마다 지정한 콜백함수 실행
                self.count = 0

            def publish_msg(self):
                msg = String() # 퍼블리시할 메시지
                msg.data = '송민영'.format(self.count) # 메시지 저장
                self.tts_publisher.publish(msg) # 메시지 퍼블리시
                self.get_logger().info('Published message: {0}'.format(msg.data)) # 콘솔창에 출력 (==print함수)

        def main(args=None):
            rclpy.init(args=args) # 초기화
            node = TTS_Publisher()
            try:
                node.get_logger().info("spin될까?")
                rclpy.spin_once(node) # 콜백함수 실행
                node.get_logger().info("spin된다!!")

            except KeyboardInterrupt: # 'Ctrl+c'와 같은 인터럽트 시그널 예외 상황
                node.get_logger().info('Keyboard Interrupt (SIGINT)')
            finally:
                node.destroy_node() # 노드 소멸
                rclpy.shutdown() # 함수 종료

        if __name__ == '__main__':
            main()

2. subscriber
   • TTS 모듈 가져오기
   • msg.data 값으로 메시지 받기

        import rclpy
        from rclpy.node import Node
        from rclpy.qos import QoSProfile
        from std_msgs.msg import String

        class TTS_Subscriber(Node):

            def __init__(self):
                super().__init__('TTS_Subscriber') # Node 클래스 생성자 호출
                qos_profile = QoSProfile(depth=10) # 서브스크라이브 데이터를 버퍼에 10개까지 저장
                self.tts_subscriber = self.create_subscription(
                    String, # 토픽 메시지 타입
                    'tts_message', # 토픽 이름
                    self.subscribe_topic_message, # 콜백 함수
                    qos_profile) # QoS 설정

            def subscribe_topic_message(self, msg) :
                msg_to_tts(msg.data)

        def msg_to_tts(msg):

            import os
            import sys
            import urllib.request
            import time
            # import playsound

            client_id = "###" # API id
            client_secret = "###" # API PW 

            msg = msg # msg 받을 경우
            encText = urllib.parse.quote("%s에게 물품을 주세요"%(msg))

            data = "speaker=nara&volume=0&speed=0&pitch=0&format=mp3&text=" + encText;
            url = "https://naveropenapi.apigw.ntruss.com/tts-premium/v1/tts"

            request = urllib.request.Request(url)
            request.add_header("X-NCP-APIGW-API-KEY-ID",client_id)
            request.add_header("X-NCP-APIGW-API-KEY",client_secret)

            response = urllib.request.urlopen(request, data=data.encode('utf-8'))
            rescode = response.getcode()

            if response.getcode()==200:
                print("CSS 성공! 파일을 저장합니다.")
                response_body = response.read()
                file_name = "음성파일"
                with open(file_name + ".mp3", 'wb') as f:
                    f.write(response_body)
                print("파일명:", file_name)
                # playsound.playsound(file_name+".mp3")
            else:
                print("Error Code:" + rescode)

        def main(args=None):
            rclpy.init(args=args)
            node = TTS_Subscriber()
            try:
                rclpy.spin(node)
            except KeyboardInterrupt:
                node.get_logger().info('Keyboard Interrupt (SIGINT)')
            finally:
                node.destroy_node()
                rclpy.shutdown()

        if __name__ == '__main__':
            main()

3. setup.py 파일의 entry_points 수정

    entry_points={
            'console_scripts': [
                'tts_publisher = first_tts_pkg.tts_publisher:main',
                'tts_subscriber = first_tts_pkg.tts_subscriber:main',
            ],
        },

4. terminal 창에서 실행

    $ ros2 run first_tts_pkg tts_publisher

    $ ros2 run first_tts_pkg tts_subscriber

운송장

( 내부 카메라 파이캠 촬영 → 사원DB 일치여부 확인) → 수신 → 스피커 송출

1. 파이캠으로 촬영해서 운송장 이미지 인식, 촬영

   • 로봇 디스플레이에 촬영 버튼 추가
     • 젯슨나노 (파이캠) ↔ 디스플레이 : OCR은 화면 연결 아예 X (그냥 화면 꺼지는걸로) TTS만 연동 가능. ⇒ 촬영 시작은 어떻게?
       • Face detection을 써야하는 이유 : 젯슨나노에서 Face detection이 안돌아감

2. 촬영 시 ocr_publisher.py 실행

   • rqt로 ‘촬영’ 신호 받으면 main에서 ocr_pub 또는 py 실행

3. publish

   ROS는 토픽 정보를 publish하면 같은 네트워크 상의 모든 노드에서 subscribe 할 수 있음. 토픽 이름만 맞추면 됨!

    # ocr_publisher.py

    # 전송할 메시지 설정
            if name : # 이름이 출력 되면
                self.message = name
            if name == "" : # 이름이 출력되지 않았다면
                self.message = "다시 촬영해주세요."

• 정보 추출 여부 (OCR이 수행 될 수 있는 이미지가 촬영되었는지)

   - 실패 시 ‘다시 촬영해주세요’
   - ⇒ **TTS**
       - OCR, 얼굴인식 등 각 기능의 토픽 메시지 이름을 다르게 설정해서 하나의 패키지에서 관련 정보를 모두 수신하도록 함.

  • 사원 존재 여부
    • 존재하지 않을 시 ‘존재하지 않는 사원입니다’
    • 기존 계획은 사원 DB와 비교하는 것이었지만 모두 존재한다고 가정 / 이름이 전달되는 수준으로 구현
  • 사원 정보
    • ⇒ 스크린 : name을 포함한 사원 정보 출력
      • String 말고 다른 형태의 메시지 전송하는법
    • ⇒ APP (수령인) : 수령인에게 알림 송출
    • ⇒ navigation

목표 장소 출발/도착

(SLAM → 도착 여부) 수신 → 스피커 송출

☆↗↗

얼굴인식

로봇 도착(navigation) → Face detection 일치 여부 결과 → 수신 → 스피커 송출 (배송완료) → 배송완료 사실 navigation으로 송출

• Face detection 일치 여부
  • navigaion으로부터 name 값 받음
  • 스크린(라즈베리안)쪽에서 수동으로 입력해서 젯슨나노로 보내줌
  • while 문 :
    • n초 이상 ‘Not match’
      • ⇒ TTS : ‘정면을 바라봐주세요.’
    • ‘Match’
      • ⇒ TTS : ‘%s님, 인증되었습니다.’
      • face_subscriber = 1이면 face_publisher.py 실행하며 끝

import rclpy
from rclpy.node import Node
from rclpy.qos import QoSProfile
from std_msgs.msg import String

class Face_result_Publish(Node):

    def __init__(self):
        super().__init__('face_result_publisher')
        qos_profile = QoSProfile(depth=10)
        self.face_result_publisher = self.create_publisher(String, 'face_result' ,qos_profile)
        self.timer = self.create_timer(1, self.publish_msg)
        self.count = 0 
    def publish_msg(self):
        msg = String()
        msg.data = "from rasberrian?"
        self.get_logger().info('Published message: {0}'.format(msg.data))
        self.count += 1

def main(args = None):
    rclpy.init(args=args) # 초기화 
    node = Face_result_Publish() 
    try:
        rclpy.spin(node) # 콜백함수 실행 
    except KeyboardInterrupt: # 'Ctrl+c'와 같은 인터럽트 시그널 예외 상황 
        node.get_logger().info('Keyboard Interrupt (SIGINT)')
    finally: 
        node.destroy_node() # 노드 소멸 
        rclpy.shutdown() # 함수 종료

if __name__ == '__main__':
    main()

패키지 설정 파일

• package.xml

<?xml version="1.0"?>
<?xml-model href="http://download.ros.org/schema/package_format3.xsd" schematypens="http://www.w3.org/2001/XMLSchema"?>
<package format="3">
  <name>topic_service_action_rclpy_example</name>
  <version>0.2.0</version>
  <description>ROS 2 rclpy example package for the topic, service, action</description>
  <maintainer email="passionvirus@gmail.com">Pyo</maintainer>
  <license>Apache License 2.0</license>
  <author email="passionvirus@gmail.com">Pyo</author>
  <author email="routiful@gmail.com">Darby Lim</author>
  <depend>rclpy</depend>
  <depend>std_msgs</depend>
  **<depend>msg_srv_action_interface_example</depend> # 해당 패키지 사용할 예정**
  <test_depend>ament_copyright</test_depend>
  <test_depend>ament_flake8</test_depend>
  <test_depend>ament_pep257</test_depend>
  <test_depend>python3-pytest</test_depend>
  <export>
    <build_type>ament_python</build_type>
  </export>
</package>

파이썬 패키지 설정 파일

• setup.py

#!/usr/bin/env python3

import glob
import os

from setuptools import find_packages
from setuptools import setup

package_name = 'topic_service_action_rclpy_example'
share_dir = 'share/' + package_name

setup(
    name=package_name,
    version='0.2.0',
    packages=find_packages(exclude=['test']),
    data_files=[ #패키지 사용 파일 기입 
        ('share/ament_index/resource_index/packages', ['resource/' + package_name]),
        (share_dir, ['package.xml']),
        (share_dir + '/launch', glob.glob(os.path.join('launch', '*.launch.py'))),
        (share_dir + '/param', glob.glob(os.path.join('param', '*.yaml'))),
    ],
    install_requires=['setuptools'],
    zip_safe=True,
    author='Pyo, Darby Lim',
    author_email='passionvirus@gmail.com, routiful@gmail.com',
    maintainer='Pyo',
    maintainer_email='passionvirus@gmail.com',
    keywords=['ROS'],
    classifiers=[
        'Intended Audience :: Developers',
        'License :: OSI Approved :: Apache Software License',
        'Programming Language :: Python',
        'Topic :: Software Development',
    ],
    description='ROS 2 rclpy example package for the topic, service, action',
    license='Apache License, Version 2.0',
    tests_require=['pytest'],
    entry_points={ # 콘솔 스크립트의 이름과 호출함수 기입. 
        'console_scripts': [
            'argument = topic_service_action_rclpy_example.arithmetic.argument:main',
            'operator = topic_service_action_rclpy_example.arithmetic.operator:main',
            'calculator = topic_service_action_rclpy_example.calculator.main:main',
            'checker = topic_service_action_rclpy_example.checker.main:main',
        ],
    },
)

소스코드 다운로드 및 빌드

$ cd ~/ros2_dashing/src
$ git clone https://github.com/robotpilot/ros2-seminar-examples.git
$ cd ~/ros2_dashing && colcon build --symlink-install

• colcon build 안됨 ㅠㅠ

ROS2 토픽, 서비스, 액션 인터페이스

인터페이스 기초

• 노드 간 데이터를 주고받을 때 사용되는 데이터의 형태
• IDL(interface definition language) : msg, srv, action 등
  • 단순 자료형 : 정수, boolean, ...
  • 메시지 안에 메시지 : geometry_msgs/msgs/Twist의 Vector3 linear
  • 배열 : sensor_msgs/msgs/LaserScan 의 float32[] ranges

단순 자료형

• 정의 방법

    fieldtype1 fieldname1

    fieldtype2 fieldname2

    fieldtype3 fieldname3

토픽 - 메시지

• turtlesim 패키지

  $ ros2 interface show geometry_msgs/msg/Twist
  $ ros2 interface show geometry_msgs/msg/Vector3

  

• geometry_msgs/msgs/Twist 메시지 = float64 자료형의 linear.x, linear.y, linear.z, angular.x, angular.y, angular.z

• ros2 interface [something]

  • show
  • list : 현재 개발 환경의 모든 msg, srv, action 메시지
  • package : msg, srv, action 인터페이스를 담고 있는 패키지의 목록
  • packages : 지정한 패키지에 포함된 인터페이스들
  • proto : 인터페이스의 기본 형태

$ ros2 interface proto geometry_msgs/msg/Twist

"linear:
  x: 0.0
  y: 0.0
  z: 0.0
angular:
  x: 0.0
  y: 0.0
  z: 0.0
"

서비스 인터페이스

• /spawn 서비스 예시

    $ ros2 interface show turtlesim/srv/Spawn.srv

    float32 x
    float32 y
    float32 theta
    string name
    ---
    string name

• ‘---’ 구분자 x, y, theta, name : 서비스 요청 (클라이언트 → 서버) ⇒ name (서버에서 서비스 수행 이후 → 클라이언트)

액션 인터페이스

• turtlesim 예시

  /turtle1/rotate_absolute 액션에 사용된 RotateAbsolute.action 인터페이스

    $ ros2 interface show turtlesim/action/RotateAbsolute.action

    float32 theta # 목표
    ---
    float32 delta # 결과
    ---
    float32 remaining # 피드백 

• ‘—-’ 구분자
  액션 목표(goal)), 액션 결과(result), 액션 피드백(feedback)을 구분 x, y, theta, name : 서비스 요청 (클라이언트 → 서버) ⇒ name (서버에서 서비스 수행 이후 → 클라이언트)

인터페이스

• 인터페이스으로만 구성된 패키지를 별도로 만들어 사용해야 의존성면에서 관리하기 편함

인터페이스 패키지 생성

• 패키지 이름 : msg_srv_action_interface_example

    $ cd ~/robot_ws/src
    $ ros2 pkg create --build-type ament_cmake msg_srv_action_interface_example
    $ cd msg_srv_action_interface_example
    $ mkdir msg srv action 

• msg 인터페이스

  ArithmeticArgument.msg

  • 텍스트 파일 생성하기 : touch [파일명].[확장자]
    • gedit 으로 파일 수정

        # Messages
        builtin_interfaces/Time stamp
        float32 argument_a
        float32 argument_b

• msg : 메시지 파일은 ROS 메시지의 영역에 대해 기술한 단순한 텍스트 파일입니다. 이 파일은 다양한 언어의 소스코드에서 사용하는 메시지를 만드는 데 사용됩니다.

  • srv 인터페이스

    ArithmeticOperator.srv

         # Constants
        int8 PLUS = 1
        int8 MINUS = 2
        int8 MULTIPLY = 3
        int8 DIVISION = 4

        # Request
        int8 arithmetic_operator
        ---
        # Response
        float32 arithmetic_result

• action 인터페이스

  ArithmeticChecker.action

        # Constants
        int8 PLUS = 1
        int8 MINUS = 2
        int8 MULTIPLY = 3
        int8 DIVISION = 4

        # Request
        int8 arithmetic_operator
        ---
        # Response
        float32 arithmetic_result

패키지 설정 파일

패키지 설정 파일(package.xml) 작성 / 수정

<?xml version="1.0"?>
<?xml-model href="http://download.ros.org/schema/package_format3.xsd" schematypens="http://www.w3.org/2001/XMLSchema"?>
<package format="3">
  <name>msg_srv_action_interface_example</name>
  <version>0.2.0</version>
  <description>
    ROS 2 example for message, service and action interface
  </description>
  <maintainer email="passionvirus@gmail.com">Pyo</maintainer>
  <license>Apache 2.0</license>
  <author email="passionvirus@gmail.com">Pyo</author>
  <author email="routiful@gmail.com">Darby Lim</author>
  <buildtool_depend>ament_cmake</buildtool_depend>
  **<buildtool_depend>rosidl_default_generators</buildtool_depend> # 인터페이스 전용 패키지에서 필수적인 의존성 패키지
  <exec_depend>builtin_interfaces</exec_depend>
  <exec_depend>rosidl_default_runtime</exec_depend>**
  <member_of_group>rosidl_interface_packages</member_of_group>
  <export>
    <build_type>ament_cmake</build_type>
  </export>
</package>

빌드 설정 파일

빌드 설정 파일(CMakeLists.txt) 작성/수정

• set 명령어로 msg, srv, action 파일을 지정해주고 rosidl_generate_interfaces에 해당 셋들을 기입

################################################################################
# Set minimum required version of cmake, project name and compile options
################################################################################
cmake_minimum_required(VERSION 3.5)
project(msg_srv_action_interface_example)

if(NOT CMAKE_CXX_STANDARD)
  set(CMAKE_CXX_STANDARD 14)
endif()

if(CMAKE_COMPILER_IS_GNUCXX OR CMAKE_CXX_COMPILER_ID MATCHES "Clang")
  set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wall -Wextra -Wpedantic")
endif()

################################################################################
# Find and load build settings from external packages
################################################################################
find_package(ament_cmake REQUIRED)
find_package(builtin_interfaces REQUIRED)
find_package(rosidl_default_generators REQUIRED)

################################################################################
# Declare ROS messages, services and actions
################################################################################
**set(msg_files
  "msg/ArithmeticArgument.msg"
)

set(srv_files
  "srv/ArithmeticOperator.srv"
)

set(action_files
  "action/ArithmeticChecker.action"
)

rosidl_generate_interfaces(${PROJECT_NAME}
  ${msg_files}
  ${srv_files}
  ${action_files}
  DEPENDENCIES builtin_interfaces
)**

################################################################################
# Macro for ament package
################################################################################
ament_export_dependencies(rosidl_default_runtime)
ament_package()

빌드

$ cd ~/ros2_bashing
$ colcon build --symlink-install --packages-select msg_srv_action_interface_example

• 구조

~/ros2_bashing/install/msg_srv_action_interface_example
├── include
│   └── msg_srv_action_interface_example
│       ├── action
│       ├── msg
│       └── srv
├── lib
│   └── python3.6
│       └── site-packages
│           └── msg_srv_action_interface_example
│               ├── action
│               ├── msg
│               └── srv
└── share
    └── msg_srv_action_interface_example
        ├── action
        ├── msg
        └── srv

rclpy로 파이썬을 활용하여 Topic, Publisher, Subscriber 작성하기

1. 패키지 생성

사용자 작업 폴더에 패키지를 생성한다.

$ ros2 pkg create [패키지이름] --build-type [빌드 타입] --dependencies [의존하는패키지1] [의존하는패키지n]

$ cd ~/ros2_dashing/src/
$ ros2 pkg create my_first_ros_rclpy_pkg --build-type ament_python --dependencies rclpy std_msgs

옵션

• rclpy : ROS에서 파이썬을 사용하기 위한 클라이언트 라이브러리
• std_msgs : 표준 메시지 패키지

해당 패키지 생성에 앞서 미리 설치해야 하는 의존 패키지들. 패키지 생성 시 위와 같이 지정할 수도 있지만, 생성한 다음 package.xml에서 직접 입력해도 된다.

생성 후 결과

• 패키지 기본 구조

.
├── my_first_ros_rclpy_pkg
│   └── __init__.py
├── resource
│   └── my_first_ros_rclpy_pkg
├── test
│   ├── test_copyright.py
│   ├── test_flake8.py
│   └── test_pep257.py
├── package.xml
├── setup.cfg
└── setup.py

3 directories, 8 files

ament_cmake 인지, ament_python 인지에 따라 구성 파일 시스템이 달라짐.

package.xml, setup.cfg, setup.py는 패키지 생성 시 자동으로 생성된다.

2. 패키지 설정

package.xml

패키지 설정 파일. 사용할 RCL (ROS2 Client Libraries)에 따라 달라짐.

• C++ → ament_cmake
• python → ament_python

<?xml version="1.0"?>
<?xml-model href="http://download.ros.org/schema/package_format3.xsd" schematypens="http://www.w3.org/2001/XMLSchema"?>
<package format="3">
  <name>my_first_ros_rclpy_pkg</name>
  <version>0.0.2</version>
  <description>ROS 2 rclpy basic package for the ROS 2 seminar</description>
  <maintainer email="pyo@robotis.com">Pyo</maintainer>
  <license>Apache License 2.0</license>
  <author email="mikael@osrfoundation.org">Mikael Arguedas</author>
  <author email="pyo@robotis.com">Pyo</author>

  <depend>rclpy</depend>
  <depend>std_msgs</depend>

  <test_depend>ament_copyright</test_depend>
  <test_depend>ament_flake8</test_depend>
  <test_depend>ament_pep257</test_depend>
  <test_depend>python3-pytest</test_depend>

  <export>
    <build_type>ament_python</build_type>
  </export>
</package>

setup.py

파이썬 패키지 설정 파일.

entry_points 옵션의 console_scripts 키를 사용한 실행 파일 설정함. (각각의 콘솔 스크립트는 각 모듈의 main 함수를 호출함.)

• helloworld_publisher → my_first_ros_rclpy_pkg.helloworld_publisher
• helloworld_subscriber → my_first_ros_rclpy_pkg.helloworld_subscriber

from setuptools import find_packages
from setuptools import setup

package_name = 'my_first_ros_rclpy_pkg'

setup(
    name=package_name,
    version='0.0.2',
    packages=find_packages(exclude=['test']),
    data_files=[
        ('share/ament_index/resource_index/packages',
            ['resource/' + package_name]),
        ('share/' + package_name, ['package.xml']),
    ],
    install_requires=['setuptools'],
    zip_safe=True,
    author='Mikael Arguedas, Pyo',
    author_email='mikael@osrfoundation.org, pyo@robotis.com',
    maintainer='Pyo',
    maintainer_email='pyo@robotis.com',
    keywords=['ROS'],
    classifiers=[
        'Intended Audience :: Developers',
        'License :: OSI Approved :: Apache Software License',
        'Programming Language :: Python',
        'Topic :: Software Development',
    ],
    description='ROS 2 rclpy basic package for the ROS 2 seminar',
    license='Apache License, Version 2.0',
    tests_require=['pytest'],
    entry_points={
        'console_scripts': [
            'helloworld_publisher = my_first_ros_rclpy_pkg.helloworld_publisher:main',
            'helloworld_subscriber = my_first_ros_rclpy_pkg.helloworld_subscriber:main',
        ],
    },
)

setup.cfg

• 패키지 이름을 기재해야함
• /home/[user]/ros2_dashing/install/my_first_ros_rclpy_pkg/lib/my_first_ros_rclpy_pkg 와 같은 지정 폴더에 실행 파일이 생성됨

[develop]
script-dir=$base/lib/my_first_ros_rclpy_pkg
[install]
install-scripts=$base/lib/my_first_ros_rclpy_pkg

3. 퍼블리셔 노드 작성

• 파일 위치 : ~/ros2_dashing/src/my_first_ros_rclpy_pkg/my_first_ros_rclpy_pkg/
• 파일명 : helloworld_publisher.py

import rclpy
from rclpy.node import Node
from rclpy.qos import QoSProfile # 퍼블리셔의 QoS 설정 
from std_msgs.msg import String # 퍼블리시 메시지 타입 

class HelloworldPublisher(Node): # Node 클래스 상속

    def __init__(self):
        super().__init__('helloworld_publisher') # 노드 이름 지정 
        qos_profile = QoSProfile(depth=10) # 퍼블리시할 데이터를 버퍼에 10개까지 저장
        self.helloworld_publisher = self.create_publisher(String, 'helloworld', qos_profile)
                # 퍼블리셔 설정 : 토픽 메시지 타입, 이름, QoS 설정 
        self.timer = self.create_timer(1, self.publish_helloworld_msg)
                # 콜백함수 : n초마다 지정한 콜백함수 실행 
        self.count = 0

    def publish_helloworld_msg(self): 
        msg = String() # 퍼블리시할 메시지 
        msg.data = 'Hello World: {0}'.format(self.count) # 메시지 저장 
        self.helloworld_publisher.publish(msg) # 메시지 퍼블리시
        self.get_logger().info('Published message: {0}'.format(msg.data)) # 콘솔창에 출력 (==print함수) 
        # logger 종류 : debug, info, warning, error, fatal
                self.count += 1

def main(args=None):
    rclpy.init(args=args) # 초기화 
    node = HelloworldPublisher() 
    try:
        rclpy.spin(node) # 콜백함수 실행 
    except KeyboardInterrupt: # 'Ctrl+c'와 같은 인터럽트 시그널 예외 상황 
        node.get_logger().info('Keyboard Interrupt (SIGINT)')
    finally: 
        node.destroy_node() # 노드 소멸 
        rclpy.shutdown() # 함수 종료

if __name__ == '__main__':
    main()

• 콜백 함수
  1. 다른 함수의 인자로써 이용되는 함수
  2. 어떤 이벤트에 의해 호출되어지는 함수

4. 서브스크라이버 노드 생성

• 파일 위치 : ~/ros2_dashing/src/my_first_ros_rclpy_pkg/my_first_ros_rclpy_pkg/
• 파일명 : helloworld_subscriber.py

import rclpy
from rclpy.node import Node
from rclpy.qos import QoSProfile
from std_msgs.msg import String

class HelloworldSubscriber(Node):

    def __init__(self):
        super().__init__('Helloworld_subscriber') # Node 클래스 생성자 호출
        qos_profile = QoSProfile(depth=10) # 서브스크라이브 데이터를 버퍼에 10개까지 저장
        self.helloworld_subscriber = self.create_subscription(
            String, # 토픽 메시지 타입
            'helloworld', # 토픽 이름
            self.subscribe_topic_message, # 콜백함수 
            qos_profile) # QoS 설정 
                # 받은 메시지는 msg.data에 저장

    def subscribe_topic_message(self, msg):
        self.get_logger().info('Received message: {0}'.format(msg.data))

def main(args=None):
    rclpy.init(args=args)
    node = HelloworldSubscriber()
    try:
        rclpy.spin(node)
    except KeyboardInterrupt:
        node.get_logger().info('Keyboard Interrupt (SIGINT)')
    finally:
        node.destroy_node()
        rclpy.shutdown()

if __name__ == '__main__':
    main()

5. 빌드

• colcon 사용

  소스 코드가 있는 workspace로 이동 → colcon build 명령어로 전체를 빌드

(워크스페이스내의 모든 패키지 빌드하는 방법) 
$ cd ~/robot_ws && colcon build --symlink-install

(특정 패키지만 빌드하는 방법)
$ cd ~/robot_ws && colcon build --symlink-install --packages-select [패키지 이름1] [패키지 이름2] [패키지 이름N]

(특정 패키지 및 의존성 패키지를 함께 빌드하는 방법)
$ cd ~/robot_ws && colcon build --symlink-install --packages-up-to [패키지 이름]

• 튜토리얼 코드 빌드 예시

$ cd ~/robot_ws
$ colcon build --symlink-install --packages-select my_first_ros_rclpy_pkg

Starting >>> my_first_ros_rclpy_pkg
Finished <<< my_first_ros_rclpy_pkg [0.66s]

Summary: 1 package finished [0.87s]

• 첫 빌드 때에는 환경 설정 파일을 불러와서 실행 가능한 패키지의 노드 설정들을 해줘야함.

. ~/robot_ws/install/local_setup.bash

6. 실행

각 터미널 창에서 아래 코드 실행

$ ros2 run my_first_ros_rclpy_pkg helloworld_subscriber

$ ros2 run my_first_ros_rclpy_pkg helloworld_publisher

$ ros2 pkg list

$ ros2 pkg executables <패키지명>

$ ros2 run <패키지명> <노드명> 

$ ros2 node list

$ ros2 topic list

$ ros2 service list

$ rqt_graph

• 노드 정보 지정된 노드의 Publishers, Subscriber, Service, Aaction, Parameter 정보를 확인할 수 있다

$ ros2 node info /<노드명>

CLI 명령어

ros2 [verbs] [sub-verbs] [options] [arguments]

• launch
  • 특정 패키지의 특정 런치파일 실행
    • 런치 파일 : 실행해야하는 노드, 파라미터 등을 정의함. ROS1에서는 XML문서로 구성되어 있음.
• run
  • 특정 패키지의 특정 노드 실행

• action
• bag
• component
• daemon
• doctor
• extension_points
• extensions
• interface
• lifecycle
• multicast
• node
• param
• pkg
• security
• service
• topic
• wtf

정보 명령어

기능 보조 명령어

파일시스템

설치 방법

바이너리 설치

ex. $ sudo apt install ros-foxy-teleop-twist-joy

패키지 명으로만으로 설치 가능. 설치된 파일은 /opt/ros/foxy 에 저장되어 ros2 run 이나 ros2 launch로 해당 패키지내의 실행 가능한 노드를 실행시킬 수 있다.

소스코드 설치

ex.

```$ cd ~/robot_ws/src $ git clone https://github.com/ros2/teleop_twist_joy.git $ cd ~/robot_ws/ $ colcon build --symlink-install --packages-select teleop_twist_joy

패키지를 수정하여 사용하고자 할 경우나 소스 코드 내용을 확인할 필요가 있을 때 

### 설치 폴더
#### 기본 설치 폴더
'/opt/ros/[버전이름]' 폴더에 설치
ROS를 설치할 때 선택했던 패키지와 ROS 구동 프로그램이 포함됨 

▪ /bin :  실행 가능한 바이너리 파일
▪ /cmake : 빌드 설정 파일
▪ /include : 헤더 파일
▪ /lib : 라이브러리 파일
▪ /opt : 기타 의존 패키지
▪ /share : 패키지의 빌드, 환경 설정 파일
▪ local_setup.* : 환경 설정 파일
▪ setup.* : 환경 설정 파일

#### 사용자 작업 폴더 
사용자가 원하는 곳에 생성할 수 있음.
사용자가 작성한 패키지와 공개된 다른 개발자의 패키지를 저장하고 빌드하는 공간

▪ /build : 빌드 설정 파일용 폴더
▪ /install msg, srv : 헤더 파일과 사용자 패키지 라이브러리, 실행 파일용 폴더
▪ /log : 빌드 로깅 파일용 폴더
▪ /src : 사용자 패키지용 폴더

- /src 내부 
▪ /src C/C++ 코드용 폴더
▪ /include C/C++ 헤더 파일용 폴더 (폴더 안에는 각 패키지 이름별 폴더로 패키지별 헤더를 구분함)
▪ /param 파라미터 파일용 폴더
▪ /launch roslaunch에 사용되는 launch 파일용 폴더
▪ /패키지_이름_폴더 Python 코드용 폴더
▪ /test 테스트 코드 및 테스트 데이터용 폴더
▪ /msg 메시지 파일용 폴더
▪ /srv 서비스 파일용 폴더
▪ /action 액션 파일용 폴더
▪ /doc 문서용 폴더
▪ package.xml: 패키지 설정 파일 (REP-0140, REP-0149 참고)
▪ CMakeLists.txt: C/C++ 빌드 설정 파일
▪ setup.py: 파이썬 코드 환결 설정 파일
▪ README: 사용자 문서, github 리포지토리의 메인에 표시된다.
▪ CONTRIBUTING: 해당 패키지 개발에 공헌하는 방법을 기술하는 파일
▪ LICENSE: 이 패키지의 라이선스를 기술하는 파일
▪ CHANGELOG.rst: 이 패키지의 버전별 변경 사항 모음 파일 (REP-0132 참고)

## 빌드  

### 빌드 시스템 
: 단일 패키지 대상 (낮은 레벨, 의존성 낮음)

- ROS 1 (ROS Fuerte 까지): rosbuild (CMake)
- ROS 1 (ROS Groovy 이후): catkin (CMake)
- ROS 2: ament (CMake), Python setuptools (Full support)
  - ament_cmake : ROS1의 catkin 업그레이드 버전. CMake의 빌드 설정 파일인 CMakeList.txt 기반으로 빌드 
  - CMake를 사용하지 않는 Python 패키지 관리도 가능 


### 빌드 툴
: 전체 패키지 대상 (상위 레벨, 의존성 높음) 

rosbuild, catkin_make, catkin_make_isolated, catkin_tools, ament_tools 그리고 현재 ROS 2 버전에서 널리 사용되고 있는 colcon이 있음 

- ament_tools
: ROS 2의 ament_cmake 및 ament_python, 순수 CMake 패키지를 모두 지원하는 툴로 catkin_make, catkin_make_isolated, catkin_tools 모두의 기능을 사용할 수 있으며 ROS 2 Bouncy 버전 이전까지 사용되었다.

- colcon
: ROS 1과 ROS 2 모두를 지원하기 위하여 통합된 빌드 툴로서 소개되었으며 ROS 2 Bouncy 이후 ROS 2의 기본 빌드 툴로 사용 중에 있다.

### 빌드 방법
- 소스 코드가 있는 workspace로 이동하고 colcon build 명령어로 전체를 빌드.
- 특정 패키지만 선택하여 빌드하고자 할 때에는 `--packages-select` 옵션을 이용하고 symlink를 이용하려면 `--symlink-install` 옵션을 붙여줌.

`$ cd ~/robot_ws && colcon build --symlink-install`
`$ cd ~/robot_ws && colcon build --symlink-install --packages-select [패키지 이름]`


- Multiple workspace : ROS2에서는 복수의 독립된 워크스페이스를 사용할 수 있음  
- No non-isolated build : 모든 패키지 별도로 빌드 
- No devel space : 패키지를 빌드 한 후 설치해야 패키지를 사용할 수 있다. `colcon build --symlink-install` 와 같은 옵션을 사용하면 패키지 설치 없이도 패키지 사용할 수 있음.  

### 빌드 시스템에 필요한 부가 기능 
#### vcstool (버전 컨트롤 시스템 툴) 
여러 리포지토리 작업을 보다 쉽게 관리할 수 있도록 설계됨.

ex) 

$ wget https://raw.githubusercontent.com/ros2/ros2/foxy/ros2.repos $ vcs import src < ros2.repos

#### rosdep (의존성 관리 툴) 
 package.xml에 기술된 의존성 정보를 가지고 의존성 패키지들을 설치해 주는 역할. 

ex)

$ sudo rosdep init $ rosdep update $ rosdep install --from-paths src --ignore-src --rosdistro foxy -y --skip-keys "console_bridge fastcdr fastrtps rti-connext-dds-5.3.1 urdfdom_headers"

#### bloom (바이너리 패키지 관리 툴) 
패키지 개발자가 개발한 패키지를 유지보수 및 관리하기 위한 툴이다. 


## [패키지 파일 사용 방법 ](https://cafe.naver.com/openrt/24411)
### 패키지 설정 파일 
#### package.xml
패키지의 정보를 기술 (패키지 이름, 저작자, 라이선스, 의존성 패키지 등)
각 패키지당 무조건 1개의 패키지 설정 파일 (package.xml)을 포함

### 빌드 설정 파일 
#### CMakeLists.txt


### 파이썬 패키지 설정 파일
#### setup.py

### 파이썬 패키지 환경 설정 파일 
#### setup.cfg

### rqt 플러그인 설정 파일
#### plugin.xml

### 패키지 변경로그 파일 
#### CHANGELOG.rst

### 라이선스 파일 
#### LICENSE

### 패키지 설명 파일 
#### README.md

나는 우분투 18.04를 사용하고 있어서 ROS2 Dashing 버전을 사용한다. ROS2 공식 사이트에 나온대로 따라가는 것보다 더 자세하게 설명되어있어서, 둘다 참고하되 옵션 설정, VSCode 환경 설정같은 부분은 위의 카페를 참고하였다.

메모

• Run commands 를 따로 설정하지 않으면 source /opt/ros/dashing/setup.bash 를 입력 후에 ros2 실행 가능함.

Visual Studio Code 단축키

• 빌드 : Ctrl + Shift + b

• 빌드+디버깅 :Ctrl + Shift + d (C++, Python 과 같이 언어별로 다른데 아래의 실행 순서를 참고하여 각 언어에 맞게 디버깅해보자.)

  • cpp
    • Run and Debug (Ctrl + Shift + d)로 이동
      • "Debug-rclcpp(gbd)" 선택
      • "Package name" 입력 (예: topic_service_action_rclcpp_example)
      • "node name" 입력 (예: argument)
      • Start Debugging 클릭 (F5)

- py
  - Run and Debug (`Ctrl + Shift + d`)로 이동
  - "Debug-rclpy(debugpy)" 선택
  - Start Debugging 클릭 (`F5`)

• 패키지 매니저. GUI로 버전관리 할 수 있음.

source ~/.bashrc

• 아나콘다, 패키지 등을 설치한 후 설치 활성화
• 관리자가 추가한 새 PATH 환경 변수를 현재 셸 세션에 로드

install aptitude 시 오류

• 오류 내용
  E: Could not get lock /var/lib/dpkg/lock-frontend - open (11: Resource temporarily unavailable) E: Could not get lock /var/lib/dpkg/lock-frontend - open (11: Resource temporarily unavailable)

• 현재 실행중인 커맨드 창 모두 끄고 다시 실행
  sudo killall apt apt-get
  

패키지 설치 시 depend 문제

https://serverfault.com/questions/1035430/install-libssl-dev-on-ubuntu-20-04-1-upgrade-from-18-04-1-reports-unmet-depend

sudo aptitude install libssl-dev

he following NEW packages will be installed:
  libssl-dev{b} 
0 packages upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
Need to get 1.582 kB of archives. After unpacking 8.005 kB will be used.
The following packages have unmet dependencies:
 libssl-dev : Depends: libssl1.1 (= 1.1.1f-1ubuntu2) but 1.1.1g-1+ubuntu18.04.1+deb.sury.org+1 is installed
The following actions will resolve these dependencies:

     Keep the following packages at their current version:
1)     libssl-dev [Not Installed]                         



Accept this solution? [Y/n/q/?] n
The following actions will resolve these dependencies:

     Downgrade the following packages:                                                   
1)     libssl1.1 [1.1.1g-1+ubuntu18.04.1+deb.sury.org+1 (now) -> 1.1.1f-1ubuntu2 (focal)]



Accept this solution? [Y/n/q/?] y
The following packages will be DOWNGRADED:
  libssl1.1 
The following NEW packages will be installed:
  libssl-dev 
0 packages upgraded, 1 newly installed, 1 downgraded, 0 to remove and 0 not upgraded.
Need to get 2.900 kB of archives. After unpacking 8.087 kB will be used.
Do you want to continue? [Y/n/?] Y

1. aptitude 설치
2. sudo aptitude install <패키지 이름>
3. Keep the following packages at their current version: Accept this solution? [Y/n/q/?] → n 라고 입력
4. Downgrade the following packages: Accept this solution? [Y/n/q/?] → y 라고 입력
5. sudo apt-get install 패키지 하면 잘 설치되는 것을 확인할 수 있다. ㅠㅠㅠㅠㅠㅠ

지금까지의 거의 모든 패키지 dependency 문제를 이렇게 해결할 수 있었을 것 같다...!!!

YOLO v3 설치 과정

make 시 cuda_runtime.h : No such file or directory

https://github.com/pjreddie/darknet/issues/753
#검색 키워드 : yolo v3 make 오류 cuda_runtime.h

cudnn.h: no such file or directory

yolo를 설치하려면 Makefile을 수정하는 과정이 필요한데, 수정 완료 후 변경된 내용을 적용하려면 make를 입력해야한다. 그런데 YOLO를 설치하기 전에 cuDNN을 제대로 설치하지 않았다면 cudnn.h: no such file or directory와 같은 에러를 만난다. 그래서 나는 CUDA부터 다시 설치했다.

• (CUDA 설치 : 10.1, Ubuntu 18.04) https://developer.nvidia.com/cuda-10.1-download-archive-update2?target_os=Linux&target_arch=x86_64&target_distro=Ubuntu&target_version=1804&target_type=deblocal

wget https://developer.download.nvidia.com/compute/cuda/repos/ubuntu1804/x86_64/cuda-ubuntu1804.pin
sudo mv cuda-ubuntu1804.pin /etc/apt/preferences.d/cuda-repository-pin-600
wget https://developer.download.nvidia.com/compute/cuda/10.1/Prod/local_installers/cuda-repo-ubuntu1804-10-1-local-10.1.243-418.87.00_1.0-1_amd64.deb
sudo dpkg -i cuda-repo-ubuntu1804-10-1-local-10.1.243-418.87.00_1.0-1_amd64.deb
sudo apt-key add /var/cuda-repo-10-1-local-10.1.243-418.87.00/7fa2af80.pub
sudo apt-get update
sudo apt-get -y install cuda

• 이후에 기본으로 사용할 CUDA 버전 지정은 https://ghostweb.tistory.com/832 을 참고했다.

  1. sudo gedit ~/.profile
  2. profile 창 마지막 칸에 아래 두 줄 입력 export PATH=/usr/local/cuda-10.1/bin:$PATH export LD_LIBRARY_PATH=/usr/local/cuda-10.1/lib64:$LD_LIBRARY_PATH
  3. source ~/.profile

• 참고자료 (cuDNN 설치~) https://cafepurple.tistory.com/39

cuda 다른 버전 재설치 이후에도 버전 변경이 안될 때

sudo install cuda 가 아니라 sudo install cuda-10.1 로 입력 (새로운 버전까지 추가로 작성)

설치

https://pgmrlsh.tistory.com/6?category=766787

• 마지막 줄 실행 시 permission denied: ./linux_mark.sh 발생
  chmod +x linux_mark.sh 로 권한 부여

YOLO 안녕..

험난한 YOLO, OpenCV 환경 구축 과정과 약 10시간의 학습을 거친 후, 테스트 결과는 처참했다. 웹캠 demo에서 아무도 인식하지 못했을 뿐만 아니라 train에 사용했던 이미지에도 반응하지 않았다. 오류를 고쳐본답시고 이것 저것 건드리다보니 example 이미지를 사용해도 box가 나타나지 않았다. 아직 해결하지 못한 문제는 darknet과 build 폴더의 위치가 어디에 존재해야 하는가이다. 여기에 있던 darknet이 저기에도 똑같이 있고.. 공식 문서나 구글링 결과에도 정확히 확인할 수 있는 곳이 없었다. 결국 OpenCV부터 다시 깔아보겠다고 크게 마음을 먹고 모두 지웠다가 3.2.0, 4.5 버전으로 재설치했는데 이번에는 OpenCV 설치부터 애를 먹었다. 도대체 어디서부터 꼬인걸까 .. 중간에 설치까지는 성공했다가 또 다시 설치부터 막히니까 진이 빠졌다.

얼굴'식별'에 YOLO?

진이 빠진 것과는 별개로, YOLO를 포기하게 된데에는 다른 이유가 있었다. 우리가 YOLO를 사용하고자 한 이유는 얼굴 인식때문이었는데, 얼굴의 세세한 부분을 감지해야하는 얼굴 식별의 경우 YOLO는 적합하지 않음을 깨달았음 처음 학습 결과에 반응하지 않는 이유를 나는 뭔가 설정이 잘못되어서, 동료는 학습이 덜 되어서라고 판단했는데 사실 알고보니 아예 적합하지 않은 알고리즘이었던 것이다.
YOLO가 얼굴인식에 적합하지 않은 객관적인 이유를 찾기 위해 논문들을 찾아 공부하였고, 얼굴 인식에 적합한 알고리즘 및 라이브러리를 찾을 수 있게 되었다.

사실 YOLO와 얼굴인식

Graph SLAM 구조

• Loop Closure Detection - Revisit
  
• 2D LiDAR SLAM은 5cm 수준의 고화질의 Map에서 Global(Loop closure) Constraint를 실시간 수준으로 계산할 수 있는 Branch-and-bound 방식을 제안함.
  • 
  • Branch-and-Bound (DFS 기반) :

Cartographer

• Localization

  • Frozen Pose graph(Map)와 현재 로봇이 만들고있는 Pose graph간의 inter trajectory constraint(또는 global constraint)를 지속적으로 찾아주는 방식
  • 현재 생성되는 pose trajectory의 길이를 windowing 방식으로 제한을 두어 실시간 최적화가 가능

• Cloud based Mapping
  cloud에서 map을 로봇에게 지속적으로 업데이트 해줌. 한정된 맵만 유지하고, 오버랩되는 submap은 지워줌. pose trajectory에 비례하는 것이 아니라 공간의 크기에 비례함

• TSDF (Truncated Signed Distance Function) support
  확률 그리드를 표현하는 방식의 일종
  주로 3D volume reconstruction 할 때 사용
  일반적인 확률 그리드 방식보다는 느리지만 더 정밀함

• cartographer 구조도
  

offline / online

Offline SLAM

센서 데이터를 모두 얻은 다음에 맵을 만드는 것

• $z_{1:T}$와 $u_{1:T}$를 고려해서 $x_{1:T}$와 $m$을 확률적으로 표현함

Onlnie SLAM

실시간으로 맵도 만들고, 자신의 위치도 파악하는 SLAM 시스템

• $u_t$와 $z_t$만을 이용해서 Map과 Path를 생성
• Online 식을 적분하면 Offline SLAM

• 서로소 집합 : 공통 원소가 없는 두 집합

• 서로소 집합 자료구조 (Union-Find) 트리 구조를 사용하여 같거나 다른 집합으로 분리해주거나 최대 N개의 집합으로 분리할 수도 있다.

  • 합집합 (Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
  • 찾기 (Find) : 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산

기본적인 구현 방법

# 특정 원소가 속한 집합 찾기 
def find_parent(parent, x):
    #루트노드를 찾을 때까지 재귀호출
    if parent[x]!=x : 
        return find_parent(parent, parent[x])
    return x 

# 두 원소가 속한 집합을 합치기 
def union_parent(parent, a, b): #여기서 parent의 의미는?
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a<b :
        parent[b] = a
    else : 
        parent[a] = b

# 노드의 개수와 간선의 개수 입력 받기
v, e = map(int, input().split())
parent = [0]*(v+1) # 부모 테이블 초기화

for i in range(1,v+1): # 부모를 자기 자신으로 초기화
    parent[i] = i

# UNION 연산을 각각 수행 
for i in range(e):
    a,b = map(int, input().split())
    union_parent(parent, a, b)

# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end="")
for i in range(1, v+1):
    print(find_parent(parent, i), end=" ")

print()

# 부모테이블 출력
print('부모 테이블:', end='')
for i in range(1, v+1):
    pritn(parent[i], end=' ')

실행결과 :

6 4 #input 
2 1
3 2
4 1
6 5
각 원소가 속한 집합: 1 1 1 1 5 5 
부모 테이블:1 1 1 1 5 5 

🛑 기본적인 구현 방법의 문제점

• 합집합 연산이 편향되게 이루어질 경우 찾기 함수가 비효율적으로 동작함. → 최악에는 시간복잡도 O(V) : 모든 노드를 확인해야함

경로압축

• FIND 함수의 최적화 : FIND 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 바로 갱신한다.

# 특정 원소가 속한 집합을 찾기 
def find_parent(parent, x):
    if parent[x] != x :
        parent[x] = find_parent(parent, parent[x])
    return parent[x] # 기존에는 return x 였음

👉FIND 함수를 호출한 이후, 해당 노드의 루트 노드가 바로 부모 노드가 됨.

서로소 집합을 활용한 사이클 판별

• 무방향 그래프 내에서 사이클을 판별할 때 사용 가능

  • cf) 방향 그래프에서는 DFS를 이용하여 판별 가능

• 사이클 판별 알고리즘

  1. 각 간선에 연결된 두 노드의 루트노드 확인 1) 루트 노드가 서로 다르다면 UNION 2) 루트 노드가 서로 같다면 CYCLE 발생
  2. 그래프에 포함되어있는 모든 간선에 대해 1번 과정 반복

# 부모 테이블 초기화 이후

# 사이클 발생 여부 
cycle = False 

for i in range(e):
    a, b = map(int, input().split())
    # 사이클 발생하면 종료
    if find_parent(parent, a) == find_parent(parent, b) : 
        cycle = True
        break 
    #사이클 X -> 합집합
    else :
        union_parent(parent, a, b)

• 신장 트리 : 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
  • cf) 트리의 조건 : 모든 노드가 서로 연결, 사이클 X

크루스칼 알고리즘

: 최소 신장 트리(최소한의 비용으로 구성되는 신장 트리)를 찾는 방법

• 그리디 알고리즘 : 가장 짧은 간선부터 트리에 포함하고, 사이클을 만들면 제외
• 시간 복잡도 : $O(ElogE)$, E는 간선의 개수
  • 간선을 정렬할 때 걸리는 시간

1. 간선을 오름차순으로 정렬
2. 각 간선이 사이클을 발생시키는지 확인 1) 사이클이 발생하지 않는 경우 최소 신장 트리에 포함 2) 사이클이 발생하는 경우 포함 X
3. 모든 간선에 대해 2번의 과정 반복

#부모테이블 초기화 이후

edges = []
result = 0

#간선 정보 입력받기
for _ in range(e) :
    a,b,cost = map(int, input().split())
    edges.append((cost, a, b))

#간선을 비용순으로 정렬
edges.sort()

#간선 하나씩 확인
for edge in edges : 
    cost, a, b = edge
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost 

print(result)

위상정렬

: 사이클이 없는 방향그래프(DAG, Direct Acyclic Graph)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열

• *큐 *이용
• 시간 복잡도 : 모든 노드 확인하며 차례대로 간선 제거 : $O(V+E)$

1. 진입 차수가 0인 모든 노드를 큐에 투입
2. 큐가 빌 때까지 아래 과정 반복 1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거 2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

✔ 수행 결과 : 각 노드가 큐에 들어온 순서

• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단 가능
• 스택을 활용한 DFS를 활용할 수도 있음

from collections import deque

v, e = map(int, input().split())
indegree = [0]*(v+1)
graph = [[] for i in range(v+1)]

# 방향 그래프 간선정보 입력받기 
for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1 #진입차수 1+

# 위상정렬 함수
def topology_sort():
    result = []
    q = deque()
    for i in range(1, v+1):
        if indegree[i] == 0 :
            q.append(i)
    while q: 큐가 빌 때까지 
        now = q.popleft() # 큐에서 원소 꺼내기
        result.append(now) 
        for i in graph[now]: # 해당 원소와 연결된 노드들의 진입차수 -1 
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

    for i in result : 
        print(i, end=" ")

topology_sort()

: 특정 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다.

• 노드 간 간선이 음의 값을 가지지 않아야 함

• 그리디 알고리즘 : 매 상황에서 가장 비용이 적은 노드를 선택함

• 동작 과정

  1. 출발 노드 설정
  2. 최단 거리 테이블 초기화 (Inf)
  3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
  5. 3~4번 반복

• 한번 처리된 노드의 최단 거리는 고정됨. 더 이상 바뀌지 않음.

구현 방법 : 순차탐색

매 단계마다 1차원 테이블의 모든 원소를 확인한다.

import sys 
input = sys.stdin.readline
INF = int(le9) #10억 

n, m = map(int, input().split())
start = int(input()) 
graph = [[] for i in range(n+1)] 
visited = [False]*(n+1) # 방문 체크 리스트 
distance = [INF]*(n+1) # 최단거리 테이블 초기화

for _ in range(m): #모든 간선 정보 입력 받기 
    a,b,c = map(int, input().split())
    graph[a].append((b,c)) 

def get_smallest_node():
    min_value = INF
    index = 0 
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i] 
            index = i 
    return index 

def dijkstra(start) : 
    distance[start] = 0
    visited[start] = True
    for j in graph[start] : 
        distance[j[0]] = j[1] # 이 부분 이해가 잘 안감

    for i in range(n-1) :
        now = get_smallest_node()
        visited[now] = True
        for j in graph[now]:
            cost = distance[now] + j[i]
            if cost < distance[j[0]] : 
                distance[j[0]] = cost 

dijkstra(start) 

for i in range(1, n+1):
    if distance[i] == INF : 
        print("INFINITY")
    else :
        print(distance[i]) 

• 시간 복잡도 : $O(V^2)$
• 코딩테스트에서 전체 노드 개수가 5000개 이하면 해결 가능 > 10,000개를 넘어가는 문제라면?

개선된 구현 방법 : 우선순위 큐

힙(Heap)

: 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나. 최소 힙, 최대 힙이 있다.

# 최소 힙 
import heapq

def heapsort(iterable):
    h = [] 
    result = []
    for value in iterable :
        heapq.heappush(h, value)
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

실행결과 : [0,1,2,3,4,5,6,7,8,9]

heappush, heappop : 오름차순 정렬

# 최대 힙
import heapq

def heapsort(iterable):
    h = [] 
    result = []
    for value in iterable :
        heapq.heappush(h, -value) # [-9, -8, -7, -6, -5, -4, -3, -2, -1, 0]
    for i in range(len(h)):
        result.append(-heapq.heappop(h)) 
    return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

실행결과 : [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

오름차순을 음의 값으로 변경해서 내림차순으로 만들기

😎 다시 다익스트라 알고리즘으로 돌아와서, Heap 자료구조를 이용해 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택한다. 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용한다.

import heapq
import sys
input = sys.stdin.readline #왜 하지?
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
distance = [INF]*(n+1)

for _ in range(m):
    a, b, c = map(int, input().split()) # a노드에서 b노드로 가는 비용은 c
    graph[a].append((b,c))

def dijkstra(start):
    q = []
    # 시작노드로 가기 위한 거리를 0으로 설정, q에 삽입
    heapq.heappush(q, (0,start)) 
    distance[start] = 0

    while q : #큐가 비어있지 않으면 
        dist, now = heapq.heappop(q) # 가장 최단거리가 짧은 노드 꺼내기
        if distance[now] < dist : # 더 짧은 경로가 있다면 무시
            continue
        for i in graph[now]: #현재 노드와 연결된 다른 인접한 노드들을 확인 
            cost = dist + i[1] 
            #현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우 
            if cost < distance[i[0]]:
                distance[i[0]] = cost 
                heapq.heappush(q, (cost, i[0]))


dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF : 
        print("INF")
    else : 
        print(distance[i])

실행결과 : 

    4 7 #n,m
    1 #start
    1 2 2 #graph
    1 3 5
    1 4 1
    2 4 2
    2 3 3
    3 2 3
    4 3 3
    0 # distance from start to 1
    2 # distance from start to 2
    4 # distance from start to 3
    1 # distance from start to 4

• 힙 자료구조를 이용하면 시간복잡도는 $O(ElogV)$가 된다.
  • 반복문은 최대 노드의 개수(V)만큼 처리되며, 현재 노드에서 다른 노드들을 확인하는 총 횟수는 최대 간선의 개수(E)만큼 처리된다.
• 직관적으로 전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사합니다. (???)

플로이드 워셜 알고리즘

: 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산

• 다익스트라 알고리즘과 마찬가지로, 거쳐가는 노드를 기준으로 알고리즘 수행
• 2차원 테이블 사용
• 다이나믹 프로그래밍 유형

각 단계마다 특정 노드 k를 거쳐가는 경우를 확인

$D_{ab}=min(D_{ab},D_{ak}+D_{kb})$

INF = int(1e9)

n = int(input())
m = int(input())
graph = [[INF]*(n+1) for _  in range(n+1)]

for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0

for _ in range(m):
    a,b,c = map(int, input().split())
    graph[a][b] = c

#플로이드워셜 알고리즘 수행 
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k]+graph[b][k]) 

#출력
for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b] == INF:
            print("INF",end=" ")
        else:
            print(graph[a][b], end=" ")
    print()

특징

• 각 단계마다 $O(N^2)$의 연산 → 총 시간 복잡도 : $O(N^3)$

실습한 내용을 사진과 함께 정리해두었습니다. https://shelled-bison-985.notion.site/1-31c87e71da8247119f74016ca189ef48

• 태블루의 가장 필수적인 기능들을 배울 수 있었음.
• 태블루는 엑셀의 고급 버전이다.
• 협업용으로 연습해보고 싶은데 어디서 경험해보지?

노션에 정리해서 사진 복붙이 안되는군요 ㅠㅠ 다음부터 공부한 내용은 모두 블로그에 적어야겠습니다! :)

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 하는 방법. 시간 효율성을 비약적으로 향상시킨다.

• * 자료구조에서 dynamic 이란?* : 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법 (그러나 여기서는 별다른 의미 없이 사용됨)

• 언제 사용 가능한가요? 1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있음. → 어떤 문제에 대한 해가 최적일 때, 그 해를 구성하는 부분 문제들의 해 역시 최적이다. 2. 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 할 때

피보나치 수열

점화식 : $a_n=a_{n-1}+a_{n-2}\quad a_1=1,; a_2=1$

def fibo(x):
  if x==1 or x==2:
    return 1 
  return fibo(x-1) + fibo(x-2)

→ fibo(6)의 계산 과정을 그래프화 함.

• 시간 복잡도 : $O(N^2)$
  • f(2)가 여러 번 호출되어 시간이 낭비됨.

메모이제이션 (Memoization)

: 한 번 계산한 결과를 메모리 공간에 메모하는 기법. 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴. (= 캐싱, caching) 다이나믹 프로그래밍에 국한된 개념은 아님

• 탑다운/보텀업 방식
  • 다이나믹 프로그래밍의 전형적 형태는 보텀업
  • DP 테이블 : 결과 저장용 리스트

탑다운 (Top-down) 방식

d = [0]*100
def fibo_top(x):
  if x==1 or x==2:
    return 1
  if d[x]!=0:
    return d[x] 
  d[x] = fibo(x-1) + fibo(x-2)
  return d[x]

보텀업 (Bottom-up) 방식

d=[0]*100

d[1] = 1
d[2] = 1
n = 99

for i in range(3, n-1):
    d[i] = d[i-1] + d[i-2]
print(d[n])

→ 메모이제이션 기법을 활용한 계산 과정

• 시간 복잡도가 $O(N)$로 줄어듦.

다이나믹 프로그래밍 vs 분할 정복

• 부분 문제의 중복에 차이가 있음.
  • 다이나믹 프로그래밍 문제는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨
  • 분할 정복은 동일한 부분 문제가 반복적으로 계산되지 않음.
    • 분할정복 예시 : 퀵 정렬 한번 Pivot이 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않음 → Pivot을 다시 처리하는 부분 문제 X

코딩테스트 대비 방법 ✌

👀 주어진 문제가 다이나믹 프로그래밍 유형인지 파악하는 것이 중요하다! 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토한 후, 풀이 방법이 떠오르지 않으면 다이나믹 고려하자.

일단 재귀함수로 비효율적인 완전 탐색 프로그램 작성 → 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있는가? → 코드 개선

일반 코테를 대비하기 위해서는 기본 유형만 숙지해도 괜찮다

cf. 최장경로 문제

• 그래프에서 두 정점을 가장 긴 길이로 연결하는 경로 구하기 문제
• AD의 최장 경로는 [A,C,B,D]인데, AC의 최장 경로는 [A,C]가 아닌 [A,B,C] 이다.
• 따라서 이러한 문제는 다이나믹 프로그래밍으로 해결하기 어렵다.

반복문 구현

def binary_search(array, target, start, end):
  while start  <= end:
    mid = (start+end) // 2
    if array[mid] == target:
      return mid
    elif array[mid] > target:
      end = mid-1
     else :
       start = mid+1
  return None 

파이썬 이진 탐색 library

: 정렬된 리스트에 값을 삽입할 때 정렬을 유지할 수 있는 인덱스를 리턴

• bisect_left(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
• bisect_right(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

EX.

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4
print(bisect_left(a, x))
print(bisect_right(a, x))

실행결과 : 2 4

특정 범위에 속하는 데이터의 개수 구하기

from bisect import bisect_left, bisect_right

def cbr(a, left,right):
    right_index = bisect_right(a, right)
    left_index = bisect_left(a, left)
    return right_index - left_index 

Parametric Search

: 최적화 문제를 결정문제(Y or N)로 바꾸어서 해결하는 기법 => 이진탐색으로 해결 가능

• 데이터를 특정한 기준에 따라 순서대로 나열하는 것
• 정렬 알고리즘은 공식처럼 사용되기도 함

선택 정렬

: 처리되지 않은 데이터 중 가장 작은 데이터를 선택 -> 맨 앞에 있는 데이터와 바꾸는 것을 반복

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)):
    min_index = i 
    for j in range(i+1, len(array)):
        if array[min_index] > array[j] :
            min_index = j 
    array[i], array[min_index] = array[min_index], array[i] #swap

실행결과 : [0,1,2,3,4,5,6,7,8,9]

• 시간 복잡도는 $O(N^2)$ 이다.

삽입 정렬

: 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입

EX) 7 5 9 0 3 1 6 2 4 8 로 위치할 때 7은 제 자리를 지키고, 5는 7보다 작으므로 7 전으로 이동, -> 5 7 ... 9는 7보다 크므로 제자리, 0은 5보다 작으므로 5 전으로 이동, -> 0 5 7 9 ...

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(1, len(array)):
    for j in range(i , 0 , -1) : #정확한 위치를 찾기 위해 
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else : # 더 작은 값을 만날 경우, 더 비교할 필요 없음 
            break

• 선택정렬보다 구현 난이도 ↑ / 동작 효율 ↑
• 시간 복잡도는 $O(N^2)$ 이다.
• 현재 리스트 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.
  • 최선일 때는 $O(N)$

퀵 정렬

: 기준 데이터를 설정하고, 그 기준 데이터보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

• 일반적인 상황에서 가장 많이 사용됨
• 정렬 라이브러리의 근간이 됨 (with 병합정렬)
• 첫번째 데이터를 기준 데이터(=pivot)로 설정
• 시간 복잡도는 평균 $O(NlogN)$, 최악일 경우 $O(N^2)$ 이다.

EX.

5 7 9 0 3 1 6 2 4 8 일 때, Pivot = 5 왼쪽에서부터는 5보다 큰데이터를, 오른쪽에서부터는 5보다 작은데이터를 선택 -> 두 데이터의 위치를 서로 변경 -> 반복 -> 왼쪽/오른쪽에서 방향이 서로 엇갈리게 되는 순간, pivot과 작은데이터의 위치를 서로 변경. 기존 pivot을 기준으로 분할하면 5보다 작은 숫자들은 왼쪽에 / 5보다 큰 숫자들은 오른쪽에 위치하게 됨. -> 왼쪽과 오른쪽 데이터를 각자 묶어 위의 과정 반복

파이썬 일반적인 코드

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end) : 
    if start >= end : # 원소가 한 개인 경우 종료 
        return 
    pivot = start 
    left = start+1
    right = end 
    while (left <= right) : 
        while (left <= end and array[left] <= array[pivot]):
            left += 1
        while (right > start and array[right] >= array[pivot]):
            right -= 1
        if (left > right):
            array[right], array[pivot] = array[pivot], array[right] 
        else : 
            array[left], array[right] = array[right], array[left]
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end) 

quick_sort(array, 0, len(array)-1)

파이썬 장점 살린 코드

def quick_sort(array):
    if len(array) <= 1 : #리스트가 하나 이하의 원소만을 담고 있으면 종료 
        return array 
    pivot = array[0]
    tail = array[1:]

    left_side = [x for x in tail if x <= pivot] 
    right_side = [x for x in tail if x > pivot]

    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

계수 정렬

: 정수 형태로 표현할 수 있을 때만 사용할 수 있음

• 시간 복잡도는 최악의 경우에도 $O(N+K)$를 보장함.
• 때에 따라 심각하게 비효율적임 (0, 999999 단 2개만 존재할 때)
• 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적

EX. 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 일 때, 정렬할 데이터의 범위만큼의 리스트 생성 -> 각 데이터가 몇 번 등장했는지 횟수 기록 -> 횟수만큼 인덱스를 출력

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
count = [0]*(max(array)+1) 
for i in range(len(array)):
    count[array[i]] += 1 
for i in range(len(count)):
    for j in  range(count[i]):
        print(i, end=' ')

선입후출 형식 컵에 원소를 한줄로 채워넣는 것으로 이해하면 쉽다.

stack = [] 
stack.append()
stack.pop() : 마지막에 추가한 원소를 제거하면서 동시에 return함. 

큐 자료구조

선입선출 형식 입구와 출구가 뚫려있는 원통으로 이해하면 쉽다.

from collections import deque

queue = deque()
queue.append()
queue.popleft()

재귀함수

자기 자신을 다시 호출하는 함수

사용 시 유의사항

• 종료 조건을 반드시 명시해야 함
• 모든 재귀함수는 반복문을 이용해 동일한 기능을 구현할 수 있음
• 함수를 연속적으로 호출하면, 메모리 내부 스택 프레임에 쌓임. 그래서 스택 사용해야할 때 라이브러리 대신 재귀함수 사용하는 경우가 많음 !

  최대공약수 계산 : 유클리드 호제법

• 유클리드 호제법 A = B*k + R 일 때, A와 B의 최대공약수는 B와 R의 최대공양수와 같다.

def gcd(a,b):
  if a%b == 0 :
    return b
  else : 
    return gcd(b, a%b) 

"어떤 순서대로 데이터를 탐색할 것인가?"

# 각 노드가 연결된 정보 (2차원 리스트)
graph = [
[], #빈 노드
[2, 3, 8], # 1번 노드는 2,3,8번 노드에 연결됨
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]

# 방문 정보 
visited = [False] * 9 

DFS

• 깊이 우선 탐색
• 스택 or 재귀함수를 이용

수행 과정

1. 탐색 시작 노드를 스택에 삽입 & 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문 처리
   • 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

동작 예시

# DFS 메서드 정의 
def dfs(graph, v, visited) : 
  visited[v] = True  # 현재 노드를 방문 처리 
  print(v, end=' ')
  for i in graph[v] : 
    if not visited[i]:
      dfs(graph, i, vistied)

출력 결과 : 1 2 7 6 8 3 4 5

BFS

• 너비 우선 탐색 : 가까운 노드부터 우선적으로 탐색함
• 큐 이용

수행 과정

1. 탐색 시작 노드를 큐에 삽입 & 방문처리
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 & 방문처리
3. 더이상 2번 과정을 수행할 수 없을 때까지 반복

동작 예시

from collections import deque 

def bfs(graph, start,visited):
  queue = deque([start])
  visited[start] = True 
  while queue :  # 큐가 빌 때까지 반복 
    v = queue.popleft()
    print(v, end=' ')
    for i in graph[v] :
      if not visited[i]:
        queue.append(i)
        visited[i] = True

bfs(graph, 1, visited)    

출력 결과 : 1 2 3 8 7 4 5 6

DFS, BFS 차이는?

• DFS

  • 미로 탐색과 유사하다. 한 방향으로 갈 수 있을 때까지 가다가, 길이 막히면 이전의 갈림길로 돌아와 다시 탐색을 시작한다.
  • 모든 노드를 방문해야할 때 선택한다.
  • BFS보다 구현이 간단하지만, 속도는 느리다.
  • 시간복잡도
    • 인접리스트 : O(N+E)
    • 인접행렬 : O(N^2)

• BFS

  • 두 노드 사이의 최단/임의의 경로를 찾고 싶을 때 사용한다.