[BOJ 백준] 19532번 : 수학은 비대면강의입니다 – Kotlin[코틀린]

문제

자세한 문제 내용은 ‘수학은 비대면강의입니다‘를 클릭하세요.

풀이

이 문제는 브루트 포스 알고리즘을 이용하거나, 2차 방정식의 특성을 이용하여 풀 수 있습니다.

브루트 포스 알고리즘을 사용한다면, x와 y 값이 -999에서 999까지의 범위로 주어졌으므로, 모든 경우를 탐색하며 대입한 값을 확인해봅니다.

연립방정식을 사용한다면 다음의 풀이 과정을 거칩니다.

주어진 연립방정식은 다음과 같습니다.

 ax + by = c \\ dx + ey = f

가감법을 사용하여 이 연립방정식을 풀기 위해서는 먼저 한 변수를 제거해야 합니다. 이를 위해 두 방정식을 적절히 곱하여 두 방정식의 x 또는 y의 계수를 동일하게 만들 수 있습니다.

예를 들어, x의 계수를 동일하게 만들기 위해 첫 번째 방정식에 d를 곱하고, 두 번째 방정식에 a를 곱합니다.

 adx + bdy = cd \\ adx + aey = af

이제 두 방정식을 빼면 x 항이 사라집니다:

 (bdy - aey) = (cd - af)

이를 y에 대해 정리하면, 아래와 같은 식으로 정리됩니다.

 y = (cd - af) / (bd - ae)

x 또한 동일한 과정을 통해 식을 정리합니다.

테스트 코드

프로덕션 코드

브루트 포스 알고리즘 사용

연립방정식 풀이 사용

결과

제출번호 62098145가 브루트 포스 알고리즘을 사용한 코드를 제출한 결과이고, 제출번호 62098191가 연립방정식을 사용한 코드를 제출한 결과입니다. 연립방정식을 사용한 코드가 메모리 사용량이나 처리 시간에서 조금 더 좋은 성능을 보이고 있습니다.

실행 결과

카테고리: BOJ(백준) | 댓글 남기기 | 편집
카테고리: BOJ(백준) | 댓글 남기기

[BOJ 백준] 1193번 : 분수찾기 – Kotlin[코틀린]

문제

자세한 문제 내용은 ‘분수찾기‘를 클릭하세요.

풀이

주어진 문제는 무한히 큰 배열에 나열된 분수들 중에서 주어진 순서(X번째)에 해당하는 분수를 찾는 문제입니다. 주어진 순서에 따라 분수들이 지그재그 순서로 나열되어 있습니다.

문제를 해결하기 위해서는 각 분수의 위치와 값 사이의 규칙을 이해하는 것이 중요합니다. 이 문제에서는 다음과 같은 규칙을 발견할 수 있습니다:

  • 분수의 위치(row, column)를 기준으로 다음과 같이 값(numerator, denominator)을 구할 수 있습니다:
    • 분자(numerator) = row – (column – 1)
    • 분모(denominator) = column
  • 분수의 위치(row, column)을 기준으로 해당 위치까지의 분수 개수(total)를 구할 수 있습니다:
    • total = (row + column – 1) * (row + column) / 2

따라서, 주어진 순서 X에 해당하는 분수를 찾기 위해 다음과 같은 절차를 수행할 수 있습니다:

  1. 분수의 위치(row, column)를 찾기 위해, X에 해당하는 분수 개수(total)를 구합니다. 이를 위해 total 변수를 1부터 증가시키며 X보다 작거나 같은 total 값을 찾습니다.
  2. X와 total의 차이를 구하여 delta 변수에 저장합니다. (delta = X – total)
  3. delta가 홀수인 경우, 분수의 위치는 (delta + 1, column – delta)입니다. 분수의 값은 위에서 언급한 규칙에 따라 계산합니다.
  4. delta가 짝수인 경우, 분수의 위치는 (column – delta, delta + 1)입니다. 분수의 값은 위에서 언급한 규칙에 따라 계산합니다.

위의 절차를 따라 구현하면 주어진 순서 X에 해당하는 분수를 찾을 수 있습니다.

테스트 코드

프로덕션 코드

결과

실행 결과

카테고리: BOJ(백준) | 댓글 남기기

[BOJ 백준] 1934번 : 최소공배수 – Kotlin[코틀린]

문제

자세한 문제 내용은 ‘최소공배수‘를 클릭하세요.

풀이

이번 문제는 주어진 두 자연수 A, B의 최소공배수를 구하는 문제입니다. 최소공배수는 최대공약수를 통해 구할 수 있는데, 그 공식은 다음과 같습니다.

