임베디드 소프트웨어

임베디드 시스템은 입력, 출력, 제어의 세가지 측면에서 생각하면 쉽다. 입력과 출력 그리고 제어의 과정이 간단한 경우에는 운영체제 없이 실현하는 경우가 다수이며, 그 외 복수의 애플리케이션 기능을 전환하거나 다양한 하드웨어 제어를 실시함으로써 실현되는 것은 고스펙의 하드웨어를 통제할 운영체제의 위에서 동작하는 경우가 많다.

임베디드 소프트웨어의 종류

• 운영체제 위에서 동작하는 타입 : 라즈베리파이3

  • 운영체제 외에 여러기능을 제공하는 Middleware가 존재한다.
  • 어플리케이션의 기능이 운영체재나 미들웨어에 준비되어 있을 경우, 절차를 작성하는 것만으로 실현이 가능함.

• 운영체제 없이 동작하는 타입 : 아두이노 우노

  • 운영체제가 없는 경우에는 실현 절차를 모두 작성해야한다.

임베디드 시스템은 하드웨어를 어떻게 사용하면 기능 요구사항을 만족할 수 있는지 검토하는 작업이 필요하다.

임베디드 소프트웨어를 개발하는 흐름

• 크로스 개발환경

개발하려고 하는 임베디드 시스템 스펙에 맞는 환경에서 빌드를 해야한다. 이러한 개발환경은 Cross Devolopment Environment라고 부른다. (개발하는 pc와 임베디드 환경이 같은 cpu를 사용하는 경우에는 동작이 가능하다.)

• 빌드

임베디드 시스템의 CPU 가 해석이 가능한 형태로 프로그램을 가공하는 작업

고급언어(c언어) 소스코드 -> (컴파일) -> 어셈블리어 -> (어셈블) -> OBJ 파일 -> (링크) -> 링크파일 -> (바이너리도구) -> HEX 파일

빌드 프로세스

avr-gcc -OS -Wall -mmcu=atmega328p main.c -o test.elf

아두이노 임베디드 소프트웨어 개발엣거는 avr-gcc 라는 도구를 사용한다. Preprocess-Compile-Link 순으로 처리되고 ELF파일이 만들어진다.

avr-objcopy -I elf32-avr -O ihex test.elf test.hex

만들어진 ELF파일을 avr-objcopy를 통해 HEX파일로 변환한다. 따라서 아두이노에서 실행가능한 임베디드 소프트웨어 파일이 만들어진다.

1. 프리프로세스

컴파일의 전단계로 C언어의 매크로를 전개하여 #include나 #ifdef 같은 directive 를 처리한다.

2. 컴파일

프리프로세싱 된 소스코드를 어셈블리어로 변환한다. CPU 레지스터나 memory map이 전개된다.

3. 어셈블리

어셈블리어로 변환된 결과를 OBJ 형식으로 변환한다. 라이브러리 사용시에는 OBJ파일 내에 라이브러리 제공 내용이 결여되어서 동작하지 않는다.

4. 링크처리

Object Code를 최종 실행가능한 실행파일로 만든다.

• 정적 링크 : 컴파일된 소스파일을 연결해서 실행가능한 파일을 만드는 것
• 동적 링크 : 프로그램 실행 도중 외부에 존재하는 코드를 찾아서 연결하는 작업 (링커가 필요하지 않음)

5. HEX 파일 변환

ROM기록을 위해 HEX파일로 변환을 수행한다.

메모리 맵

메모리 각 영역의 역할을 나타낸 것이며, CPU에 의존하여 소프트웨어 쪽에서 변경이 불가능하다.

• 코드 영역 : 읽기 전용, ROM 공간
• 메모리 영역 : 읽고쓰기 가능, RAM공간

스택

함수를 호출할 때, 이용되는 메모리 영역이며, LIFO로 이용된다. || |---| |반환값| |파라미터| |파라미터| |되돌아갈번지|

func함수를 호출하면 비어있던 스택이 위처럼 채워진다. func함수를 호출하기 전에 main함수에서는 스택 포인터를 조작해 되돌아갈 번지, 파라미터를 스택에 넣는다. func에서는 파라미터를 꺼내 반환값을 보관한다. 처리 종료 후에는 되돌아갈 번지를 꺼내어 main으로 돌아간다.

스택은 빈번히 사용되며, 함수안의 로컬변수 영역으로도 사용된다. 운영체제를 이용할 때는 사용영역에 제한이 있으므로 주의해야한다.

스택과 인터럽트

인터럽트가 발생하면 인터럽트 벡터에 등록되어있는 처리가 발생한다. 처리 실행 전에 인터럽트가 발생한 전의 프로세스의 번지를 스택에 넣는다. 따라서 인터럽트 수행 후에는 스택에서 해당 번지로 돌아간다.

인터럽트는 발생시기가 정확하지 않으므로 CPU 내부상태도 스택에 적재해야한다.

(1) 인터럽트 발생 → (2) 프로그램 카운터에 있던 처리 주소와 CPU의 시스템 레지스터, 범용 레지스터 내용을 스택에 저장한다. → (3) 인터럽트 벡터의 주소를 프로그램 카운터에 설정한다.

Embedded System Programming에서의 C

c언어는 고급 언엊이지만, 임베디드 시스템의 제약 사항으로 용량 혹은 처리시간 제약이 있기 때문에 컴파일러의 최적화 옵션을 사용하여 프로그램 구조를 최적화하여 제약사항을 준수한다.

Volatile 선언

• Polling

  주기적으로 하드웨어를 감시해 상태 변화를 감시하는 프로세스. 인터럽트 기능을 갖고 있지 않는 주변장치를 감시하기 위해 사용됨.

  → 주변장치의 레지스터 주소를 컴파일러는 모르기 때문에 문제가 생길 수 있음. 따라서 volatile 선언으로 최적화 하지 않도록 함.

• Unsigned (부호가지지 않음), Signed (음수표현)

  임베디드시스템에서는 unsigned, signed 여부가 중요하다. 주변장치의 레지스터는 비트로 표현되기 때문에, 의도하지 않은 값이 될 가능성이 있다. 따라서 하드웨어를 제어할때는 unsigned 타입을 이요해야한다.

  (예시)

  typedef struct{
    signed int control_bit: 1; //0이나 -1중 하나가 됨. 1을 되지 않음
  }
  typedef struct{
    unsigned int control_bit: 1; //0이나 1중 하나가 된다.
  }

• Pragma

  하드웨어나 메모리 주소를 직접 지정하여 데이터나 코드를 배치하고 싶은 경우 이용한다. 메모리 맴에 독자적인 섹션을 늘려서 배치가 가능하다. 다만 사용할 수 없는 컴파일러도 존재한다.

• Pointer & Array

  임베디드 시스템의 자원은 한정되어있기 땜누에, 하드웨어의 성능을 고려한 코딩을 해야한다. 포인터를 사용하게 되면 명령주의 단축이나 루프내 처리 명령도 줄어든다.

• 인터럽트 핸들러

  인터럽트 처리가 길어지면 일반 처리에 영향을 미친다. 인터럽트 핸들러 자체는 인터럽트 벡터에 대상 프로그램의 시작 주소를 등록함으로써 인터럽트가 발생했을 떄 cpu가 자동으로 전환해준다.

임베디드 시스템의 하드웨어에서 공통된 부분을 소개하고, 임베디드 시스템에서 소프트웨어를 동작시키기 위한 필요 지식에 대해 설명한다

하드웨어의 종류

• CPU
  • Bus를 통해서 명령을 전달하고 입력을 전달 받는다.
• Memory
  • ROM (Read Only Memory)
  • RAM (Random Access Memory)
• Peripheral(주변장치)

메모리의 종류

(1) ROM (Read Only Memory)

프로그램을 보관해 두고, CPU가 참조하여 동작을 수행한다. 제조공정에서 데이터를 써놓으면 바꿀 수 없는 MaskROM, 작성이 가능한 ProgrammableROM으로 나뉜다.

• ROM
  • MaskROM (명령코드, 상수 저장)
    • 제조공정에 데이터가 써지며, 삭제 불가함. 저렴
  • FlashMemory (명령코드, 상수 저장)
    • 전기적으로 저장하며, 재기록 가능하다.
  • EEPROM (명령코드, 상수 저장)
    • 바이트 단위로 삭제 가능하며, 용량이 적다.
  • EPROM (명령코드, 상수)
    • 자외선을 통한 저장, 재기록 가능
  • PROM (OTP)
    • 삭제 불가로 1회의 재기록 가능

(2) RAM (Random Access Memory)

데이터 보관과 무관한 기능을 전환할 때 사용되며, DynamicRAM (DRAM), StaticRAM(SRAM) 두 종류가 있다.

• RAM
  • SRAM
    • 전기적으로 기록,삭제하며 소비전류가 적다.
  • DRAM
    • 프로그램처리, 고밀도

버스의 구성

메인버스와 로컬버스로 나뉘며, 메모리 등의 고속 제어장치는 메인버스를 통해 CPU와 접속하며, 이외의 주변장치는 Bridge를 경유하여 CPU와 통신함.

메인버스

각종 버스 신호는 Clock(신호)에 의해 동기화되어 디바이스(메모리, 주변장치)에 지시를 전달하는데에 사용된다.

(1) 주소 버스 : 특정 디바이스에 접근하기 위해 이용하는 신호

(2) 데이터 버스 : 디바이스로부터 데이터를 읽어들이기 위한 신호

(3) 컨트롤 버스 : 디바이스 제어를 위한 신호선

로컬버스

메인버스의 클럭 속도보다 저속으로 동작하는 디바이스를 제어하는 신호선

(1) 브릿지

메인버스와 로컬버스를 연결하는 컨트롤러, FIFO룰 구현한 하드웨어 등에서, 저속의 로컬버스와 메인 버스 타이밍에 맞춰서 데이터를 송수신해주는 하드웨어

(2) UART

동기식 직렬신호를 병렬신호로, 혹은 역으로 변환하는 하드웨어. CPU로부터 8~16비트 폭으로 데이터가 병렬 전송되며, 이를 직렬 신호로 (Tx) 전송한다. 수신(Rx)에는 병렬로 변환 후에 송신한다.

UART 끼리 통신시에는 데이터의 시작과 긑을 데이터 사이에 신호로 보내어 송수신을 하며, 호스트 PC와 임베디드 시스템에 접속하여 시리얼 콘솔로 테스트나 디버깅할때 많이 사용된다.

(3) I2C

Serial Clock(SCL)과 Serial Data(SDA) 두개의 신호선을 사용하여 통신하는 동기식 직렬 통신. 마스터와 슬레이브가 있어서 복수 슬레이브에 연결이 가능하다. bit rate (초당 전송 비트수)는 표준(100Kbit/s), 저속(400Kbit/s), 고속(3.4Mbit/s)가 있다.

**동기식/비동기식**

동기와 비동기를 나누는 가장 큰 차이점을 어떻게 실행 순서를 가지는 지에 있다.

Syncronous 동기는 요청을 보낸 후 해당 요청의 응답을 받아야 다음 동작을 실행하는 방식을,

Asynchronous 비동기는 요청을 보낸 후 응답과 관계없이 다음 동작을 실행할 수 있는 방식을 의미한다.

(4) SPI

시리얼 커뮤니케이션을 하며, Serial Clock과 단방향 Seiral Data In (SDI), Serial Data Out (SDO)로 통신하는 동기식 직렬 통신. 복수의 슬레이브에 접속 가능하며, Slave Select를 이용하여 Slave 선택하여 통신. 많은 신호선이 필요하지만 I2C보다 빠르다.

Peripheral (주변장치)

(1) DMA (Direct Memory Access) Controller

CPU가 PIO(Programmed I/O)를 통해 메모리를 읽고 쓸수있지만, 자원관리를 위해서 DMA를 통해 CPU를 사용하지 않고 데이터를 읽고 쓴다. Bus Aribiter를 이용해서 데이터 충돌이 없이 DMA 가 데이터 처리를 하도록 돕는다.

데이터 전송 도중에 버스를 점유하여 메모리 엑세스가 늦어질 수 있으므로, 전송 설정 (주소, 사이즈)를 잘 설정해야한다.

