극대 증가 부분서열을 찾는 선형 알고리즘

• 영문명: Linear-time algorithms for computing a maximal increasing subsequence
• 발행기관: 한국스마트미디어학회
• 저자명: 나중채
• 간행물 정보: 『스마트미디어저널』Vol12, No.6, 9~14쪽, 전체 6쪽
• 주제분류: 공학 > 컴퓨터학
• 파일형태: PDF
• 발행일자: 2023.07.31

국문 초록

최장 증가 부분서열(longest increasing subsequence)은 컴퓨터 과학 분야에서 오랫동안 연구되어온 주요 문제이다. 본 논문에서는 최장 조건을 극대로 완화한 극대 증가 부분서열(maximal increasing subsequence) 문제를 고려한다. 본 논문에서는 두 가지 버전의 증가 개념(단조증가, 순증가)에 대해, 알파벳 에 대한 서열의 극대 증가 부분서열을 구하는 선형시간 알고리즘을 제안한다. 극대 단조증가 부분서열을 구하는 알고리즘은 공간을 사용하고, 극대 순증가 부분서열을 구하는 알고리즘은 공간을 사용한다.

영문 초록

The longest increasing subsequence is a fundamental problem which has been studied for a long time in computer science. In this paper, we consider the maximal increasing subsequence problem where the constraint is released from the longest to the maximal. For two kinds of increasing (monotone increasing and strictly increasing), we propose linear-time algorithms computing a maximal increasing subsequence of an input sequence from an alphabet . Our algorithm for computing a maximal monotone increasing subsequence requires space and our algorithm for computing a maximal strictly increasing subsequence requires space.

목차

Ⅰ. 서론

Ⅱ. 본론

Ⅲ. 결론

REFERENCES

키워드

극대 증가 부분서열 증가 부분서열 서열 분석 문자열 알고리즘 maximal increasing subsequences increasing subsequences sequence analysis string algorithms