23년 1학기 13주 수업

ToC

• 모빌리티서비스
• 알고리즘
  • 리뷰
    • 피보나치
    • knapsack
  • 팰린드롬
  • GA 리뷰 + 공지
• 소프트웨어분석및설계
• 소프트웨어디자인패턴

모빌리티서비스

• 라즈베리파이 네트워크 설정을 포함한 SBC setup
• OpenCR setup
• roscore bringup, teleop, rqt
• SLAM, save map

알고리즘

리뷰

DP를 구성하는 세 가지 요소

1. guess: 문제를 잘 파악
2. recursion: 재귀
3. memoization: 잘 기억

DP 풀이 순서

1. 부분 문제 결정
2. 각 부분 문제에 소요되는 시간 계산
3. 부분 문제 구현
4. 재귀 설계
5. 원래 문제 해결

피보나치

memo = {}
fib(k):
    if(k in memo) return memo[k]
    else if (k <= 2) f= 1
        else: f = fib(k - 1) + f(k + 2)
            memo[k] = f
            return f

해결해야 할 오리지널 문제는 fib(k). 아래에서부터 위로 올라가며 계산하는 문제이기 때문에 Bottom-up 방식이라고 한다.

knapsack

용량이 정해진 주머니와, 크기와 가치가 정해진 요소들이 있다. 각 요소의 크기와 가치는 S_i, X_i로 나타낸다.

1. suffix i given X
2. guess: in or not in
3. DP[i, X] = max(DP[i + 1, X], DP[i + 1, X - s_i] + X_i)

초기 상태: 아무것도 넣지 않음
1-1. 첫 번째 아이템을 넣지 않는다.
1-1-1. 두 번째 아이템을 넣지 않는다.
1-1-2. 두 번째 아이템을 넣는다.
1-2. 첫 번째 아이템을 넣는다.
1-2-1. 두 번째 아이템을 넣지 않는다.
1-2-2. 두 번째 아이템을 넣는다.

사람의 생각은 위와 같은 방식으로 진행되지만 실제 컴퓨팅은 주머니가 꽉 찬 상태에서 비워지는 방향으로 이루어짐.

팰린드롬

주어진 단어에 사용된 알파벳을 조합하여 최대한 긴 팰린드롬 단어를 찾는다. 단어의 의미는 고려하지 않는다.

탐색 방식: 양 끝에서 좁혀오는 투 포인터(i, j) 탐색

1. 부분 문제: 동일한 알파벳의 쌍 찾기
2. X[i] == X[j]: 2 + pal(i + 1, j - 1)
X[i] != X[j]: max(pal(i, j - 1), pal(i + 1, j))
3. i: 0 -> n
   j: n -> 0
4. start pal(0, n - 1)

pal(i, j):
    if (i == j): return 1  # base case
    else if (X[i] == X[j]):
        if (i + 1 == j): return 2  # base case
        else: return 2 + pal(i + 1, j - 1)
    else: return max(pal(i, j - 1), pal(i + 1, j))

C++ 구현

#include <iostream>
#include <vector>
#include <random>
#include <string>
using namespace std;

int longest_pal(string& word, int i, int j) {
  if (i == j)
    return 1;
  if (word.at(i) == word.at(j)) {
    if (i + 1 == j)
      return 2;
    else
      return 2 + longest_pal(word, i + 1, j - 1);
  }
  else
    return max(longest_pal(word, i + 1, j), longest_pal(word, i, j - 1));
}

int longest_pal(string& word, int i, int j, vector<vector<int>>& memo) {
  /*
  * 컨닝페이퍼 작성 팁: 모든 반환값을 컨닝페이퍼에서 베껴서 내게 한다.
  * 채워지지 않은 컨닝페이퍼는 내기 전에 채워둔다.
  */
  if (memo[i][j] != -1)
    return memo[i][j];

  if (i == j) {
    memo[i][j] = 1;
    return memo[i][j];
  }

  if (word.at(i) == word.at(j)) {
    if (i + 1 == j) {
      memo[i][j] = 2;
      return memo[i][j];
    }
    else {
      if (memo[i + 1][j - 1] == -1)
        memo[i + 1][j - 1] = longest_pal(word, i + 1, j - 1, memo);
      memo[i][j] = 2 + memo[i + 1][j - 1];
      return memo[i][j];
    }
  }
  else {
    if (memo[i + 1][j] == -1)
      memo[i + 1][j] = longest_pal(word, i + 1, j, memo);
    if (memo[i][j - 1] == -1)
      memo[i][j - 1] = longest_pal(word, i, j - 1, memo);
    return max(memo[i + 1][j], memo[i][j - 1]);
  }
}