최소공배수(LCM) = (첫 번째 수 × 두 번째 수) / 최대공약수(GCD)

최소공배수는 두 수를 곱한 값에 최대공약수를 나눈 결과입니다. 이 공식은 두 수가 서로소(공약수가 1인 경우)인 경우에도 사용될 수 있습니다.

이 문제를 풀기위해서는 최대공약수를 구하는 알고리즘을 알아야 합니다. 최대공약수를 구하는 알고리즘은 여러가지가 있지만, 여기서는 유클리드 호제법을 이용해 문제를 풀어보기로 했습니다.

유클리드 호제법(Euclidean algorithm) : 최대공약수를 구하는 간결한 알고리즘

숫자 이론에서 최대공약수(GCD, Greatest Common Divisor)는 두 개 이상의 숫자의 공통된 약수 중 가장 큰 수를 의미합니다. 유클리드 호제법은 오래된 알고리즘으로, 두 숫자의 최대공약수를 효과적으로 찾는 방법을 제공합니다. 이 알고리즘은 매우 간결하며 효율적이어서 널리 사용되고 있습니다.

유클리드 호제법은 두 개의 숫자를 가지고 작업하며, 각 단계에서 나머지 연산을 사용합니다. 두 숫자를 A와 B라고 가정해봅시다. A를 B로 나눈 나머지를 R이라고 합시다. 이때, A와 B의 최대공약수는 B와 R의 최대공약수와 같습니다. 이 아이디어를 재귀적으로 적용하여 최대공약수를 찾을 수 있습니다.

다음은 유클리드 호제법의 단계를 보여주는 간단한 예시입니다. 우리는 270과 192의 최대공약수를 구하려고 합니다.

  • 270을 192로 나눕니다. 나머지는 78입니다.
  • 192를 78로 나눕니다. 나머지는 36입니다.
  • 78을 36으로 나눕니다. 나머지는 6입니다.
  • 36을 6으로 나눕니다. 나머지는 0입니다.
  • 나머지가 0이 되면, 이전 단계의 나누는 수가 최대공약수입니다. 따라서 270과 192의 최대공약수는 6입니다.

유클리드 호제법은 숫자의 크기에 관계없이 적용될 수 있으며, 계산 속도가 빠르기 때문에 널리 사용됩니다. 또한, 이 알고리즘은 다른 숫자 이론 문제에도 응용될 수 있습니다. 예를 들어, 최소공배수(LCM, Least Common Multiple)를 구하는 문제에도 사용될 수 있습니다.

테스트 코드

프로덕션 코드

결과

실행 결과

카테고리: BOJ(백준) | 댓글 남기기

[BOJ 백준] 2164번 : 카드2 – Kotlin[코틀린]

문제

자세한 문제 내용은 ‘카드2‘를 클릭하세요.

풀이

문제는 간단합니다. 큐에 1부터 n까지의 카드를 넣고, 큐에서 가장 위에 있는 카드를 버리고 그 다음 카드를 맨 뒤로 옮기는 작업을 반복합니다. 이 과정을 큐에 카드가 하나 남을 때까지 반복한 후, 남은 카드를 출력하면 정답이 됩니다.

문제 풀이에 사용될 자료구조는 선형 자료 구조 중에서도 양쪽 끝으로 데이터를 추가 혹은 삭제할 수 있는 Deque가 적합합니다. Kotlin Collection 에서는 ArrayDeque가 있기 때문에, 해당 Collection 을 이용해 문제를 풀어보기로 했습니다.

추가로, MutableList를 이용해 문제를 푸는 경우, 실제 채점 시에는 시간 초과가 발생합니다. 이는 MutableList가 기본적으로 링크드 리스트로 구현되기 때문인데요. 링크드 리스트는 각 노드들이 연결되어 있어서, 원소를 추가하거나 제거할 때마다 각 노드를 탐색하고 연결을 수정해야 합니다. 따라서 원소가 많아질수록 탐색 시간이 늘어나게 되어 실행 속도가 저하됩니다.

테스트 코드

프로덕션 코드

결과

실행 결과

카테고리: BOJ(백준) | 댓글 남기기

[Jenkins] trackingSubmodules 옵션에 관하여

사건의 발단

얼마전 부터 회사에서 관리하는 미들웨어 repository에서 일부 모듈들을 git submodule로 분리하여 관리하기 시작했습니다.

이와 대응해 Jenkins 파이프라인(Groovy 스크립트)에도 submodule과 관련된 스크립트를 추가했는데요. 최근 submodule 들이 parent repository에 커밋된 해시 코드가 아니라 최신 으로 체크아웃 받아져서 빌드되는 것을 확인되었습니다.