(2) Timer

Peripheral의 지속적인 감시 혹은 주기적 데이터 출력을 위한 시간 관련 처리에서 필수적이다. 카운터라고 불리는 레지스터에 주기 시간을 설정하고, 시간 경과하면 Interrupt발생. CPU는 해당 인터럽트를 통해서 프로그램을 동작시켜 주기적 처리를 실현함.

(3) RTC (Real Time Clock)

시간관리 장치. CPU 정지후 재개시 정확한 시간을 제공

(4) GPIO (General Perpose Input/Output)

CPU에 직접 연결되어 입력 및 출력을 범용으로 사용되는 포트. 외부의 주변장치로부터 인터럽트 신호에 사용되는 등 범용적으로 IO에 이용 가능하다.

제어방식

대다수 CPU의 Resigster라는 제어용 메모리를 사용해서 제어함. CPU 관점에서 레지스터 제어는 Memory mapped I/O와 I/O mapped I/O가 있다.

https://code-lab1.tistory.com/204

• Memory Mapped I/O :

  ROM, RAM과 공통 주소를 이용하여 특정 주소에 대해 읽고 씀. ROM,RAM과 마찬가지로 주변장치의 레지스터도 메모리로 취급함.

• I/O Mapped I/O

  I/O 맵드 I/O의 경우, ROM, RAM는 메모리 공간으로 취급하고, 주변장치의 레지스터는 전용 명령으로 제어한다.

  
  

CPU란

ROM으로 부터 실행해야할 절차를 읽어들이며, 읽어들인 절차를 해석해서 실행한다. 실행 결과는 RAM등에 보관한다.

• Progrm Counter

프로그램 카운터는 ROM내의 프로그램의 어디를 참고할지 관리함. Program Counter는 CPU 명령의 보관장소를 관리하여, 다음에 실행해야할 명령을 읽을 위치를 CPU에 전달하는 역할을 함.

• Decoder

불러온 명령을 해독하여 ALU에서의 연산이나, 데이터의 이동등 구체적 지시를 CPU내에서 실행한다.

• ALU

정수의 사칙연산 혹은 AND, OR, NOT 등의 논리연산을 실행함. ALU에서 연산을 수행한 후에는 범용 레지스터나 시스템 레지스터에 반영한다.

• General Purpose Register (범용레지스터)

CPU에 내장된 범용 메모리로, 고속이지만 용량이 작아 일시적으로 이용된다. ALU의 연산결과를 보관하거나 데이터를 이동할 떄의 보관장소로 이용된다.

• System Register (시스템 레지스터)

CPU 명령 실행을 위해 이용되며, 명령을 보관하는 명령 레지스터, 주소 관리용 주소 레지스터, CPU상태 관리용 플래그 레지스터 등이 있다.

CPU 명령실행

1. 명령 패치 사이클 : ROM에서 명령 추출
2. 명령 디코드 사이클 : 추출한 명령 해독 및 실행준비
3. 실행 사이클 : 명령 실행
4. 라이트 백 사이클 : 명령 실행 결과의 반영

CPU 명령의 종류

데이터 취급 명령의 대부분은 범용 레지스터를 활용함. 범용 레지스터의 데이터를 메모리에 기록하거나, 메모리에 있는 데이터를 범용 레지스터로 읽어 들인다.

• CPU와 메모리 사이의 데이터 교환명령
• CPU와 주변장치 사이의 데이터 교환명령
• CPU 내부명령

인터럽트

주변장치로 부터의 처리요구를 CPU에 통지하기 위한 신호이다. 인터럽트는 interrupt vectro table에 저장되며, 미리 정해진 프로그램에 맞게 점프한다. 인터럽트 처리 종료후에는 일상적 동작을 재개한다.

인터럽트의 종류

• 타이머 인터럽트

  소정의 시간이 되면 인터럽트를 발생시키는 의도를 가지고 사용함

• 외부 인터럽트

  주변장치의 상태에 따른 인터럽트

인터럽트의 종류에는 타이머 처리, DMA 처리, 스위치 처리, 렌더링 처리, 시리얼 처리 가 있다. 인터럽트 벡터에는 처리 그 자체를 등록하는 것이 아니라 메모리 주소를 저장한다.

인터럽트 우선순위

인터럽트 처릴 순서를 위해서 우선순위를 정해야한다. 인터럽트의 우선순위를 지정해두고, 인터럽트 벡터에 프로그램 번지를 등록한다. 특정 CPU에는 우선순위를 위한 레지스터가 있다.

4개의 맞물린 톱니바퀴가 있다. 각 톱니에는 자성(N극, S극)이 있고 지정된 톱니가 지정된 명령대로 회전한다. 그 결과를 구하라

조건

문제는 간단하게 생각할 수 있는 문제였다.

확실히 과거 삼성 기출이 지금보다 훨씬 쉬운거 같다..

1. 톱니바퀴는 1,2,3,4 순으로 놓여져 있다.
2. 옆의 톱니바퀴가 회전하면 그 다른 톱니바퀴는 다른 방향으로 회전한다.
3. 각 톱니는 극성이 있는데 (N극 S극) 마주하는 극이 같으면 회전하고, 그렇지 않다면 정지한다.
4. 명령에 따라 회전을 했을때, 최종 톱니바퀴의 12시 방향의 극성으로 점수를 계산하여 반환하라

Solution

필요했던 함수는 크게, 톱니를 회전시키는 함수, 회전 가능한지 확인하는 함수, 실제로 한 톱니가 돌았을 때 결과. 세가지가 필요했다.

rotate() -> List

우선 톱니가 회전한 결과를 반환하는 함수 rotate()를 작성했다.

def rotate(g : list, direction : int) -> list:
  """
  g :  gear list 
  direction : rotate direction, 1 : 시계방향, -1 반시계 방향
  return : rotated g
  """
  new_g = []
  if direction == 1:
    new_g = [g[-1]] + g[0:-1]
  elif direction == -1:
    new_g = g[1:] + [g[0]]
  return new_g

여기서 했던 실수중의 하나가, 톱니들이 0번 톱니 (12시 방향)부터 시계방향으로 리스트에 극성이 담긴 형태인데, 슬라이싱을 이용했더니, g[0] 혹은 g[-1]이 값이어서 브라켓을 씌워서 리스트화 한다음 남은 부분과 더하기 했다. (이 방식이 메모리 측면에서는 좋지 못하다는 정보를 봤다)

movable() -> Boolean

다음은 마주보는 톱니를 이용해서, 기준이 되는 톱니 base와 compare를 이용해서 기준 톱니 기준 왼쪽인지 오른쪽인지 여부에 따라서 Boolean값을 반환하는 함수 movable을 작성했다.

def moveable(base : list, compare : list, direction : int) -> bool:
  """
  base : 기준이 되는 톱니
  compare : 움직일 톱니
  direction : base 기준 compare 위치, 
              1 : 왼쪽, 
              -1 : 오른쪽
  """
  # 왼쪽과 비교
  if direction == 1:
    return base[6] != compare[2]
  # 오른쪽과 비교
  elif direction == -1:
    return base[2] != compare[6]
  return "error"

처음에는 비트 연산 ^를 사용했는데, 그냥 달라야지만 움직이는 것으로 변경했다. (또 오른쪽 왼쪽 설정한걸 헷갈려서...오류가 있었다)

iteration() -> list

마지막으로 하나의 톱니가 돌았을때, 양 옆을 보며 톱니를 회전시키는 함수를 작성했다. 우선 오른쪽, 왼쪽을 나눠서 본다. 이때 코드가 중복되어 수정을 해보는 방안을 고민해 봤는데, 굳이 싶어서 그냥 두번 적었다. (사실 이런건 기술부채인가요...)

def iteration(gear : list, command : tuple) -> list:
  """
  gear : gear list
  command : (gear number, direction) direction, 1 : 시계방향, -1 반시계 방향
  """
  g, base_dir = command[0] -1, command[1]
  rotation = [(0,0)] * 4
  rotation[g] = (1, base_dir)

  # g 기준 왼쪽 오른쪽 분리 (인덱스로)
  left = [0,1,2,3][:g][::-1] # 역순으로 슬라이싱해서 루프 돌리기 편하게 함
  right = [0,1,2,3][g+1:]

  base = gear[g]
  dir = base_dir
  # base 기준 왼쪽
  for idx in left:
    if moveable(base, gear[idx], 1):
      base = gear[idx]
      dir = dir * -1
      rotation[idx] = (1, dir)
    else:
      break

  # base기준 오른쪽
  base = gear[g]
  dir = base_dir
  for idx in right:
    if moveable(base, gear[idx], -1):
      base = gear[idx]
      dir = dir * -1
      rotation[idx] = (1, dir)
    else:
      break

  new_gear = []
  for idx, g in enumerate(gear):
    if rotation[idx][0]:
      new_gear.append(rotate(g, rotation[idx][1]))
    else:
      new_gear.append(g)

  return new_gear

여기서 코드가 중복되면서 발생했던 문제점은, 기존 톱니가 도는 방향을 dir이라는 변수에 저장했다 (변수명도 적절한 것은 아닌거같다). 이때 왼쪽 기준으로 회전방향에 -1 을 곱해가면서 변경했는데, dir을 다시 기존 방향으로 갱신했어야 하는데 누락되어서 저 멀리 있는 톱니가 돌아가는 불상사가 벌어졌다. Movable 하지 않으면 바로 루프를 탈출한다.

Sol() -> int

최종적으로 위의 조건처럼 12시의 톱니를 이용하여 최종 점수를 환산한다.

def sol(gear, K, move):
  for i in range(K):
    gear = iteration(gear, move[ i])

  return gear[0][0] + 2 * gear[1][0] + 4 * gear[2][0] + 8 * gear[3][0]

전체코드

# 톱니바퀴 https://www.acmicpc.net/problem/14891 

import sys

def InputData():
  readl = sys.stdin.readline
  gear = [[int(x) for x in readl().strip()] for _ in range(4)]
  K = int(readl())
  move = [tuple(map(int, readl().split())) for _ in range(K)]

  return gear, K, move


def rotate(g : list, direction : int) -> list:
  """
  g :  gear list 
  direction : rotate direction, 1 : 시계방향, -1 반시계 방향
  return : rotated g
  """
  new_g = []
  if direction == 1:
    new_g = [g[-1]] + g[0:-1]
  elif direction == -1:
    new_g = g[1:] + [g[0]]
  return new_g

def moveable(base : list, compare : list, direction : int) -> bool:
  """
  base : 기준이 되는 톱니
  compare : 움직일 톱니
  direction : base 기준 compare 위치, 
              1 : 왼쪽, 
              -1 : 오른쪽
  """
  # 왼쪽과 비교
  if direction == 1:
    return base[6] != compare[2]
  # 오른쪽과 비교
  elif direction == -1:
    return base[2] != compare[6]
  return "error"

def iteration(gear : list, command : tuple) -> list:
  """
  gear : gear list
  command : (gear number, direction) direction, 1 : 시계방향, -1 반시계 방향
  """
  g, base_dir = command[0] -1, command[1]
  rotation = [(0,0)] * 4
  rotation[g] = (1, base_dir)

  # g 기준 왼쪽 오른쪽 분리 (인덱스로)
  left = [0,1,2,3][:g][::-1] # 역순으로 슬라이싱해서 루프 돌리기 편하게 함
  right = [0,1,2,3][g+1:]

  base = gear[g]
  dir = base_dir
  # base 기준 왼쪽
  for idx in left:
    if moveable(base, gear[idx], 1):
      base = gear[idx]
      dir = dir * -1
      rotation[idx] = (1, dir)
    else:
      break

  # base기준 오른쪽
  base = gear[g]
  dir = base_dir
  for idx in right:
    if moveable(base, gear[idx], -1):
      base = gear[idx]
      dir = dir * -1
      rotation[idx] = (1, dir)
    else:
      break

  new_gear = []
  for idx, g in enumerate(gear):
    if rotation[idx][0]:
      new_gear.append(rotate(g, rotation[idx][1]))
    else:
      new_gear.append(g)

  return new_gear