int main()
{
  clock_t clock_start;

  mt19937 gen(random_device{}()); // 난수 생성기
  uniform_int_distribution<int> alphabet(int('a'), int('z')); // 알파벳 아스키코드 생성
  uniform_int_distribution<int> word_len(15, 25); // 단어 길이 선택
  string word = ""; // 단어
  int idx = 0; // 팰린드롬 길이
  vector<vector<int>> memo;
  vector<string> words;

  for (int i = 0; i < 30; i++) {
    word.clear();
    for (int i = 0; i < word_len(gen); i++)
      word.push_back(alphabet(gen)); // 단어에 글자 붙이기
    words.push_back(word);
  }

  clock_start = clock();
  for (string& wd : words) {
    memo.clear();
    memo.resize(wd.length(), vector<int>(wd.length(), -1));
    std::cout << "# " << ++idx << ": " << longest_pal(wd, 0, wd.length() - 1) << ", " << wd << "\n";
  }
  std::cout << "\nrecursion 실행 시간 : " << double(clock() - clock_start) << "ms\n\n";

  idx = 0;
  clock_start = clock();
  for (string& wd : words) {
    memo.clear();
    memo.resize(wd.length(), vector<int>(wd.length(), -1));
    std::cout << "# " << ++idx << ": " << longest_pal(wd, 0, wd.length() - 1, memo) << ", " << wd << "\n";
  }
  std::cout << "\nmemo 실행 시간 : " << double(clock() - clock_start) << "ms\n";

  return 0;
}

시간복잡도 계산

1. T(n) = 2T(n - 1) = 2^n → exponential → use memo for O(n^2)
2. 어디에 memo를 넣을지는 각자 알아서 생각해보기(기말고사에 나올지도?)

GA 리뷰 + 공지

• 보고서 형식 자유, 분량만 지키면 된다. 그래도 글자 크기 1pt로 하면 안 된다.
• 선택한 알고리즘에 대해 왜 그것을 선택했는지, 하이퍼 파라미터를 바꿔봤을 때 어떻게 달라지는지 등 탐구 과정에 대한 내용이 더 많이 들어가길 바람.
• 하이퍼 파라미터 튜닝: grid search. 예를 들어 하이퍼 파라미터가 30개 있다면 30차원의 grid를 모두 채우면서 테스트를 하는 것. 현실적으로 너무 오래 걸리니까 요즘은 랜덤으로 준다. 매번 부여된 랜덤한 값에 대한 결과를 보고 좋은 방향으로 찾아가는 것. random search라고 한다.

소프트웨어분석및설계

• UP(unified process): 가장 많이 사용되는 객체 지향 개발 방법론, 반복적이고 점증적인 개발
  • Inception(개시)
    • 대강의 비전과 요구사항, 비즈니스 케이스, 범위, 대략적 비용 추정에 대해 정의
    • 기본적인 요구 사항 기술, 유스케이스 분석: 모든 유스케이스를 작성할 필요는 없음
    • 기능 요구: 사용자가 사용할 수 있는 모든 기능 / 비기능 요구: 기능을 제외한 모든 것. non-functional req. 대표적으로 품질 요구를 의미함. 소프트웨어의 성능, 속도, 정확성, 보안 등. “How well”
    • PoC: 개념 증명. 설계한 시스템/소프트웨어가 실제로 작동 가능한지 프로토타입을 만들어 확인함.
    • iteration: 첫 번째 feature 단위 release에서 할 일 정함
  • Elaboration(정련)
    • 정제된 비전, 핵심 아키텍쳐(구조) 정의. 대부분의 요구사항과 범위 식별, 보다 현실적인 추정. 높은 위험성 해결
    • 기본적이고 핵심적인 시나리오 구성
    • 도메인 모델, 설계 모델, SW 아키텍처 문서, 데이터 모델, 스토리보드, UI 프로토타입 등을 만듦
      분석 단계에서는 UI에 대해 고려하지 않는다. ‘버튼’, ‘터치’ 등의 UI를 나타내는 표현은 설계 단계에서 나오는 것. 이외에도 데이터베이스, 제어 등의 개념이 개입할 때를 설계 단계라고 한다.
  • Construction(구축)
    • 반복적인 구현 및 배치 준비
    • 사용 가능한 완제품을 만들어가는 단계
  • Transition(전이)
    • 베타 테스트, 배치
    • 사용자에게 배포
• 분석 절차 - GRAPPLE
  1. 요구사항 수집
     • 전체 과정에서 가장 중요한 활동으로 구성됨
  2. 분석
     • 수집한 요구 사항 세분화
  3. 설계
     • 솔루션 고안에 관한 결정 수행: 객체 및 컴포넌트 다이어그램 개발, 배포 계획, 사용자 인터페이스 설계, 시험 설계, 문서화 시작
  4. 개발
     • 코딩 시작
  5. 배포
     • 백업 및 복구 준비, 하드웨어에 시스템 설치, 배포
• 활동 다이어그램: flow chart의 확장 버전. 알고리즘을 서술할 때에도 사용함.
• 다시 한번 과정 정리
  1. 비즈니스 업무 흐름 파악
  2. 도메인 분석: 인터뷰 분석(명/동사 분석), 일반화/그룹화 -> 주요 클래스/관계 파악.
     클래스 파악 팁: 무슨 책임이 있는지 생각해보기
  3. 클래스 간 연관에 이름 붙이기: 삼원 연관, 반사 연관(자기 자신과 연관), 집합/복합 연관
  4. 클래스 내용 채우기: 속성과 오퍼레이션 작성
  5. 유스케이스 작성 후 클래스 업데이트
  6. 사용자 인터페이스 설계
     • 사용자 중에는 색약/색맹이 있을 수 있으니 색깔에 너무 많은 의미를 주지 말라
     • 화면 좌측에 비중 있는 기능을 배치하고, 관련 있는 기능은 그룹화한다.
     • 취소 기능을 제공하고, 가급적 취소 횟수를 제한하지 않는다.
     • 어떤 기능을 실행하기 위한 동작은 한 가지 이상 제공한다.
     • 오래 봐도 눈이 피곤하지 않게 색깔은 적당히 쓴다.