각 submodule에 최신으로 커밋된 수정사항들이 문제가 없어서 릴리즈에는 문제가 없었는데, 수정된 내용 중에 일부 플랫폼에는 아직 반영되면 안되는 사항들이 추가된 것을 로그 분석 중에 우연히 확인한 것이었습니다.

문재 해결

결론적으로, trackingSubmodulestrue에서 false로 변경하여 해결하였습니다.

구체적으로, 위의 코드에서 사용되는 플러그인 클래스 ‘SubmoduleOption’은 다음과 같은 옵션을 지원합니다.

  • disableSubmodules: Git 서브모듈 기능을 비활성화할지 여부를 설정합니다.
  • parentCredentials: 부모 Git 저장소의 자격 증명을 사용하여 서브모듈을 가져올지 여부를 설정합니다.
  • recursiveSubmodules: Git 서브모듈을 재귀적으로 처리할지 여부를 설정합니다.
  • reference: Git 서브모듈을 업데이트할 때 사용할 참조를 설정합니다.
  • trackingSubmodules: Git 서브모듈을 추적할지 여부를 설정합니다.
카테고리: Memo | 댓글 남기기

[Review] 넥스트스텝 교육콘서트 2기 간단 후기

교육정보

페어 프로그래밍 장점

  • OR 법칙으로 인해 50% 이상 버그가 감소 (나와 상대방이 놓치는 부분을 서로 확인)
  • 전문가들의 경험적 인지 작업을 효과적으로 배울 수 있음
  • 갈등이 드러나므로 오히려 팀워크가 향상됨
    • 페어 프로그래밍은 팀의 최소 단위(2명)이기 때문에, 갈등이 더 빨리 들어나고, 더 빨리 보완됨
  • 짝 용기가 생김

페어 프로그래밍의 도입시기는 언제가 좋을지?

  • 두렵거나, 지겹거나…
  • 페어 프로그래밍의 범위에는 문서 작성도 포함된다!

페어 프로그래밍 하는 방법

  • 역할 분리! : 내비게이터, 드라이버
    • 내비게이터 : 직접 운전대를 잡고 운전하는 역할
    • 드라이버 : 전체 지도를 보며 목적진에 다다르는 길을 안내
  • 중요한 것은 한 역할을 너무 오래하지 않고, 빈번하게 교대 (과몰입 방지)

페어 프로그래밍 시 주의할 점

  • 수평관계 유지 → 원활한 의사 소통

TDD

  • 켄트백은 2가지 모자를 동시에 쓸 수 없다고 말한다 → 기능 추가와 리팩토링을 동시에 하지 말라는 뜻
    • 노란 모자(안전모),  → Add function
    • 갈색 모자(진짜 모자) → Refactoring

리팩토링을 해야하는 순간 (마틴 파울러가 말하는 리팩토링의 순간)

  • 쓰레기 줍기 리팩토링 , Yuck! : 나쁜 코드, 코드 스멜이 나는 경우
  • 이해를 위한 리팩토링 , Comprehension : 내가 짠 코드가 아니거나 너무 오래 전에 짠 코드의 기억을 되살리는 경우
  • 준비를 위한 리팩토링, Preparatory : 기능을 쉽게 추가하도록 만들기

글쓰기를 통한 퍼스널 브랜딩

  • 처음 부터 많은 양이 길을 쓰려고 하지 말고, 점차 쓰는 양을 늘려 나가라.
  • 기술적인 얘기를 할 때, 나의 의견이 들어가는 것이 좋다. → “~을 생각해 보았다.”
카테고리: Memo | 댓글 남기기

[Ubuntu] Python 버전 변경하는 방법

소개

Ubuntu에서 다수의 python 버전을 운영할 때, update-alternatives를 이용하면, 손쉽게 python 버전을 변경할 수 있습니다.

update-alternatives는 Debian 계열 시스템에서 다수의 패키지를 심볼릭 링크로 관리해 주는 명령어입니다. 해당 명령어는 python 뿐만 아니라, jdk와 같이 대부분의 패키지 버전을 관리하는데 사용할 수 있습니다.

현재 사용중인 Python 실행 위치 확인

which 명령어를 사용하면 현재 사용 중인 python의 실행 위치를 조회할 수 있습니다.

조회된 /usr/bin/python 파일을 ls 명령어로 조회해 보면, 심볼릭 링크이고 실제 python 바이너리가 다른 위치에 설치된 것을 확인할 수 있습니다.