def sol(gear, K, move):
  for i in range(K):
    gear = iteration(gear, move[ i])

  return gear[0][0] + 2 * gear[1][0] + 4 * gear[2][0] + 8 * gear[3][0]


gear, K, move = InputData()
print(sol(gear, K, move))

i,j가 함께 팀이 되었을때의 능력치는 S[i][j] + S[j][i]이다. 두팀의 능력치 합이 최소가 되는 경우를 구하라

기본적인 조합 문제였던 것 같다. N명의 사람들을 어떻게 반으로 나누는 모든 조합을 구할까 고민이 가장 컸는데, DFS를 이용해서 조합을 구하고, 전체 인원에서 해당 조합을 빼는 방식을 쓰기 위해서 리스트를 set으로 변환해줬다.

조건은 간단하다

• S에는 i가 j와 내는 능력치 S[i][j]가 저장되어있다.
• S[i][j] 는 S[j][i]와 다를 수 있다.

우선 DFS를 이용하여 조합을 구한다.

def dfs(start, array, count):
  global N, grid, team_list, minScore

  if count == N//2:
    team_list.append(set(tuple(array)))
    return

  for x in range(start, N):
    dfs(x + 1, array + [x], count + 1)

그다음 각 조합별로 전체 선수의 set에서 빼서 start팀 link팀을 따로 구성하여 점수합 차를 구한다.

eam_list = []
min_score = float("inf")
dfs(0, [], 0)
all_player = set(tuple([x for x in range(N)]))