• 분석과 설계는 다르다
  • 분석: 사용자 시각. needs -> requirement.
  • 설계: 개발자 시각. requirement -> target lang, DB, UML. 품질, 성능, 사용성, 보안, 신뢰성, 유지보수성 등을 고려해야 함. 이 요소들은 아키텍처의 영향을 받고, 서로 trade-off 관계라 잘 고민해야 함.
• 시험 공지
  • 서술형 주관식
  • 중요한 컨셉, 간단한 분석 문제
  • 90분 정도
  • 팀 과제는 코딩보다 분석과 설계에 시간을 더 투자하고, 분석/설계의 내용이 코드에 잘 반영되도록 할 것. 코딩 과목이 아니니까.

소프트웨어디자인패턴

• Chain of Responsibility 패턴
  • 책임 떠넘기기
  • 해결자(추상 클래스), 구체해결자, 요구자. 각 해결자는 자신의 다음 순서 해결자를 갖는다.
  • 온라인 주문 시스템 예시: 인증된 사용자만 주문 가능하게 함, 관리자는 모든 권한 허용. 인증 과정은 차례대로 수행되어야 함. 중도 탈락 시 이후 과정 진행 불가.
  • 인증의 각 과정을 독립된 핸들러로 구현, 각 핸들러를 체인으로 연결
  • 문제가 발생하여 “누군가는 처리해야 하는” 상황
  • 각 핸들러가 문제를 동시에 처리하는 게 아니기 때문에 처리할 수 있는 문제가 서로 겹치는 건 괜찮다.
  • 처리가 될 때까지 다음 인증자(해결자)에게 떠넘기는 체인. 구매 인증 과정이라고 생각한다면 인증 실패 사유가 발견될 때까지 다음 인증자에게 넘기는 것.
  • 특정 문제 케이스에 대해 문제 해결 과정 시퀀스 다이어그램 그리기 문제 있음. 각 클래스 별 해결 가능한 문제를 정해주고, 클래스마다 문제를 몇 개나 해결할 수 있는지 / 몇 개나 처리하지 못했는지 개수를 세는 문제 있음(뒤에 있는 해결자는 앞에서 해결한 문제는 제외하고 세어야 한다) + 마지막까지 남은 문제를 모두 해결할 수 있는 논리 구조 작성하기 문제 낼 수 있음.
  • 해결할 수 있는 문제가 많을수록 내부에서 처리할 일도 많은 게 일반적이므로 보통은 복잡하고 할 수 있는 일이 많은 해결자가 뒤로 간다. 지금은 예시이므로 각 해결자가 알맹이 없이 껍데기만 있어서 역순이 더 효율적일 뿐이다.
  • 각 해결자의 해결 시간을 계산할 때, 자기 자신의 해결 시간이 짧더라도 앞에 다른 해결자가 있다면 그 과정을 거쳐오는 시간까지 같이 포함해야 한다. -> 보기엔 좋은데 효율성 계산이 참 까다로움.
  • ‘문제’와 ‘해결자’가 느슨하게 연결되어 있기 때문에, ‘문제’는 처음 보이는 ‘해결자’에게 요구하고 기다리기만 하면 되기 때문에 누군가가 단독으로 문제와 매치되는 해결자를 판단할 필요가 없다. 문제와 매치되는 해결자를 판단하는 역할을 ‘문제’에게 맡기는 것은 부적절하다.
  • 동적으로 문제 해결의 순서 변경 가능. 유연성은 높지만 처리 속도는 느리기 때문에 요구와 처리자의 관계가 고정적이고, 처리의 속도가 중요할 때는 이 패턴을 안 쓰는 게 나을 수 있다. -> 순서를 잘못 구성하면 처리 속도가 대폭 느려질 수 있다는 단점이 기말 시험에 나올지도
  • 동전 교환기 예시: 10원 구멍, 50원 구멍 등 동전 크기별 구멍이 (기기 내부에) 크기 순서대로 있기 때문에 100원 동전이 10원 구멍에 들어갈 수 없고, 50원 동전에 500원 구멍에 들어갈 일이 없다.
  • 마지막까지 해결되지 않는 문제가 있을 수 있다. 이에 대해 마지막 해결자의 역할과 문제 처리가 중요하다.
• 기말고사 공지
  • 15주차에 본다
  • 자잘한 영단어는 시험으로 내지 않겠지만 패턴 이름 정도는 영어로 쓸 줄 알아야 한다
  • 답안지가 궁금하면 메일로 문의
• 다음 주 현충일 휴강