이미 다른 버전의 python을 설치했다면 아래의 명령어로 설치된 python 버전들을 확인할 수 있습니다.

update-alternatives를 이용한 python 버전 변경

python 등록 여부 확인

update-alternatives --config python 명령어를 통해 update-alternatives에 등록된 python 버전이 있는지 확인할 수 있습니다.

python 버전 등록 및 변경

현재는 등록된 python 버전이 없으므로, update-alternatives --install [symbolic link path] python [real path] number 명령어를 이용하여 python 버전을 등록합니다.

update-alternatives --config python 명령어를 다시 입력하면 등록된 python 버전이 확인이 가능합니다.

숫자를 입력하여 원하는 버전의 python을 선택할 수 있습니다.

카테고리: Linux | 댓글 남기기

[Design Patterns] Model View Controller 패턴

MVC(Model-View-Controller)

MVC는 Model-View-Controller 의 약자입니다.

소프트웨어 설계 및 개발을 진행할때, 프로그램을 3가지 요소로 나누어 개발하는 ‘소프트웨어 디자인 패턴‘입니다.

MVC 패턴을 도입하면 도메인(비즈니스 로직) 영역과 UI 영역이 분리되므로 서로 영향을 주지 않고 유지보수가 가능합니다. MVC 패턴의 구조를 살펴보면서 각 컴포넌트가 무슨 역할을 수행하는지 알아보도록 하겠습니다.

MVC 패턴 개요

모델(Model)

DATA, 정보들의 가공을 책임지는 컴포넌트를 말합니다.

모델(Model)은 어플리케이션의 정보, 데이터를 나타냅니다. 데이타베이스, 처음의 정의하는 상수, 초기화 값, 변수 등을 뜻합니다. 비즈니스 로직을 처리한 후 모델의 변경사항을 컨트롤러와 뷰에 전달합니다.

모델은 다음과 같은 규칙을 가지고 있습니다.

  • 사용자가 편집하길 원하는 모든 데이터를 가지고 있어야 합니다.
  • 뷰나 컨트롤러에 대해서 어떤 정보도 알지 말아야 합니다.
  • 변경이 일어나면, 변경 통지에 대한 처리 방법을 구현해야만 합니다.

뷰(View)

사용자에게 보여지는 부분, 즉 유저 인터페이스(User interface)를 의미합니다.

MVC 패턴은 여러 개의 뷰(View)가 존재할 수 있으며, 모델에게 질의하여 데이터를 전달받습니다. 뷰는 받은 데이터를 화면에 표시해주는 역할을 가지고 있습니다. 모델에게 전달받은 데이터를 별도로 저장하지 않아야 합니다. 사용자가 화면에 표시된 내용을 변경하게 되면 모델에게 전달하여 모델을 변경해야 합니다.

뷰는 다음과 같은 규칙을 가지고 있습니다.

  • 모델이 가지고 있는 정보를 따로 저장해서는 안됩니다.
  • 모델이나 컨트롤러와 같이 다른 구성요소들을 몰라야 됩니다.
  • 변경이 일어나면 변경통지에 대한 처리방법을 구현해야만 합니다.

1.3. 컨트롤러(Controller)

모델(Model)과 뷰(View) 사이를 이어주는 브릿지(Bridge) 역할을 의미합니다.

모델이나 뷰는 서로의 존재를 모르고 있습니다. 변경 사항을 외부로 알리고 수신하는 방법만 있습니다. 컨트롤러(Controller)는 이를 중재하기 위해 모델과 뷰에 대해 알고 있어야 합니다. 모델이나 뷰로부터 변경 내용을 통지 받으면 이를 각 구성 요소에게 통지해야 합니다. 사용자가 어플리케이션을 조작하여 발생하는 변경 이벤트들을 처리하는 역할을 수행합니다.

컨트롤러는 다음과 같은 규칙을 가지고 있습니다.

  • 모델이나 뷰에 대해서 알고 있어야 합니다.
  • 모델이나 뷰의 변경을 모니터링 해야 합니다.
카테고리: Design Patterns | 댓글 남기기

Test Driven Development(테스트 주도 개발, TDD)

Test Driven Development(테스트 주도 개발, TDD) 란?

TDD는 Test Driven Development의 약자로, ‘테스트 주도 개발’이라고 합니다.

일반적인 개발 과정에서는 요구사항을 분석 후 설계를 마친 뒤에 프로덕션 코드(Production code)를 작성하는 합니다. 상황에 따라 프로덕션 코드를 작성한 후에 테스트 코드를 추가할 수도 있는데 이는 단위테스트이며, TDD와는 다릅니다.