for start in team_list:
  score_start, score_link = 0, 0
  link = tuple(all_player - start)
  start = tuple(start)

  for i in range(N//2):
    for j in range(N//2):
      if i == j:
        continue
      score_start += grid[start[i]][start[j]]
      score_link += grid[link[i]][link[j]]

  min_score = min(min_score, abs(score_start - score_link))

이렇게 하면 꽤나 간단하게 구할수가 있다.

전체코드는 아래와 같다.

import sys

def InputData():
  readl = sys.stdin.readline
  N = int(readl())
  grid = [list(map(int, readl().split())) for _ in range(N)]

  return N, grid

def dfs(start, array, count):
  global N, grid, team_list, minScore

  if count == N//2:
    team_list.append(set(tuple(array)))
    return

  for x in range(start, N):
    dfs(x + 1, array + [x], count + 1)


N, grid = InputData()
team_list = []
min_score = float("inf")
dfs(0, [], 0)
all_player = set(tuple([x for x in range(N)]))

for start in team_list:
  score_start, score_link = 0, 0
  link = tuple(all_player - start)
  start = tuple(start)

  for i in range(N//2):
    for j in range(N//2):
      if i == j:
        continue
      score_start += grid[start[i]][start[j]]
      score_link += grid[link[i]][link[j]]

  min_score = min(min_score, abs(score_start - score_link))

print(min_score)

주어진 조건대로 경사로를 이용하거나 그냥 통행할 수 있는 길을 구하라

문제의 설명 때문에 이해하는데에 오래 걸렸던 문제이다.

• N x N 행렬이 존재할 때, 각 행, 열을 지나 갈 수 있는지 여부를 판단한다
• 각 셀에 적힌 수 (10 보다 작거나 같은 자연수) 는 높이를 뜻하며, 셀 간의 높이가 1 차이일 때 경사로를 설치 할 수 있다.
• 경사로는 L의 밑변을 가지며, 경사로는 겹쳐질 수 없다. (아래 그림 과 같이)

행렬이 주어질 때, 지나 갈 수 잇는 길의 개수를 구하는 프로그램을 작성하시오

각 행, 열을 판단해야하는 문제인데 겹치지 않는 경사로에 현혹되어서, 한 행에 경사로가 설치되면, 그 행을 지나는 열의 경로에는 경사로를 못 넣는 것으로 생각해서 너무 어려웠다. 하지만 그냥 각 행과 열을 따로 생각하는 문제...(급격히 쉬워짐)

각 행과 열을 생각했을 때, 고려해야하는 부분은 이것이다.

1. 인덱스 0부터 시작하여서 높이가 다른 셀을 만났을 때, 낮은 곳이 L 보다 같거나 큰 개수로 이어져야한다.
2. 높아졌을 떄는, 낮은 것이 얼마나 이어졌는지 기록한다.
3. 낮아졌을 때는, 이후에 L 이상으로 길이가 같은지 확인한다.
4. 매번 경사로가 겹치지는 않는지 확인한다.

일단 높아지건 낮아지건 블럭이 1차이가 나야 의미가 있다.

또 가장 신경 썻던 부분은, 통행 가능 한지 였으므로 못찾는다면 바로 0을 return 하도록 했다.

높아질때는, 받침보다 길게 이어지는지와, 그 구간에 경사로가 있는지를 확인한다

if abs(prev - current) == 1:
      # 1 높아질 때
      if prev + 1 == current:
          # 만약 받침보다 길게 이어진다면
        if count >= L:
        # slope에 경사로 저장 부분을 확인.
          if slope[i-L:i] != [0] * L:
            return 0
          # 경사로를 두고 저장
          slope[i-L:i] = [1] * L
        else:
          return 0

낮아 질때는, 그 다음 구간이 범위 (N)을 넘어서는지, 그리고 경사로가 겹치지는 않는지, 해당구간이 연속되는지 여부를 봤다.

elif prev - 1 == current:
        # 범위를 벗어나지 않는지 확인
        if i + L <= N:
          # 겹치는 경사로가 있는지 확인
          if line[i: i+L] == [current] * L:
            slope[i: i+L] = [1] * L
          else:
            return 0
        else:
          return 0

따라서 전체 풀이는 아래와 같다.

def check_if(N, L, line):
  prev = 0
  count = 0
  slope = [0] * N
  available = True
  # 인덱스 0부터 순회함
  for i in range(N):
    current = line[i]
    # 첫칸이거나, 이어질때 prev를 두고 갯수를 기록한다.
    if not prev or prev == current:
      prev = current
      count += 1
      continue
    # 더 높은 블럭이 1차이 나야함
    if abs(prev - current) == 1:
      # 1 높아질 때
      if prev + 1 == current:
          # 만약 받침보다 길게 이어진다면
        if count >= L:
        # slope에 경사로 저장 부분을 확인.
          if slope[i-L:i] != [0] * L:
            return 0
          # 경사로를 두고 저장
          slope[i-L:i] = [1] * L
        else:
          return 0
      # 1 낮아질 때
      elif prev - 1 == current:
        # 범위를 벗어나지 않는지 확인
        if i + L <= N:
          # 겹치는 경사로가 있는지 확인
          if line[i: i+L] == [current] * L:
            slope[i: i+L] = [1] * L
          else:
            return 0
        else:
          return 0
      # 경사로 만들고 다시 진행
      prev = current
      count = 1
    # 차이가 1보다 크면 못건넘
    else:
      return 0
  return 1


def sol():
  result = 0
  for i in range(N):
    result += check_if(N, L, grid[i])

  for j in range(N):
    line = [grid[x][j] for x in range(N)]
    result += check_if(N, L, line)

  print(result)

sol()

1. S/W의 힘으로 세계 최고 초전도 화질 달성

LG전자 채명석 책임 연구원

SW 개발자로써 HW영역의 화질 분야를 접근하는 과정

초전도 화질이란? 연구원 본인이 만든 용어로, "저항을 0으로 만든다"의 개념에 입각하여 비디오 월의 멀티 비전 스크린에서도 눈으로 볼떄 하나의 디스플레이로 보는 것과 같이 거부감이 전혀 느껴지지지 않는, 시각 인지의 저항 없는 균일한 화면의 상태 를 뜻 한다.

비디오 월은 다양한 모니터 혹은 패널들의 조합으로 제작하는 만큼 각각의 통일성이 무척 중요하다.

• LCD/OLED 사이니지 비디오 월 : 모니터와 같은 기기들을 이어붙여 하나의 화면처럼 동작하도록 한다. 다만 테두리들의 존재로 검은선과 같이 나타나여 합일성이 좀 떨어진다는 단점이 있다.

• LED 사이니지 비디오월 : 패널 위에 LED를 이용하기 때문에 패널들간의 통일성은 무척 뛰어나나, LED 패널 내의 LED간의 단차로 인해서 밝은 부분, 어두운 부분이 존재하여 이슈가 존재한다.

LED 사이니지 비디오 월의 문제를 해결하기 위하여 이해야하는 디스플레이 성능지표에서의 성능지표는 위 블로그에서 아주 설명이 잘 되어있다.

사람의 눈은 하나의 색을 볼때는 이후의 색과 차이를 크게 못느끼지만, 특정색과 비교를 하게 되면 그 차이를 쉽게 찾아낸다. 따라서 LED 패널에서의 미세한 차이 (RGB 1정도)도 눈에 크게 차이 나는 것처럼 보이기 때문에 중요한 해결 과제이다. 경계면에 그라데이션을 적용하면 해결되기도 한다.

LED Signage Calibration

Pixel Calibration

광원 각각 (UHD Screen : 3940 x 2160 x 3 = 24,883,200 개의 광원) 을 Calibration을 한다. 특히나 광원마다 온도의 변화로 밝기 또한 변한다. 심지어 LED에서의 발열로 인해, 화면 얼룩현상은 더 심화될 수 있다.

아쉽게도 배경지식에 대한 설명이....길어서 세션 시간을 넘겨 해결방안을 못들었다..(실화냐)

2. ThinQ 데이터 큐레이션 & 개인화 시스템

개인화 서비스를 위해서는 정말 많은 요소들이 필요하다. Data Engineering부터 MLops, Data Science 등 거의 대부분 Data 비즈니스의 Engineering 과정이 필요하다.

여기에서 드는 기술적인 비용과 부하도 대단하지만 실제 문제는 따로 존재한다. 바로 사용가능한 데이터의 양의 부족이다. 실제 ThinQ에서의 데이터는 월단위로 TB단위로 쌓이지만, 본질적인 고민을 했을 때 우리는 어쩌면 MB단위의 데이터만 필요하지만 실제 사용가능한 좋은 데이터는 없는 것이 아닌가 라고 생각한다.

달성해야하는 과제

1. 고품질, 고활용성, 표준화 된 Curation Data 확보
2. 비용 효율적인 데이터 생성
3. 고객 Engagement 높이기 위한 개인화 시스템 확보
4. 룰 기반 탈피, 빠르고 효과적인 개인화 모델 구축

ThinQ 데이터 큐레이션

현재 사내에서 다루는 데이터는 ThinQ 사용 Data등 다양한 데이터가 있지만, 그 안에서 압도적인 양을 차지하는 데이터는 기기 데이터이다.

현재 LG전자에서는 많은 제품을 제작하지만, 같은 제품군에서도 많은 모델이 존재한다. 다양한 모델이 존재하고 기능이 다른 만큼 발생되는 데이터가 무척 방대하다.

기존에는 데이터를 Case by Case로 데이터를 한정 활용했다. 기기의 Raw Data를 필요에 따라 Parsing을 수행하고 이용하였다. 따라서 중복적으로 데이터를 각 부문에서 가공하고 이용하는 부문에서 효율성이 많이 떨어졌다.

데이터 큐레이션이란

흔히들 사용되는 Data Engineering 프로세스인 것 같다. + 도메인지식

데이터를 효율적으로 사용하기 위해, 수집/정리/가공을 기반으로 목적성 있는 표준화 된 데이터를 만드는 것이다. 파싱을 통해 제품의 Raw데이터를 해석하고, 전처리를 통해 제품별로 표준화를 수행한다. 이런 데이터를 지수화하여 Insight를 반영하고 모든 구성원들이 접근하여 직접 활용 할 수 있는 수준까지 만드는 과정을 거친다.

• L0 Data : Raw (제품 본연 데이터)
• L1 Data : Parsed
• CL2 Data : Preprocessed (사영성 기반 분석 나응, 데이터 활용의 전처리 Load 절감)
• CL3 Data : Profitting Data (Insight 반영한 지수화 데이터, 마이크로 새그멘테이션 직접활용)

이러한 과정에서 얻을 수 있는 가장 큰 이득은, TB규모의 데이터를 가공을 거침에 따라 GB 심지어는 MB 수준까지 데이터의 규모를 감소시킬 수 있다는 점이다.

대용량 데이터 처리를 위한 Solution

Spark on EKS 도입을 활용하여 비용적인 부분을 해결하기 위해 노력하고 있다. 비용 효율 극대화를 위해서 Spot Instance를 사용한다.

사업부마다 필요 데이터와 데이터 처리 로직이 다르다. 이런 문제점의 해결방법은 각 조직별 로직을 pod화 하여 EKS상에서 운영하는 정책을 도입했다. Aurora DB나 Athena 를 이용하여 운영하는 솔루션을 채택했다.

Apache Airflow를 이용한 스케쥴링을 통해서 데이터를 체계적이고 직꽌적으로 관리하기 위해서 노력한다. 특히 데이터 특성에 따른 스케쥴링에 집중하였고, 유지보수를 위해서 MS Teams를 통해 장애알림을 즉각적으로 받을 수 있도록 노력한다.

Personalization

아직까지도 많은 문제가 존재하여 ML보다는 룰기반에 의존하고 있지만 ML Solution 적용을 노력하고 있다. 하지만 cold start 문제와 bias 문제를 해결하는 문제들이 존재한다. 따라서 MLaaS를 도입하여 (AWS SageMaker, MS Azure ML)등을 통해서 해결하는 방안도 고려하고있다.

3. DevSecOps 보안 적용 사례

서혁준 팀장

추진 배경

보안공역이 점점 증가하고 있다. 클라우드 IaaS에서 SaaS로, 웹에서 API endpoint로 공격 표면 영역이 넓어지고 있다. 따라서 다수의 사업자들과 글로벌 서비스에서 취약점들이 발견되고 있거나 사고가 벌어지고 있다.

따라서 기존의 웹 공격을 넘어 SW공급망, API엔드포인트, 소스코드, 클라우드 공격에 적극 대응해야한다.

• 종속 외부 라이브러리 : sw공급망을 OSS약점코드, 취약점 공격
• API Gateway : API 신규 포인트 공격
• Opensource : Log4J 이후로 관심도가 높아지나 했으나, 커뮤니티 등 취약
• 소스코드(웹) : PHP로 쓰여진 코드들이 쉽게 공격당함

이러한 다양한 분야에서 신규 보안 취약점들이 발견됨에 따라, SaaS서비스 운영자의 보안 책임이 더 높아졌다. 개발시 Q-Gate 보안을 준수했다 하더라도, 운영 시 형상 변경으로 인한 보안취약성을 관리 통제하여야 한다.

→ 소스 정적점검, 오픈소스 취약점점검, 모의해킹, 동적 점검, API 보안점검

DevSecOps 보안 프로세스

예산과 인력을 고려하여 SW 운영 보안 활동을 식별하고, 각 활동의 세부 프로세스를 기술 관리적으로 정의

정적분석

배포 단계에서 자동 실행되도록 하고, 취약점이 수정되어야 운영에 배포되도록 통제 (SonarQube와 Checkmarx 를 조합하여 넓은 룰셋을 이용)

• 코드 커밋한 뒤 Jenkins의 트리거로 정적분석이 자동 실행되고, 취약점 자동 취합
• 심각/높은 등급의 취약점은 개발자가 수정 후 운영 배포 가능
• KISA 49개 보안 약점 기준 기본 룰 외에, 커스텀 룰을 추가하여 품질 개선

동적점검 & 모의해킹

전문가 모의 해킹과 동적점검의 장단점을 혼합하여 반복 수행 가능하도록 구성하고 의미 있는 취약점을 발견

• 전문가가 수립한 시나리오 기반으로 모의해킹을 수행. 대상은 in-hous SW 필수, 솔루션 SW는 선택적으로 수행한다.
• Python 프로그래밍, N-map을 활용하여 자동화. ZAP과 Burp Suite 플러그인 이용하여 재개발

DevSecOps 적용 성과와 과제

점검경롸가 빠른 주기로 중앙 집계되어 정량화되고, 보안 위험이 가시화됨에 따라 변화의 트리거가 됨.

현업 개발 조직의 시큐어 코딩 인식이 재고됨

• CI/CD 단계에서 자동 점검되어 배포가 중단되므로 개발자는 시큐어 코딩에 더욱 관심을 가지게 됨
• 시큐어 코딩 플랫폼을 이용하여 교육을 실시 후 평가한 결과, 점검 항목별 50%-90% 수준으로 이해하고 있음.

DevSecOps

• DevSecOps는 개발 프로젝트의 DevOps 적용이 전제되어야 함 (취약점 수정 가능한 개발자 필요, CI/CD 연동)
• 보안팀과 개발팀의 높은 업무 피로도를 감소시켜야 함 (예: 오탐 최소화)
• 23년은 프로세스 정착의 해였다면, 24년은 개발자 인식의 개선, 조치 리드타임 줄이기, 점검 자동화를 고도화하여 DevSecOps 성숙도를 높여야 함.

1. Keynote

초거대 AI 시대, 신뢰할 수 있는 AI의 경쟁력

LG AI 연구원 배경훈 원장

AI는 사실에 기반으로 진단하는 영역으로 뻗어나가야한다. 신뢰성 높은 데이터로 적은 파라미터로도 좋은 성능을 낼수있는 엑사원을 만들겠다. 나아가 중장기로는 미래 예측 및 자율 실행 가능한 AI Agent로의 Path를 계획할 것이다.

• 데이터의 신뢰성, 전문성이 현업 적용 여부를 결정한다.
• 데이터 생성 및 활용의 순환 체계 통한 Customized Model 생성
• 산업 분야별 실질적 성공사례를 창출

2012년 이후로 딥러닝이 산업에 부상하였지만, 다양한 문제 (컴퓨테이션 케파의 부족과 비용)으로 인해 비즈니스적인 회의가 존재했다. 하지만 생성형AI인 ChatGPT의 등장으로 생성형 AI의 비즈니스적인 가능성을 다시 볼 수 있었다.

<생성형AI 시장이 과열되는 이유는 뭘까?> 나스닥 시총 상위 테크기업 모두 LLM 개발/서비스에 참여하면서, 국내의 기업들도 자체 LLM 개발에 참여하고 있다

• LLM : LG, SKT, KT, 네이버, 카카오
• sLLM : 마음AI, 엔씨소프트, 42Maru, 코난텍, 올거나이즈, 솔트룩스, 업스테이지, 스켈터랩스

생성형 AI에서 뒤쳐지는 것이 곧 시장에서 뒤쳐지는 것이라고 판단하여 많은 기업들이 개발에 뛰어들고있다. 그렇다면 이러한 회사들이 목표로하는 문제해결은 뭘까?? 그에대해서는 아직 많은 의문들이 존재한다.

OpenAI는 Genereal Intelligence를 표방한다. 하지만 이를 이룩하기 위해서는 아직도 많은 시간이 걸릴 것이라고 생각한다. 이러한 한계를 인식한 LG AI 연구원은 Vertical한 지식분야에 대한 Expert Model을 제작하는 것을 목적으로 하고있다.

<데이터 부족과 가공에 대한 기회비용 문제가 여전히 존재한다.>

딥러닝 자체의 능력은 점점 뛰어나지지만, 특정한 테스크에 맞게 데이터를 생성, 가공하는데에는 많은 시간과 비용이 필요하다. LG AI연구원에서 엑사원을 충분히 만들 수 있다면, LG AI연구원은 데이터 생성으로써의 비즈니스 가치를 꾀할 수도 있다.

<Hallucination과 Bias> 현재 많은 생성형 AI가 이러한 문제를 가지고 있다. LG AI는 다량의 데이터셋을 확보하는데에 많은 노력을 기울였지만, 편향문제를 해결하기 위해서 검색부분에서 기존의 생성형 검색 시스템과 다른 부분을 표방한다.

Exaone은 전문분야에 대한 코퍼스를 따로 클러스터를 형성하고, 이에 대해서 Reasonable하게 지식을 추론한다. 따라서 문서 내에서 질문을 할때, 참조한 부분 또한 제공할 수 있다.

2. Retrieval QA / Knowledge Graph QA

** LG전자 이대연 책임연구원 **

대화형 QA : 대화의 문맥을 적절히 이해하여 적절하게 응답하는 시스템

• 문맥 이해
• 양방향 상호작용
• 지속적인 학습
• 다양한 응용

→ Generative AI는 질의응답 벤치마크에서는 그다지 높은 성적을 보여주지 못한다.

Conversational Question Retireval (cQR)

cQR에서 중요한 것은 Coreference Resolution 이 중요하다. 생략어의 사용비율이 높기 때문에 한국어는 Anaphora Resolve 하기가 쉽지 않다. → GPT를 이용하면 Zero shot 해결이 가능하긴 하다.

cQR의 경우에는 Closed Domain이 아니라 Open Domain 영역이기 때문에, 모델의 크기가 대규모여야한다. 이러한 도메인의 차이 때문에 벤치마크 성적은 실제 비즈니스 적용에 괴리가 발생하게 된다. 따라서 도메인 타게팅을 Open Domain으로 해야한다.

Retrieval

• Term Search : Term에 Robust하지만, 비용이 많이 들고 유연하지 못한다.
• Semantic Search : 유사의미간 벡터 유사도가 높아 작은 차이를 인지하지 못한다.

따라서 Hybrid Search를 이용하여 Term Based Search와 Semantic Search의 장점을 결합한다. 실제로 BM25(Term기반)나 Ada(Semantic기반) 보다 조금 더 높은 결과를 보여줬다. 고무적인 부분이라 하자면 질문들에 대한 유사질의에서 압도적인 정확도를 보여주었다.

3. UP가전 2.0: 새로운 SW와 DSL - 플렛폼 전환과 SW설계 솔루션

UP가전 : Upgradable 가전으로 사용자 맞춤형 및 업데이트 가능 가전

플렛폼 전환

기존의 SW는 One Binary SW인 문제점을 가지고 있다. 이러한 문제점이 야기하는 것은 몇가지가 있어 UP가전 생성을 위해서는 SW 구조 수정이 필요하다.

• 기능단위 Upgrade가 어렵다 (Binary 전체 교체를 야기)
• One Binary SW 종수가 너무 다양하겍 늘어난다.
• 기능의 개인화가 쉽지 않다. (고객이 원하는 기능만 고른다면 기능의 조합이 무수함)

따라서 RT-OS 탑재와 HW Topology를 변경하고 전용 칩을 적용하였다.

Domain Specific Language 적용

코드 편찬을 가능하게 하여, 코드 간편화 (코드 600줄가량에서 100줄가량으로 감소, 7레이어에서 2레이어 코드로 변화)

Transformer

Transformer는 큰 범주에서 인코더 디코더로 나누어져있다. 두 불록은 디테일에서 차이가 있을 뿐, 본질적으로 크게 다르지 않다.

Encoder

인코더의 입력은 Input Embedding과 Positional Encoding을 더해서 만들어진다.Input Embedding은 BPE (Byte Pair Encodding)을 사용한다. Positional Encoding은 문장 내에서의 단어 위치를 나타낸다. 이렇게 만들어진 입력은 Encoder의 첫번째 입력이 되며, 해당 Encoder의 출력은 두번째 Encoder의 입력이 된다. 이를 N번 반복한다.

Output Layer

출력층의 출력은 타깃 언어의 어휘 만큼의 차원을 갖는 확률 벡터가 된다 (Softmax의 결과). 트랜스포머의 학습은 인코더와 디코더의 입력이 주어졌을 때, 모델의 최종 출력에서 정답에 해당하는 단어의 확률값을 높이는 방식으로 수행된다.

Self Attention - Encoder

(1) Query, Key, Value 만들기

셀프어텐션은 Query(쿼리), Key(키), Value(벨류) 요소 사이의 문맥적 관계성을 추출하는 과정이다. X라는 시퀀스가 있을 때, 행렬 곱을 이용해서 아래와 같이 Q, K, V를 만든다. (이떄 시퀀스가 n개 이면 $ n * 3$ 개의 벡터가 생성된다.

$$ Q = X \times W_Q $$ $$ K = X \times W_K $$ $$ V = X \times W_V $$

(2) 셀프 어텐션 출력값 계산하기

$$ Attention(Q,K,V) = softmax(\frac{QK^T}{\sqrt d_k})V $$

Query와 Key를 행렬곱한 뒤, 해당 행렬의 모든 요소 값을 Key 차원수의 제곱근 값으로 나누워주고, 이 행렬을 Row 단위로 Softmax를 취해 스코어 행렬을 만들어 준다. 이 스코어 행렬에 Value를 행렬곱해줘서 셀프어텐션 계산을 마친다.

(3) Multi-Head Attention

Multi-Head Attention은 Self Atention을 여러번 수행한 것을 일컫는다. 여러 헤드가 독자적으로 Self Attention을 계산합니다.

입력 단어 수는 2개, Value의 차원수는 3, Head는 8개인 멀티-헤드 어텐션을 나타낸 그림입니다. 개별 헤드의 셀프 어텐션 수행 결과는 ‘입력 단어 수 × Value 차원수’, 즉 2×3 크기를 갖는 행렬입니다. 8개 헤드의 셀프 어텐션 수행 결과를 다음 그림의 ①처럼 이어 붙이면 2×24 의 행렬이 됩니다.

Multi-Head Attention은 개별 헤드의 셀프 어텐션 수행 결과를 이어붙인 행렬(①)에 $𝐖^𝑂$를 행렬곱해서 마무리됩니다. $𝐖^𝑂$ 의 크기는 ‘셀프 어텐션 수행 결과 행렬의 열(column)의 수 × 목표 차원수’가 됩니다. 만일 Multi-Head Attention 수행 결과를 그림9와 같이 3차원으로 설정해 두고 싶다면 $𝐖^𝑂$ 는 24×3 크기의 행렬이 되어야 합니다.

Encoder 에서의 Self Attention

인코더의 셀프어텐션은 Query, Key, Value가 모두 소스 시퀀스와 관련되어 있다. 즉 번역 Task라면 Q,K,V가 모두 한국어라는 것이다. 따라서 한 시퀀스에서 A라는 단어가 B라는 단어와 관계가 높다면, Softmax값이 가장 높을 것이고, 이것이 Value 벡터와 가중합 되서 셀프 어텐션 계산을 마친다.

결론적으로 *인코더에서의 Self Attention은 소스 시퀀스 내의 모든 단어 Pair와의 관계를 고려하게 된다. * 참고로 Attention Score 행렬의 (i, j) 요소는 i번째 입력값 (Query)와 j번쨰 입력값 (Key, Value) 사이의 유사도를 의미한다.

Self Attention - Decoder

Decoder에는 Encoder의 마지막 블록에서 나온 소스 단어 벡터 시퀀스와 이전 디코더 블록의 수행 결과로 도출된 타깃 단어 벡터 시퀀스이다.

Masked Self Attention

기존의 Encoder-Decoder 구조의 모델들은 순차적으로 입력값을 전달받아 t+1 시점 예측을 위해 사용할 수 있는 데이터가 t 시점까지로 한정된다. 하지만 Transformer에서는 전체 입력값을 전달 받기 때문에 입력값을 예측할 때 미래의 시점의 입력값까지 참고하는 문제가 발생한다. 이러한 문제를 방지하기 위한 기법을 Look-ahead Mask 라고한다.

Look Ahead Mask Attention Score의 (i, j)는 i번째 Query와 j번쨰 Key,Value 사이의 유사도다. 따라서 $i < j$ 가 되면 i가 미래의 Attention 값을 보게 된다. 이를 막기 위해 $i \geq j$의 계산을 강제할 수 있지만 이것보다 $i<j$인 요소 (즉 Attention Score 행렬의 대각선 윗부분) 를 $- \infty$ 로 변경하고 Softmax로 취해서 Attention Weight을 0으로 만든다.

해당 매커니즘에서는 타깃 언어의 벡터 시퀀스를 계산 대상으로 한다. Encoder의 Self Attention과 크게 다르지 않다.

Multi-Head Attention

Encoder의 단어 시퀀스와, Decoder의 단어 벡터 시퀀스를 각각 KEY, Query로 삼아 계산을 수행한다.

FFN, ADD, Norm

(1) Feed Forward Network

Multi-Head Attention의 출력은 입력 단어들에 대응하는 벡터 시퀀스이다. 벡터 각각을 FFN에 입력합니다. Activation은 ReLU를 이용합니다.

(2) Add : 잔차

트랜스포머 블록의 Add잔차 Residual Connection을 가리킨다. 이를 통해서 블록 계산을 다양한 관점에서 수행할 수 있다.

(3) Norm : 레이어 정규화

$$ y = \frac {x - E\left [x \right ]}{\sqrt{V\left [ x \right ] +\epsilon}} * \gamma + \beta $$

Layer Normalization 는 미니 배치의 인스턴스($x$)별로 평균을 빼주고 표준편차로 나누어 정규화를 수행하는 기법입니다.

이를 통해 학습이 안정되고 그 속도가 빨라지는 등의 효과가 있습니다.

HOW TO TRAIN

(1) Dropout

과적합을 방지하는 방법으로, 뉴런의 일부를 학률적으로 0으로 대치하여 계산에서 제외하는 방법이다.

(2) Adam Optimizer

Adam은 경사하강을 할떄 방향과 보폭을 적절하게 정해준다. 현재 위치에서 가장 경사가 급한 쪽으로 내려가되, 하강하던 관성을 일부 유지하도록한다. 보폭의 경우 안가본 곳은 큰 걸음으로 걸어 훑고, 많이 가본 곳은 갈수록 보폭을 줄여 세밀하게 탐색하는 방식으로 학습된다.

How to Prevent Overfitting

딥러닝을 이용한 모델 학습의 가장 큰 관건은, 주어진 데이터셋을 가지고 특정 테스크에 일반화되어 잘 학습된 모델을 만드는 것이다.

따라서 Overfitting 문제를 해결하는 것이 무척 중요하며, 이에는 다양한 방법들이 사용된다. 대표적으로 다음과 같다.

1. 데이터의 수를 늘린다
2. 모델의 Complexity를 줄인다
3. Regularization을 사용한다.

1,2 번 방법에 대해서도 차차 이야기하겠지만 오늘은 L1-Regularization과 L2-Regularization에 대하여 이야기하겠다.

Regularization

우선 데이터셋의 bias를 제거하고 증대하고, 모델의 Complexity를 줄여도 Overfitting 문제가 해결이 되지 않는다면, Regularization을 적용해야한다.

Regularization은 모델의 복잡도를 낮추기 위한 방법이다. Weight 값이 너무 크면 지나치게 구불구불한 형태의 계산함수가 만들어지는데, Regularization은 Weight가 너무 큰 값을 가지지 않게 방지한다.

Regularization에 대해서 이야기 하기 전에 Norm과 L1 Norm, L2 Norm의 차이, 그리고 Loss들과 차이에 대해서 알아보자.

1. Norm

$$ \left| x\right|{p} := \begin{pmatrix} \sum{n}^{i=1}\left|x_{i}\right|^{p}\end{pmatrix}^{\frac{1}{p}} $$

Norm은 벡터의 크기(길이) 를 측정하는 방법이다. 선형대수학에서 자주 접할 수 있는데, 벡터가 얼마나 큰지 (차원의 크기가 아닌 구성 요소의 Magnitude) 알려주는 것이라고 생각하면 간단하다. 혹은 두 벡터사이의 거리를 측정하는 방법이기도 하다.

• p 는 Norm의 차수를 의미한다. p=1이면 L1 Norm이고, p=2 이면 L2 Norm 이다.
• n은 해당 벡터의 원소의 개수를 의미한다.
  

2. L1 Norm

$$ d_{1}\left ( p, q \right )= \left|p - q\right|{1} = \sum{n}^{i=1}\left|p_{i}-q_{i} \right| $$

위와 같이 p,q라는 벡터가 있을 때, 두 벡터 차의 절댓값의 합이 바로 L1 Norm이다.

3. L2 Norm

$$ \left| x \right|{2} = \sqrt{\sum{n}^{i=1}\left|x_{i}\right|^{2}} $$

L2 Norm은 n차원 좌표평면 (유클리드 공간)에서 피타고라스 정리를 이용한 벡터간의 유클리디안 거리 (직선거리)를 나타낸다. 여기서 한 벡터가 원점이면 X의 원점간 직선거리라고 볼수 있다.

4. L1 Norm, L2 Norm 차이

검정색 두 점 사이의 L1 Norm 은 빨강, 파랑, 노랑색 선으로 표현될 수 있지만, L2 Norm은 오직 초록색(대각선) 선으로만 표현될 수 있다. L1 Norm은 여러가지 path를 가지지만, L2 Norm은 Unique Shortest Path를 가진다.

5. L1 Loss, L2 Loss

$$ L_{1} = \sum_{n}^{i=1}\left|y_{i}-f(x_i)\right| $$ $$ L_{2} = \sum_{n}^{i=1}\left ( y_i -f(x_i) \right )^{2} $$

$y_i$ 는 실제값, $f(x_i)$는 예측값을 의미한다.

L1 Loss : 실제값과 예측값 사이의 오차 절대값의 합을 L1 Loss라고 한다. L2 Loss : 오차의 제곱합

Robustness

L2 loss는 outlier의 정도가 심하면 심할수록 직관적으로 제곱을 하기에 계산된 값이 L1보다는 더 큰 수치로 작용하기때문에 Robustness가 L1보다 적게된다.

따라서 Outlier가 효과적으로 적당히 무시되길 원한다면, 비교적 이상치의 영향력을 덜 받는 L1 loss를 선택하고, 반대로 이상치의 등장이 중요한 상황이면 L2 loss를 취해야한다.

6. Regularization

모델 복잡도에 대한 패널티로 정규화는 과적합을 예방하고 Generalization 성능을 높이는데 도움을 준다. RegularizationDpsms L1/L2 Regularization, Dropout, Early Stopping등이 존재한다.

Regulariztion은 특정 가중치가 너무 과도하게 커져 과적합이 되는 것을 방지한다.

L1 Regularization (Lasso)

$$ Cost = \frac{1}{n}\sum_{n}^{i=1}\left{L(y_i, \hat{y_i}) + \frac{\lambda }{2}|w| \right} $$

L1 Regularization은 기존 Cost Functiond에 가중치 (W)의 크기가 포함되면서, 학습의 방향이 Cost Function 뿐만이 아니라 가중치 또한 줄여나가는 방식으로 진행이 된다. 람다$\lambda$는 학습률 하이퍼 파라미터로, 0에 가까워질 수록 정규화의 효과는 없어진다.

L1 Regularization이 적용된 Cost Function을 편미분한 결과로

$$ w \to w - \frac{\eta \lambda}{n}sgn(w) - \eta \frac{\partial C0}{\partial w} $$ $sgn(w)$ 는 실수의 부호를 출력하는 함수이므로, w의 크기에 상관없이 w 부호에 따라 상수값을 빼주는 방식으로 진행된다.

L2 Regularization (Ridge)

$$ Cost = \frac{1}{n}\sum_{n}^{i=1}\left{L(y_i, \hat{y_i}) + \frac{\lambda }{2}|w|^2 \right} $$

기존의 Cost Function에 가중치의 제곱을 더함으로써, 가중치가 너무 크지 않은 방향으로 학습되게 된다.

위의 Cost Function을 편미분하게 되면,

$$ w \to w - \eta \frac{\partial C0}{\partial w} - \frac{\eta \lambda}{n} $$ 이는 곧 w 에 $(1-\frac{\eta \lambda}{n})$을 곱함으로써 w 값이 감소되는 방향으로 진행되며, Weight Decay 라고도 불린다.

7. Regularization의 선택기준

Regularization의 의미인 가중치 w를 감소시키는 방향으로 학습시킨다는 것은 결국 Local Noise에 Robust한 모델을 만들겠다는 의미이다. 따라서 Outlier에 Robust해지고 일반화된 모델이 만들어지는 것을 목표로 하는것이다.

L1 Regularization

• 가중치 업데이트 시, 가중치의 크기에 상관없이 상수값을 빼면서 진행된다.
• L1 Norm에서 봤듯이, L1 은 Feature Selection이 가능하다. 이는 곧 L1 Regularizaiton의 특징이 되기도 한다.
• 가중치들은 0으로 수렴하는 경향이 있으며, 중요한 가중치들만 남게 된다.
• 의미있는 값을 강조하고 싶은 Sparse Model에 적합하다.
• 즉, 변수선택이 가능하다.

L2 Regularization

• 모든 가중치를 균등하게 작게 유지한다. 이런 특성으로 학습에는 더 유리하다

참고 문헌 https://ratsgo.github.io/machine%20learning/2017/05/22/RLR/ https://seongyun-dev.tistory.com/52 https://huidea.tistory.com/154

소프트웨어 개발에는 다양한 방법론이 존재한다. 오늘은 일반적인 소프트웨어 개발 과정을 한기용님의 강의를 참고하여 정리해보도록 하겠다.

소프트웨어 개발 과정의 주요 부분들은 아래와 같다.

• Plan
• Execute/Track
• Manage Source Code
• Test
• Build

위와 같은 과정의 순서대로 하나씩 방법론과 현상황을 공유하고 정리하도록 하겠다.

1. How to Plan

소프트웨어 개발의 특징으로 꼽자면, 요구조건은 계속해서 변화한다는 것과, 디자인 단계에서 모든 문제를 미리 알 수 없다는 것이 대표적이다. 소프트웨어 개발 모델(프로세스)에는 폭포수, 애자일, 나선, 프로토타입, 테스트 드리븐 등 다양한 방법론이 있는다. 그 중 가장 핵심적으로 알아봐야할 모델은 폭포수(Water Fall)과 애자일(Agile)이다. Water Fall 모델과 Agile Model을 소개하고, Agile Model에 포커스하여 세부 방법론에 대해서 이야기하겠다.

(1) Water Fall Model

폭포수 모델은 소프트웨어 개발 모델 중 초창기에 정립된 모델로, 70년대에 고안되었다고 알려져있다. 폭포수 모델은 분석, 설계, 개발/구현, 테스트가 순서대로 이루어진다. 치명적인 단점으로는 대규모 프로젝트일수록 디자인에 걸리는 시간이 길어지며 그 기간 사이에 요구조건이 바뀔 수 있으며 실제 개발에 들어가면 예상 못한 문제들로 디자인을 변경해야할 가능성이 있다는 점이다.

- 분석 : 고객의 요구조건, 시스템 환경 등 타당성을 검토하고 요구사항에 대한 명세 작성
- 설계 : 요구사항 명세를 바탕으로 S/W의 전체 구조와 구조간의 관계, 상세 알고리즘등을 세부 설계
- 개발/구현 : 요구사항 명세를 준수하는 설계에 따라 개발하는 단계
- 테스트: 통합테스트, 인수테스트, 시스템 테스트를 통해 완성된 프로그램을 테스트하는 단계.

Water Fall Model의 키워드는 이렇다. 절차적, 단계검증, 하향식 접근, 피드백.

• 장점
  • 오랜기간 사용된 모델로써, 사례가 풍부하며 검증된 방식으로 업무 진행이 가능
  • 전체 과정이 S/W 생명주기와 일치하여 이해하기 쉽다.
  • 각 진행 단계별 산출물(문서)가 확실하여 진행중 및 진행이후에도 관리가 용이함.
• 단점
  • 각 단계가 종결되어야 다음 단계가 진행 가능
  • 사용자 피드백에 대한 빠른 대응이 어려움
  • 테스트 단계에서 발견된 중요 결함은 치명적인 문제가 될 수 있다.

실제로 법제처의 지능형 문석 검색 서비스 개발에 참여할때 PM께서 이러한 구조를 채택하였는데, AI 모델을 연구개발하는 우리로써는 많은 어려움이 있었다. 분석 과정에서 모델 구조를 선정하였어야하는데, 아직 선례가 없던 개발과정이다 보니 다양한 모델을 선정해서 실험 검토를 진행했어야했다. 다만 정리된 데이터가 없었기에 병행해야 하여 애자일 방법을 제안했는데, 감리사 출신인 PM께서는 거부하셨고 결국 프로젝트가 산으로 갔던 기억이 있다…

(2) Agile Model

변화에 유연하게 대처가 불가한 Water Fall Model의 단점을 보완하기 위해서 개발 주기를 단축하고 잦은 업데이트가 가능하도록 하는 방법론이다. 각 단계별 핵심은 지나치게 긴 토론을 지양한다는 점이다. 결국 아무런 계획 없이 개발하는 방법과 지나치게 많은 개발 방법들 사이에서 타협점을 찾고자 발생한 모델이라고 볼 수 있다. 따라서 핵심을 말하자면, 특정한 주기 (Sprint)를 이용하여 실질적인 개발을 진행하며 필요 요구를 더하며 수정하는 방법론이라고 볼 수 있다.

Agile 방법의 특징으로는, 개인과의 상호작용을 중시하며 문서보다는 작동하는 소프트웨어를 중시한다는 점이다. 실제로 애자일 개발 방법론을 채택한 스타트업들이 회고를 중요시하고 소통을 중요시하는데에는 애자일 모델의 특성또한 투영된 것이라고 생각한다.

약 2주 정도의 싸이클을 (보통 Sprint라고 부른다) 기준으로 개발을 진행한다. 한싸이클에서 진행되는 단계는 아래와 같다.

- Backlog Prioritization : Gromming이라고도 불리며, 대개 PM이 작업별 중요도와 복잡도를 결정하는 단계이다.
- Planning : 해당 사이클의 작업을 결정한다 (토론 혹은 투표로 진행된다.)
- Daily Standup Meeting : Scrum이라고도 불리는 것 같으며, 하루의 상황을 보고하는 자리이다.
- Retrospective & Demo : 한 사이클맏 진행된 내용을 회고 및 데모한다.

Agile Model의 뚜렷한 특징을 꼽자면, 빠른 의사소통과 개발 착수가 아닐까 싶다. 토론은 빠르고 효율적으로 진행되어야 하며, 간소화가 중요하다.

Agile Model의 키워드는 이렇다. 상호작용, 개발 우선, 협력, 변화 대응

• 장점
  • 개발 주기를 통해 프로젝트의 방향과 목표를 가늠할 수 있음
  • 반복적인 결과물을 통해 수정된 요구사항 및 문제점에 유연하게 대처 가능
• 단점
  • 개발자 중심의 방법론으로 기획, 디자이너가 Passive하게 참여될 수 있다.
  • 빈번한 수정으로 개발의 피로도가 높음
  • 비용 및 시간이 불완전하게 정의 된 채로 진행될 가능성이 있다.

다음은 Agile Model의 각 과정에서 주목할만한 특징과 형태에 대해서 이야기해보겠다.

Planning 위의 Agile Scrum Model 이미지를 보면 Product Back log 이후에 Planning 단계를 거치는데, Planning 단계에서 사용하는 PM은 Sprint Card를 작성하여 구성원들과 작업별 일정을 산정한다. 스프린트 카드의 구성은 PM 별로 상이하지만 한기용님이 제공하신 예시를 사용하겠다.

<스프린트 카드 예시>

• 타이틀 : 작업의 이름
• 세부설명
• 포인트 (플래닝 포커를 통한다. 아래에서 설명하겠다)
• 성공의 정의: Definition of Done
• 체크리스트: 작업이 성공적으로 끝나는데 필요한 세부작업

위의 과정에서 포인트는 일종의 작업별 일정이다. 그런데 왜 포인트라는 표현을 쓰느냐면, 이를 결정하는데에 Planning Poker라는 방식을 사용하기 때문이다. 포인트는 회사마다 정의가 다른데, 1포인트는 1 Full data for a Developer와 같이 산정되어 있다. 개발자들이 모여 작업별로 들어가는 일정을 산정하는데 이에 포인트를 이용해 투표를 하므로 포커라는 말이 쓰였다. 의견이 상이할 경우에는 토론을 진행하지만, 애자일 방식의 특성상 빠른 의견합치를 요구한다. 따라서 토론이 오래걸릴 경우, 작업의 정의가 명확하지 않거나, 작업의 분할이 필요하다는 것을 암시한다.

Daily Standup Meeting 앞에서 언급한 것과 같이 매일 모든 팀원들이 각자 상황을 공유하는 과정이다. 각 보고 당 10-15분 정도로 상황을 공유한다. 보고의 내용은, 마지막 스탠드업 이후의 작업물, 오늘의 작업 내용와 진행중인 목표, 이슈 정도를 공유한다. 이때 신속하고 빠른 의사소통이 중요하다. (길어지는 회의를 막기 위해서 플랭크를 한다는 밈도 있다)

2. How to Execute/Track

대표적인 협업 툴로는 JIRA 와 Trello 등이 있다.

(1) Jira

프로젝트 관리를 위한 전반적인 기능을 제공하는 툴로 호주의 Altassian 이라는 회사에서 개발하였다. 주요 기능으로는 Agile Scrum 관리 툴, SVN (소스코드 컨트롤), Wiki (협업 문서툴) 등이 있다. 많은 수의 회사들이 JIRA를 프로젝트 관리를 위해 사용한다.

(2) Trello

Agile Scrum 관리를 위한 툴로 JIRA에 비해 훨씬 더 직관적인 단순한 인터페이스를 제공한다. JIRA가 최근에 인수를 하여 결국 한식구가 되었다.

3. How To Manage Source Code

소스 버전 컨트롤 소스버전 컨트롤은 아주 중요하다. 개발자 각자가 개발하는 소프트웨어의 소스코드에 발생하는 변경사항들을 관리할 수 있도록 해주는 프로그램이기 때문이다. 소스 버전 컨트롤의 중요성은 다음과 같다.

• 코드 변경사항들을 쉽게 추적 가능하다. (에러 발생시 이전 버전으로 Rollback 또한 가능하다)
• 다수의 개발자가 공동 개발시에, 공유 및 변경이 용이하다.
• 최근 소스 버전 컨트롤 시스템들은 코드 리뷰 기능 또한 지원한다.
• 코드 백업의 역할 또한 수행 가능.

소스 버전 컨트롤 소프트웨어에는 CVS (Concurrent Version System), SVN (SubVersionN)등이 있지만 가장 대표적인 것은 Git/Github 이다. Github은 가장 인기 있는 버전 컨트롤 소프트웨어 이며, 웬만한 오픈소스 소프트웨어들은 Github상에 존재한다. (Github은 2018년, Microsoft에 $7.5B 가격으로 인수되었다.)

코드리뷰

코드리뷰는 주니어 개발자나 새로 온 개발자들을 트레이닝 시키는 최선의 방법이라고 익히 알려져 있다. 이는 취업을 준비하는 개발자 지망생들이 알고리즘 스터디를 만들어 서로의 풀이를 보면서 최적화하고 리뷰하면서 이 효과를 간접적으로 느낄 수 있을 것이다. 다만, 리뷰를 진행하는 개발자들이 시니어들이라는 점에서 바쁜 사람들이라는 점이 애로사항이다. 따라서 애자일 방법론에서는 스프린트 플래닝에 이를 고려해서 테스크를 할당한다.

코드리뷰 팁

(1) 코드리뷰를 요청하는 이

• 요청시 되도록이면 Unit test 단위로 요청하는 것이 제일 좋은 방법이다.
• 주석을 최대한 추가하고 목적과 솔루션을 명시한다.
• 리뷰에 대한 피드백을 감정적으로 받아들이지 않는 자세

(2) 코드리뷰를 하는 이

• 코딩 스타일에 대한 것 보다는 코드 자체에 집중하여 이야기한다.
• 객관적으로 작성하며, 비판적인 어조는 지양하는 것이 좋다.
• 충분히 시간을 들여 도움이 되는 리뷰를 제공하는 것이 장기적으로 좋다.

한기용님이 공유하신 코드리뷰 예시 링크를 함께 첨부한다. Before : https://github.com/keeyong/2021-code-smells/blob/main/before.py After : https://github.com/keeyong/2021-code-smells/blob/main/after.py

4. How to Test

TDD (Test Driven Development) 개발을 시작할 때부터 테스트를 어떻게 진해아할 것인지 부터 생각하고 개발에 착수하는 방법론이다. 이러한 방법론은 코드 구성 자체가 테스트에 편리하게 작성되는 효과를 발생시킨다. 또한 개발자 본인이 만들려는 기능에 대해 숙고하게 되는 효과 또한 발생한다. 테스트에는 여러가지 종류가 있는데 그 중 몇가지만 열거하겠다.

(1) Unit Test : 가장 보편적이고 기본적인 테스트 방법론으롸, 모듈의 특정 기능을 테스트하는 방식이다

(2) Integration Test : 다수의 모듈을 통합하여 하는 Unit Test의 한 차원 위의 테스트라고 볼 수 있다.

(3) Acceptance Test : 과다한 트래픽이 몰릴 때, 서버 혹은 기능이 부하를 견딜 수 있는지 테스트하는 것이다.

(4) UI Test : 근래 Selenium 등의 툴을 이용해서 웹페이지 자체의 기능을 테스트하는 것 또한 보편화 되어 있다.

대다수의 IT 기업들이 Unit Test를 포함한 코드 변경을 의무적으로 요구하는 것을 보면, 테스트가 얼마나 중요하게 취급되는지 알수 있다. 이런 기업들에서는 Test가 없으면 아예 코드 체크인이 실패한다고 한다. 테스트가 많을 수록 시스템의 안정성을 증대할 수 있고, 이후 Refactoring이 요구되는 순간이나 신규 엔지니어의 코드 수정에도 굉장히 편리하다는 장점이 있다. 따라서 Sprint Planning 또한 Test 시간을 포함하여 진행해야한다.

5. How to Build

빌드 빌드란 개발자 혹은 팀이 개발한 소프트웨어를 배포를 위한 형태로 만드는 것을 말한다. 배포와 연관된 만큼, 테스트 또한 빌드의 중요한 일부로 포함된다. 개발팀의 규모 혹은 참여자가 많을 수록 더 중요하다. Continuous Integration이라는 것이 있는데, 말 그대로 개발이 끝나기 전부터 지속적으로 빌드를 하는 것이다. 이런 방식을 통하면 소프트웨어의 안정성이 증대된다고 한다.

Continuous Integration Software Engineering Practice 중의 하나로 위에서 말한 것 처럼 개발이 끝나기 전부터 지속적으로 빌드를 해가는 것이다. 몇가지 기본 원칙이 있는데, 코드 Repository는 하나만(Master, Main) 유지하면서 코드 변경은 최대한 자주 반영한다는 것이다. Test Coverage를 통해 테스트를 최대한 추가하는 것을 지향하며, 빌드를 계속 적으로 수행한다. 이때 빌드는 자동화 하는 경우도 있다.

많은 쇠사들은 빌드가 실패할 경우 빌드가 다시 성공할 때까지 코드 변경을 금지한다고 한다. 즉, 빌드 실패가 발생하면 모든 개발자의 발이 묶이는 족쇄(?)가 된다는 것이다. 따라서 조직이 커지면 빌드만 전담하는 엔지니어가 생기는데 Devops라고 불리며, 주 업무는 빌드 실패의 주원인(개발자)를 찾는 것이다. 역할군이 나뉠정도로 빌드는 중요한 부분이고, 빌드 실패 원인인 개발자에게는 가벼운 패널티를 부과하는 경우도 있다고 한다.

Jenkins (오픈소스 CI 빌드 소프트웨어) Jenkins는 오픈소스 CI 빌드 소프트웨어이며, CI와 관련한 모든 기능을 지원한다. 직접 지원하는 것은 아니고 플러그인의 형태로 지원하며, Github, Git, SVN 등 대부분의 소스 컨트롤 시스템과 연동된다. 빌드된 소프트웨어의 배포를 위해서도 사용이 가능하다. 재밌는 이야기는 원래 썬 마이크로시스템에서 개발하여 Hudson이라는 오픈소스로 공개되었었는데, 오라클이 썬을 인수하면서 오픈소스화를 취소했다. 이에 불만을 가진 Hudson 개발자가 새로 개발하여 배포한 것이 Jenkins라고…

마무리하며…

오늘은 이렇게 Plan, Execute/Track, Manage Source Code, Test, Build의 보편화된 소프트웨어 개발과정에 대해서 알아봤다. 필자는 사실 이수학점이 남질 않아서 소프트웨어 공학 수업을 듣지 못했는데, 디자인 패턴, 소프트웨어 공학은 취업 이후 꼭 읽어볼 계획을 하고 있다. 이전에 있던 연구조직에서 얼마나 구먹구구식의 진행을 했는지 느낄 수 있었던 학습이었던 것 같다…

웹페이지에 표시되는 콘텐츠 영역

Block, Inline, Inline-block

Body 태그는 크게 Block 요소, Inline 요소로 구별된다.

1. Block (블록레벨 요소)

<div> <article> <section> ...

레고 블록처럼 차곡차곡 쌓이고 브라우저 너비에 꽉 차게 삽입이 된다.

• 블록의 크긱와 내/외부에 여백을 지정할 수 있고 일반적으로 페이지의 구조적 요소를 나타낸다
• 인라인(inline)요소를 포함할 수 있으나, 인라인 요소에 포함 될 수 없다.

<span>, <a>, <strong> ...

사람의 눈에는 보이지 않지만 "문서의 정보"가 담기는 영역 여기서 문서의 정보란, 타이틀, 메타데이터, CSS, Script등이 포함된다.

메타데이터

Head 태그에 포함 가능한 메타데이터는 다음을 포함한다.

• 인코딩 정보
• 문서 설명
• 문서 작성자

인코딩 정보에는 Charset(character set)이 있는데, 이는 "문서에서 허용하는 문자의 집합"을 일컫는다. charset에 선언된 "문자의 집합" 규칙에 따라 문서에서 사용할 수 있는 문자가 제한된다. 위 사진의 예처럼 ISO-8859-1을 사용하면 문서의 한글이 출력되지 않는다. (최신 브라우저의 경우에는 문서 인코딩이 잘못되어 있어도 자동으로 수정해주지만, 잠재적 문제 해결을 위해 UTF-8으로 설정해주자.

Style, Link, Script

<style>, <link>, <script>

태그 자체는 Head안에 있지만, 문서 내 컨텐츠의 외형에 영향을 끼친다.

1. Style

컨텐츠를 가지는 태그이다. 시작태그와 종료태그 사이에 CSS가 작성된다.

<style>
  body {
      color: blue;
  }
</style>

위와 같이 작성하면, 본문의 글씨가 파란색으로 바뀐다.

2. Link

index의 head가 길어지게 되면 편집의 용이성이 떨어지므로, 수정의 용이성을 얻기 위해서 Link 태그를 사용한다.

<link rel="stylesheet" href="style.css" />

위의 Link는 style 태그가 길어져서 CSS와 HTML을 동시에 수정하고 길이가 길어지는 경우와 같이 내용이 길어졌을 때 사용한다. rel 속성에 링크된 파일이 stylesheet파일임을 알려주고, href에 스타일 시트 파일의 링크를 작성한다.

3. Script

Style 태그는 콘텐츠 방식으로 작성을하거나 Link 태그를 이용해서 링크 방식으로 이용해서 작성한다. 하지만 script는 두가지 방식을 한번에 사용이 가능하다. script 태그는 특이하게 컨텐츠를 가지는 태그이지만, 컨텐츠를 가지지 않는 경우도 존재한다. 따라서 콘텐츠 방식으로 Head에 작성을 하거나, 링크 방식으로 작성하는 두가지 방식으로 작성 가능하다.

1. 콘텐츠방식: Style 태그와 동일
2. 링크 방식: 컨텐츠를 가지지 않지만 종료 태그를 첨부해줘야함

   <script src="script.js"></sript>

   컨텐츠를 가지지 않는 단일태그는 셀프 클로징을 사용하나, script는 셀프 클로징이 아닌 종료태그를 작성해줘야한다.

HTML은 콘텐츠를 가지는 태그와 콘텐츠를 가지지 않은 태그로 구분된다. 기본 작성은 꺽쇠 (<>)를 이용하여 태그의 이름을 지정한다.

1) 콘텐츠를 가지는 태그

<div> 콘텐츠 </div>

2) 콘텐츠를 가지지 않는 태그

<br />

속성과 값

어떤 태그를 쓰느냐에 따라 태그가 가진 고유의 속성과 값이 있고, 모든 속성에 적용되는 전역속성도 있다.

<div title="제목">Content</div>

<!-- 태그 a (a 링크라고 불림) 는 페이지 이동 기능 -->
<!--속성           값           콘텐츠   -->
<a href="http://naver.com">네이버 바로가기</a>

HTML 기본 문서

<!DOCTYPE html>
<html lang="ko">
    <head>
        <title>문서 제목</title>
    </head>

    <body>
        문서 내용
    </body>
</html>

위와 같은 기본적인 문서를 만들고 VScode의 Live Extension을 실행하면 아래와 같은 창이 만들어진다.

부모요소 자식요소

html은 계층적으로 부모요소 자식요소가 정해져있기 때문에 Indent를 신경써서 작성해주어야한다. Indent에서 문제가 있어도 사실 Python처럼 Indentation 문제가 생기지는 않지만 가독성을 위해서 Depth를 지켜준다.

Heap은 이진트리의 한 종류이며, 정렬시에 유용하게 사용됨

Heap

• BinaryTree의 한종류이며, 완전 이진트리의 구조를 가지고 있음

• 루트 노드가 언제나 최대 혹은 최소 값을 가짐. (MaxHeap, MinHeap)
• 서브트리도 모드 Heap 구조
• 자식 노드들 간의 관계는 이진탐색트리와 다르게 상관 없음
• 루트 노드는 1번으로 시작하며, 어레이 형식으로 담기에 편함 (왼쪽자식 2i, 오른쪽 자식 2m + 1

구현 및 시간복잡도

class MaxHeap:

    def __init__(self):
        self.data = [None]

*1) 원소 삽입: insert() * 트리의 마지막 인덱스에 새로운 원소를 임시 저장하고 부모노드와의 비교를 통해 위로 이동.

시간복잡도 : O(logN) - 부모노드와 대소 비교 횟수

def insert(self, item):
    self.data.append(item)
    idx = len(self.data) - 1
    while idx > 1:
        if self.data[idx] > self.data[idx//2]:
            self.data[idx], self.data[idx//2] = self.data[idx//2], self.data[idx]
            idx = idx//2
        else:
            break

2)원소의 삭제

루트 노드의 제거(Max Heap일 경우 최대값) 트리 마지막 인덱스의 Key 값을 루트 노드로 이동 후, Left Right 자식들과 비교하며 자리를 바꿈. (Left Right 중 더 큰 값과 교체)

시간복잡도 : O(logN) - 자식 노드와 대소 비교 횟수

def remove(self):
    if len(self.data) > 1:
        self.data[1], self.data[-1] = self.data[-1], self.data[1]
        data = self.data.pop(-1)
        self.maxHeapify(1)
    else:
        data = None
    return data

def maxHeapify(self, i):
    left = i * 2
    right = i * 2 + 1
    smallest = i
    if left < len(self.data) and self.data[left] > self.data[smallest]:
        smallest = left
    if right < len(self.data) and self.data[right] > self.data[smallest]:
        smallest = right

    if smallest != i:
        self.data[i], self.data[smallest] = self.data[smallest] = self.data[i]
        self.maxHeapify(smallest)

3) 활용방안

• Priority Que (Dequeue에서 최대 혹은 최소값 반환: O(logN)
• HeapSort

반시계 방향으로 90도씩 회전하는 로봇청소기가 청소한 횟수를 구하라

손풀려고 시작한 문제였음에도 불구하고, 디버깅에 시간이 오래 걸렸다. 이상했던 점은 청소기가 회전부터 수행하는데, 원래 자리로 돌아오고 나서 전진을 못한다는 점이었다.

북동남서 순서로 0,1,2,3 으로 설정하고, 주변에서 청소가능한 타일을 못찾았을 경우 False를 반환하게 설정하였는 데, 자세히 보니, False == 0 이어서

def check_room(n, m, grid, x, y, d):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    for i in range(4):
        d = rotate(d)
        nx = x + dx[d]
        ny = y + dy[d]
        # 청소할 곳이 있다면 전진
        if grid[nx][ny] == 0:
            return d
    # 한바퀴 회전 이후에도 청소되지 않는 빈칸이 없다면 후진 준비
    return -1

주변에 청소할 타일이 있나 확인하는 지점에서 북쪽 방향을 반환하면 False를 반환하게 되는데, 이 부분에서 전진하지 못하고 False로 인식되어 반대로 후진하는 문제가 있었다.

최근 스터디원이 이동불가 한 개체를 -1로 표기하던데, 나도 False보다는 -1로 표기하는 습관을 들여야 할거같다.

# 회전 (시계 반대방향 90도)
def rotate(d):
    return (d + 3) % 4

# 시계반대방향으로 회전하며 청소 가능한 (0) 인 칸 식별
def check_room(n, m, grid, x, y, d):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    for i in range(4):
        d = rotate(d)
        nx = x + dx[d]
        ny = y + dy[d]
        # 청소할 곳이 있다면 전진
        if grid[nx][ny] == 0:
            return d
    # 한바퀴 회전 이후에도 청소되지 않는 빈칸이 없다면 후진 준비
    return -1


if __name__ == "__main__":
    N, M = map(int, input().split())
    r, c, d = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(N)]
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    # 청소 횟수
    cnt = 0
    # 후진해야하는데 뒤에 벽(1)이 있으면 break
    while True:
        # 현재 칸을 청소해야할때.
        if grid[r][c] == 0:
            cnt += 1
            grid[r][c] = 2

        # 청소할 다음 칸 찾기
        next_d = check_room(N, M, grid, r, c, d)
        # 청소할 곳이 없는 경우
        if next_d == -1:
            # 반대방향
            op_d = (d + 2) % 4
            # 후진 (방향은 유지됨)
            nr = r + dx[op_d]
            nc = c + dy[op_d]
            # 뒤가 벽이면 정지
            if grid[nr][nc] == 1:
                break
            # 뒤로 한칸 이동
            else:
                r = nr
                c = nc
        else:
            r = r + dx[next_d]
            c = c + dy[next_d]
            d = next_d
    print(cnt)

FastCampus 운영체제 강의 요약

컴퓨터 시스템의 기본 4 구성

• 하드웨어
• 운영체제 (응용 프로그램간 하드웨어 사용 제어 및 조정)
• 응용 프로그램
• 사용자

운영체제의 역할

(1) 리소스 할당의 주체 (2) 프로그램 실행을 제어하고 부적절한 사용을 방지함

컴퓨터 시스템의 작동

BootStrap

PC의 전원버튼을 누른 직후부터 운영체제가 메모리에서 동작하기까지의 과정

(1) 메인보드 전력 공급 (2) BIOS 루틴 시작 (3) BIOS의 셀프테스트를 통한 하드웨어 체크 (4) MBR (Master Boot Record) 혹은 Master Partition Table 에 존재하는 부팅정보를 읽어옴 (5) RAM에 Bootloader 적재. 디스트에 있는 OS(커널) 코드를 복사하여 메모리에 적재 초기화.

인터럽트

우선순위 높은 상황이 발생하면 신호를 보내는 것

1. 하드웨어 인터럽트 : 하드웨어가 발생시키는 인터럽트로, CPU외의 하드웨어가 CPU에 신호를 보내야 할 경우 발생

2. 소프트웨어 인터럽트 : 사용자 프로그램이 인터럽트 하는 경우 발생. 예외상황 / SVC (Supervisor Call)

인터럽트 발생의 전체과정

[인터럽트 신호 발생] - [CPU 수행중인 작업 중지, 지정 위치로 실행위치 변경] - [인터럽트 종료] -[일시중단 되었던 컴퓨팅 재개]

인터럽트가 종료되면 이전 작업으로 돌아가야 하므로, 중단된 명령어의 주소가 반드시 저장되어야한다. 따라서 인터럽트 신호 발생 이후에는 저장된 복귀 주소를 PC(Program Counter)에 적재.

졸업한지 꽤 되서 CS 인터뷰 준비한다고 패스트 캠퍼스 초격차 강의를 돈주고 샀다... 약 한달남짓 모든강의를 듣고 강의요약을 작성하려는데.. 이제 듣기 시작하는거지만 수업의 수준이 전공자 수준으로 진행되냐 하면...아니다 (교수님 보고싶어요)

작일 삼성 SW 역량테스트를 마친후 듣는 수업이 알고리즘 수업...

감회가 새로웠다.

어제 삼성문제는 난도가 엄청 높진 않았지만, 특정부분에서 디버깅이 너무 오래걸리는바람에 완벽한 1솔을 못했으므로 상심이 컸다. (시험이 4시간이 되고부터는 해야할 테스크가 제법 많아졌다)

평소에 잘풀던 구현과 시뮬레이션, 최단거리에 행렬회전, 눈감고도 풀던 문제일 정도로 자주 연습해왔는데 사각형 범위 구하는데에 실수가 있었던 것 같다.

금주 토요일에 LG전자 코테또한 있으니 사실 상심할 시간은 없다.

오늘은 프로그래머스 데이터엔지니어링 데브코스 수업 첫날이었다. 내용이 알고리즘이라 편하게 들었고, 남은 시간은 구현문제를 한문제 풀었다 (미련이 남아서)

문제요약 : 어항 어레이를 2차원으로 늘려 회전하고 주변값과 연산 후 다시 1차원으로

문제는 여섯 단계로 나뉘었다.

1. 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣는다

2. 가장 왼쪽에 있는 어항을 그 어항의 오른쪽에 있는 어항의 위에 올려 놓는다.

3. 2개 이상 쌓여있는 어항을 모두 공중 부양시킨 다음, 전체를 시계방향으로 90도 회전시킨다. 이후 공중 부양시킨 어항을 바닥에 있는 어항의 위에 올려놓는다.

4. 공중 부양 작업이 모두 끝나면, 어항에 있는 물고기의 수를 조절한다.모든 인접한 두 어항에 대해서, 물고기 수의 차이를 구한다. 이 차이를 5로 나눈 몫을 d라고 하자. d가 0보다 크면, 두 어항 중 물고기의 수가 많은 곳에 있는 물고기 d 마리를 적은 곳에 있는 곳으로 보낸다.

5. 공중 부양 작업을 해야 한다. 이번에는 가운데를 중심으로 왼쪽 N/2개를 공중 부양시켜 전체를 시계 방향으로 180도 회전 시킨 다음, 오른쪽 N/2개의 위에 놓아야 한다. 이 작업은 두 번 반복해야한다.

6. 다시 위에서 한 물고기 조절 작업을 수행하고, 바닥에 일렬로 놓는 작업을 수행한다.

7. 물고기가 가장 많이 들어있는 어항과 가장 적게 들어있는 어항의 물고기 수 차이가 K 이하가 될때까지 반복한다.

구현은 항상 요구가 길어 머리가 아프지만, 실제로 풀다보면 명확하게 기능이 나누어져 있어서 별로 어렵지 않다. (근데도 시험장에선...)

결과는 아래와 같다.

import copy
def add_fish(bowl: list):
    min_fish = min(bowl)
    for idx, fish in enumerate(bowl):
        if fish == min_fish:
            bowl[idx] += 1
    return bowl


# 한번 회전해서 쌓기위한 준비
def find_bowl(grid):
    # 탐색 해야하는 층수 계산
    # 남은 부분의 길이가 길면 temp_grid 반환
    temp_grid = grid.copy()
    start_col = 0
    N = len(grid)
    if grid[-1][0] is not None:
        grid[-2][1], grid[-1][0] = grid[-1][0], None
        return grid, None, None, None

    for j in range(N):
        if grid[-1][j] is not None:
            start_col = j
            break
    array = []
    # 회전시킬 어레이 찾기
    # print(grid[-4:])
    for x in range(N-1):
        flag = 0
        temp = []
        for y in range(start_col, N-1):
            if grid[x][y] is not None:
                temp.append(grid[x][y])
                flag = 1
                grid[x][y] = None
            else:
                if flag:
                    array.append(temp)
                    break

    rest_len = len([x for x in grid[-1] if x is not None])
    # print(array)
    if array == [] or rest_len - len(array[0]) < len(array) + 1:
        return temp_grid, array, start_col, None
    else:
        col_len = len(array[0])
        last_line = []
        for last in range(start_col, start_col + col_len):
            last_line.append(grid[-1][last])
            grid[-1][last] = None
        array.append(last_line)
        return grid, array, start_col, rest_len

def rotate_array(array: list):
    n_row = len(array)
    n_col = len(array[0])
    new_array = [[0] * n_row for _ in range(n_col)]

    for j in range(n_col):
        for i in range(n_row):
            new_array[j][n_row-1-i] = array[i][j]

    return new_array


def add_bowl(grid, array, start_col):
    new_bowl = rotate_array(array)
    start_row = (len(grid)-1) - len(new_bowl)
    for new_row in range(len(new_bowl)):
        for new_col in range(len(new_bowl[0])):
            grid[start_row+new_row][start_col+len(array[0])+new_col] = new_bowl[new_row][new_col]

    bowl = []
    for x in range(start_row, len(grid)):
        row = []
        for y in range(start_col+len(array[0]), len(grid)):
            row.append(grid[x][y])
        bowl.append(row)
    # print(bowl)
    return grid, bowl


def arrange_fish(bowl):
    # 한번씩만 연산하므로, 오른쪽과 아래만 보면됨
    dx, dy = (0, 1), (1, 0)
    temp = [[0] * len(bowl[0]) for _ in range(len(bowl))]

    for x in range(len(bowl)):
        for y in range(len(bowl[0])):
            if bowl[x][y] is None:
                continue
            else:
                for i in range(2):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0 <= nx < len(bowl) and 0<= ny <len(bowl[0]):
                        if bowl[nx][ny] is not None:
                            d = abs(bowl[x][y] - bowl[nx][ny]) // 5
                            if d > 0:
                                if bowl[x][y] > bowl[nx][ny]:
                                    temp[x][y] -= d
                                    temp[nx][ny] += d
                                else:
                                    temp[x][y] += d
                                    temp[nx][ny] -= d
    # print("temp :",temp)
    for i in range(len(bowl)):
        for j in range(len(bowl[0])):
            if bowl[i][j] is not None:
                bowl[i][j] += temp[i][j]

    return bowl

def flatten(bowl):
    flat_bowl = []
    for j in range(len(bowl[0])):
        for i in range(len(bowl)-1, -1, -1):
            if bowl[i][j] is not None:
                flat_bowl.append(bowl[i][j])
    return flat_bowl

def rotate_twice(bowl):
    result = []
    # 1번 회전
    bowl1, bowl2 = bowl[:len(bowl)//2], bowl[len(bowl)//2:]
    result.append(bowl1[::-1])
    result.append(bowl2)
    # 2번 회전
    top = []
    bottom = []
    for i in range(2):
        top.append(result[i][:len(result[0])//2])
        bottom.append(result[i][len(result[0])//2:])

    top_rotate = rotate_array(rotate_array(top))

    return top_rotate + bottom


if __name__ == "__main__":
    N, K = map(int, input().split())
    bowl = list(map(int, input().split()))
    # 가상의 공간
    T = 0
    diff = 999
    while True:
        if diff <= K:
            print(T)
            break
        T += 1
        grid = [[None] * N for _ in range(N - 1)]
        bowl = add_fish(bowl)
        grid.append(bowl)

        trial = 1
        while True:
            temp_grid = copy.deepcopy(grid)
            if trial == 1:
                grid, _, _, _ = find_bowl(grid)
            else:
                grid, array, start_col, rest_len = find_bowl(grid)
                if rest_len is None:
                    grid = temp_grid
                    break
                else:
                    grid, bowl = add_bowl(grid, array, start_col)
            trial += 1

        arranged_bowl = arrange_fish(bowl)

        flat_bowl = flatten(arranged_bowl)

        rotate_bowl = rotate_twice(flat_bowl)

        arranged_bowl2 = arrange_fish(rotate_bowl)

        bowl = flatten(arranged_bowl2)

        diff = max(bowl) - min(bowl)