TDD는 요구사항을 분석후에 테스트코드를 먼저 작성(Test First Development)하고 이후에 프로덕션 코드를 작성합니다. 이후에 프로덕션 코드와 테스트 코드를 리팩토링하는 과정을 반복하여 코드의 완성도를 높힙니다.

TDD = TFD(Test First Development) + Refactoring

Refactoring : 설계의 과정 중 하나, 기능의 변화 없이 클래스 구조, 메서드 분리를 하는 설계의 과정

TDD의 아이러니 중 하나는 테스트 기술이 아니라는 점이다. TDD는 분석 기술이며, 설계 기술이기도 하다.
Kent Beck, Test Driven Development by Example 중

TDD를 하는 이유

  • 디버깅 시간을 줄임
  • 동작하는 문서 역할
  • 코드 리팩토링에 대한 두려움을 줄여줌

TDD 싸이클

  • 실패하는 테스트를 구현한다.
  • 테스트가 성공하도록 프로덕션 코드를 구현한다.
  • 프로덕션 코드와 테스트 코드를 리팩토링 한다.

TDD 원칙

  • 원칙1 – 실패하는 단위 테스트를 작성할 때까지 프로덕션 코드를 작성하지 않는다.
  • 원칙2 – 컴파일은 실패하지 않으면서 실행이 실패하는 정도로만 단위 테스트를 작성한다.
  • 원칙3 – 현재 실패하는 테스트를 통과할 정도로만 실제 코드를 작성한다.
카테고리: TDD(Test-driven development) | 댓글 남기기

MPEG-2 TS(Transport Stream)

MPEG-2 시스템 개요

MPEG-2 시스템 표준

  • MPEG(Moving Picture Expert Group)-2 시스템은 비디오, 오디오 Elementary Stream(ES)을 저장 또는 전송하기 위하여 단일(single) 혹은 다중(Multiple) 스트림 멀티미디어 정보를 다중화(Multiplexing)하는 방식을 규정한 표준(ISO/IEC 13818-1)
  • MPEG-2 시스템에는 용도에 따라 Transport Stream(TS), Program Stream(PS)의 두 가지의 형태의 스트림을 제공

표 1 – Transport Stream과 Program Stream[5]

TS

(Transport Stream)

  • 전송용 스트림
  • 전송 에러가 존재하는 (error-prone) 전송 매체에 이용
  • 일정한 길이(188byte)의 packet으로 구성
  • 27MHz 단위의 PCR (Program Clock Reference)을 사용

PS

(Program Stream)

  • 저장용 스트림
  • 전송 에러가 없는 (error-free) 전송 매체에 이용
  • 가변 길이의 pack으로 구성
  • 27MHz 단위의 SCR (System Clock Reference)을 사용

PSI / SI / Section

서비스  정보는  수신기가  Transport Stream(TS)을  복호화 할  수  있게  하는 PSI(ISO/IEC IS MPEG-2 System 13818-1[1])와 선택된 프로그램 안내의 근간을 이루는 SI(DVB EN 300 468[2])를 포함한다.[3]

Section은 PES에 포함되는 오디오, 비디오 데이터를 제외한 나머지 정보들을 칭하며 하고 방송 수신 정보 PSI(Program Specific Information)와 방송 부가 정보 SI (Service Information) 및 기타 일반적인 데이터들이 여기에 해당한다. 실제로 Section은 구체적인 데이터인 Table의 일부분이고 수신부에서는 Packetized되서 전송되는 여러 개의 Section을 모아서 하나의 Table을 구성해야 유효한 정보를 얻을 수 있다. 실제로 각 Section Header의 신택스를 보면 section_number와 last_section_number와 같은 값이 있는데 해당 값을 통해 Packet을 재조립하여 하나의 Table을 완성하게 된다.

때때로 Table의 사이즈가 TS packet 사이즈보다 작은 경우가 있는데 이 경우에는 section_number와 last_section_number 값이 모두 0x00이 된다. Section Header 신택스 중에 table_id라는 값이 있는데, 수신부에서는 이 값을 이용하여 Packet에 어떤 Table 정보가 저장되어 있는지 알 수 있다.[7]

MPEG 다중화

그림 1 – MPEG 다중화[8]

그림 1는 MPEG 시스템의 다중화 과정을 통해 TS의 생성과정을 보여주고 있다. Encoder에 의해 코딩 된 비디오, 오디오 ES(Element Stream)는 가변적 크기로 잘라낸 후 헤더를 붙여 PES Packet이 된다. 이때 PES Packet의 크기는 고정되지 않고 가변적이며, PES Header에는 영상, 비디오의 싱크 정보(DTS, PTS) 등이 들어간다. 이 PES 패킷을 고정된 크기 184byte로 잘라내고 4byte Header를 붙여 TS Packet으로 변환한다. TS Packet은 최종적으로 하나의 TS 스트림으로 다중화 되게 된다.

PES / TS / PS

그림 2 – PES, TS, PS의 상관 관계

TS와 PS의 가장 큰 차이점은 기본단위(Packet, Pack)의 길이 이다. PS 스트림의 경우 저장용 스트림이기 때문에 저장매체에서 스트림을 읽는 경우 에러가 발생할 확률이 낮아 Pack의 길이가 가변적 이어도 문제가 되지 않는다. 그러나 전송용 스트림인 TS 스트림의 경우 전송 도중에 에러가 발생할 확률이 높기 때문에 Packet의 길이를 188byte로 고정하여 에러로 인한 데이터 손실을 최소화 한다.

TS 스트림은 Packet의 길이를 188byte로 고정시키기 위한 과정을 거치기 때문에 수신단에서 원본 데이터를 재조립하기 위한 부가적인 정보가 들어가게 된다. 이 정보들은 TS Header에 저장되며 수신단에서는 4byte인 TS Header를 분석하여 나머지 184byte Payload 데이터를 재조립한다.

그림 3 – ITU-T Rec.H.222.0 | ISE/IEC 13818 transport packet[1]

위 그림 3은 TS Packet의 구조를 보여주고 있다. 앞서 설명한 것처럼 TS Header는 기본적으로 4byte로 구성되고 필요에 따라 adaptation filed가 추가될 수 있다. TS Header의 구성을 살펴보도록 하겠다.

  • sync_byte (8 bit) : 0x47로 고정된 값을 갖고 TS Packet의 시작을 표시한다.
  • transport_error_indicator (1 bit) : 전송된 Packet에 에러가 있는지 없는지를 표시하며, ‘0’ 이면 에러가 없고 ‘1’이면 에러를 포함한다.
  • payload_unit_start_indicator (1 bit) : TS Packet의 경우 원본 데이터를 쪼개서 보내기 때문에 현재 packet이 포함하고 있는 데이터가 원본 데이터의 어느 부분을 포함하고 있는지를 알아야 수신단에서 원본 데이터를 재조립할 수 있다. 이 flag는 원본 데이터의 시작이 Packet에 있는지 없는지를 알려준다. 값이 ‘0’이면 해당 Packet에 원본 데이터의 중간 부분이 포함되어 있고 ‘1’이면 원본 데이터의 처음 부분이 포함되어 있다. 뒤에 나오는 continuity counter와 함께 사용된다.
  • transport_priority_indicator (1 bit) : TS Packet의 우선 순위를 표시하며, 값이 ‘0’인 Packet보다 ‘1’인 packet이 우선순위가 높다.
  • PID (13 bit) : Packet에 포함된 Payload의 데이터가 어떤 데이터인지를 알려주는 flag로 수신단에서는 이 값을 보고 필요한 데이터를 구분한다.

그림 4 – PID Table[1]

  • transport_scrambling_control(2 bit) : Payload의 scramble 유,무를 표시한다.

그림 5 – Scrambling control values[1]

  • adaptation_field_control(2 bit) : Adaptation field의 유,무를 표시한다.

그림 6 – Adaptation field control values[1]

  • continuity_counter(4 bit): 같은 PID를 갖는 Packet의 경우 1씩 증가하면서 전송되며 값이 15 (4 bit의 max값)가 넘어가면 다시 0으로 초기화 된다. Adaptation field만 전송되는 Packet의 경우에는 값이 증가하지 않는다.

ATM & TS Packet

그림 7 – ATM Packet으로 구성되는 TS Packet[4]

추가적으로 TS는 ATM(Asynchronous Transfer Mode) 방식으로 전송되는데 한 개의 회선을 여러 개의 채널로 분할해서 동시에 통신하는 다중화 방식 중 하나이다. 기존의 방송망이 ATM방식을 사용하므로 호환성을 위해서 디지털 방송 또한 ATM방식을 사용한다. ATM packet은 5byte의 Header와 1byte의 AAL(ATM Adaptation Layer) 그리고 47byte의 payload로 구성되어 총 53byte의 크기를 갖는다. TS Packet의 사이즈가 188byte인 이유는 ATM Packet에서 ATM Header 와 ALL을 제외한 payload 데이터 4개를 합쳐 구성되기 때문이다. (47byte x 4 = 188byte)

MPEG 동기화

그림 8 – MPEG 동기화[8]

MPEG 시스템에서는 영상 및 음성 미디어 간 Encoder 및 Decoder 간의 시각 기준의 일치를 위한 동기화가 필요하다.

STC

STC(System Timing Clock) : MPEG 시스템 송신 측에서 발생시키는 공통의 기준 클럭(27 Mhz)으로 수신 측에서는 이에 맞추어 STC 타이밍에 동기화 한다. 즉, 송수신부에서 동작의 기준이 되는 시스템 기준 클럭이다.

PCR / SCR

PCR, SCR은 송신 측에서 주기적으로 전송하고, 수신 측에서 이에 맞춰지는 기준 되는 시간 값이다. 송신 측에서 송신단 출력 순간의 STC 값을 표본화하여 주기적으로 전송하고, 수신측은 수신단 입력 순간에 수신단 STC를 보정하여 STC를 맞춘다.

  • PCR(Program Clock Reference) : MPEG-2 TS의 프로그램 시각 기준 값으로 프로그램 마다 기준 되는 시각 기준 값이다. 여러 프로그램들이 모여 하나의 TS를 구성하는 경우에는 각 프로그램 마다 PCR이 다른 시간 기준을 갖을 수 있으나, 가능하면 단일한 PCR을 갖는 것이 바람직하다. 인코더 시스템의 시간을 27Mhz의 System Clock으로 샘플링한 값으로 오디오, 비디오 재생 시 기준 시각으로 사용된다. 42 (33 + 9) bit 정확도를 가지고 있으며 MPEG-1과의 호환성을 위해 33 bit의 90Khz의 정확도를 가지는 PCR_base값과 27Mhz의 정확도를 가지는 9 bit의PCR_ext로 구성되어진다. TS Packet Adaptation Field에 위치하며, 0.1초 이내 최소 1회 이상 전송된다.
  • SCR(System Clock Reference) : MPEG-1 PS의 시스템 시각 기준 값이다. PS는 단일 프로그램으로 이루어지므로 SCR 값을 항상 하나이다. PS의 Pack Header의 SCR 필드를 통해 전송되며, 0.7초 이내 최소 1회 이상 전송된다.

DTS / PTS

기준 클럭 시간 값에 따라, 오디오,비디오 ES 각각에 대해 PTS/DTS 타임스탬프를 사용한다. 디코딩을 위한 시각이 DTS(Decoding Time Stamp)이며, 재생을 위한 시각이 PTS(Presentation Time Stamp) 이다.

  • DTS(Decoding Time Stamp) : 수신된 오디오, 비디오 정보가 디코딩 되어져야 하는 시각을 나타내며 PES Packet Header에 위치한다.
  • PTS(Presentation Time Stamp) : 오디오나 비디오가 실제로 재생 되어져야 하는 시각을 나타내며, PES Packet Header에 위치한다.

디지털 방송 Channel Search

디지털 방송 수신과정

그림 9 – 위성방송 데이터 수신 구조

그림 3은 하나의 위성에서 송신하고 있는 정보들의 구조를 보여주고 있다. 여기서는 1개의 위성에3개의 Transponder(TP)가 존재하고 있다. TP는 방송국 단위로 생각할 수 있다. 우리나라 지상파 방송국(SBS, KBS, MBC)의 경우 각 방송국마다 보통 한 개의 서비스(=채널)만을 제공하고 있지만 그림 1의 TP2는 세 개의 서비스를 제공하고 있다. 특정 방송국의 경우 다수의 서비스를 하나로 묶어 부케단위로 제공하기도 한다. 서비스 정보를 확인하기 위해서는 위성에서 데이터를 송신할 때 사용하는 주파수 정보 등을 알고 있어야 한다. 구체적으로 Frequency, Symbol rate, Polarization(Horizontal, Vertical) 등의 정보가 있어야 TP에 락킹하여 방송 신호를 수신할 수 있다. 수신기(셋탑박스)에서는 기본적으로 위성 정보를 저장하고 있지만 없는 경우에는 원하는 위성 정보(www.lyngsat.com)를 확인 후 수동으로 방송 신호를 수신할 수 있다. 일반적으로 셋탑박스에서는 이 과정을 최초 한번만 수행하면 데이터베이스에 저장하고 그 이후에는 이 과정을 수행하지 않는다. 물론 방송국 혹은 위성에서 변경사항이 발생하면 그 정보를 새로 수신하여 반영하여야 한다.

Channel Search 방법

Tuner Locking

그림 10 – 위성방송 서비스 Channel Search 과정[7]

셋탑박스는 TP 정보를 통해 락킹을 시도하게 되는데 TP정보를 얻는 방법은 크게 2가지다. 첫째, TP 정보를 OP에게 입수하여 미리 플래시 메모리에 저장하는 방법이 있으며, 둘째, NIT 테이블을 파싱하여 테이블 내의 delivery system descriptor를 읽는 방법이다.

TP가 락킹된 후 튜너의 DeMod와 DeMux를 거치게 되면 TS 스트림이 출력되고 SI 데이터 파싱을 위해 sync_byte(0x47)을 찾는다. sync_byte를 찾으면 188byte 이후의 byte를 조회하여 sync_byte인지 확인하고 이 과정을 3회 연속 성공하면 정상적인 TS 스트림으로 보고 최종 락킹하게 된다.

TP 락킹이 성공적으로 완료되면 PAT를 파싱하게 되고 PAT 파싱을 통해 PMT의 PID와 개수 등을 알게된다. PAT 파싱을 완료하면 PMT 테이블의 개수만큼 PMT를 파싱하게 되고 PMT 파싱을 통해 해당 서비스의 Video PID, Audio PID 등을 파악한다. 마지막으로 SDT를 파싱하여 각 서비스별 채널명, 속성정보 등을 파악하게 된다.

PAT 파싱

튜너가 특정 TP를 락킹하여 TS 스트림을 출력하게 되면 가장 먼저 PID가 0x000인 PAT 테이블을 파싱 하게 된다. PAT 테이블은 서비스(=채널)들의 정보를 담고 PMT 테이블의 PID를 얻어낸다. 하나의 TP에는 PAT 테이블이 한 개로 유일하며, 최소 0.7초 마다 한번씩 발생하는 것으로 알려져 있다.

그림 11 – Program association section[1]

PMT 파싱

PAT 파싱에서 얻어낸 PMT PID에 따라 PMT 테이블을 파싱한다. PMT는 하나의 TP에 서비스의 개수 즉 채널 개수만큼 있으며 한 TP에 4개의 방송이 있다면 PMT 테이블도 4개가 있다. PMT 테이블은 Video PID, Audio PID, CAT PID 등의 정보를 담고 있다. 이렇게 얻어낸 서비스별 PID의 리스트를 셋톱박스에 저장해두고 이후 사용자가 채널을 변경하면 해당 채널에 맞춰 화면에 디스플레이 하고 오디오를 구동하는데 쓰이게 된다.

예를 들어 BBC HD라는 방송이 있을 때 Video PID가 0x1001, Audio PID가 0x1002라고 가정하면, 사용자가 BBC HD라는 방송으로 채널을 돌리면 화면에는 PID 0x1001을 갖는 비디오 스트림을 뿌려주고 0x1002라는 사운드 스트림을 틀어주면 되는 것이다. 방송이 바뀔 때 마다 스트림의 PMT 테이블을 찾고 Video PID, Audio PID 등을 얻어 낸다면 채널 변경시간(Zapping Time)이 오래 걸리기 때문에 보통 서비스(=채널) 서치 과정에서 이러한 정보를 미리 셋톱박스의 데이터베이스에 저장해 놓는다.

그림 12 – TS program map section[1]

SDT 파싱

SDT 파싱을 통해 서비스명을 얻어내고 채널과 관련된 속성 정보를 얻어내어 마찬가지로 셋톱박스의 데이터베이스에 저장해 놓는다. 즉 방송의 이름을 알아내고 관련된 정보를 알려주는 것이 SDT의 역할이다.

그림 13 – Service description section[2]

Channel Search Pseudo 코드 정리[7]

References

  • [1] ISO/IEC 13818-1
  • [2] ESTI, EN 300 468
  • [3] 한국정보통신기술협회, TTAS.KO-07.0008/R1, 2000
  • [4] 유시룡, 장규환, 이병욱, 김종일, 정해묵, MPEG 시스템, 브레인코레아
  • [5] 강성곤, MPEG-2 System, 휴맥스, 2008
  • [6] 김규현, MPEG-2 ES/PES/TS/PSI, Media Lab of Kyung-Hee UNIV
  • [7] Google, “디지털 방송 채널 서치”, http://blog.naver.com/windheim/90048572443, (2009. 6. 8)
  • [8] Google, “MPEG 시스템”, http://www.ktword.co.kr/test/view/view.php?nav=2&no=3682&sh=MPEG, (2018. 11. 05)
카테고리: MPEG | 댓글 남기기