외부 메모리에서 문자열을 효율적으로 탐색하기 위한 인덱스 자료 구조

박근수(Kunsoo Park),나중채(Joong Chae Na) 한국정보과학회 2005 정보과학회논문지 : 시스템 및 이론 Vol.32 No.11·12

본 논문에서는 새로운 외부 메모리 인덱스 자료 구조인 접미사 B-tree를 제안한다. 접미사 B-tree는 String B-tree와 마찬가지로 문자열을 키로 가지는 B-tree이다. String B-tree의 노드는 복잡한 Patricia trie로 구현된 반면, 접미사 B-tree의 노드는 일반적인 B-tree처럼 배열로 구현되어 보다 간단하고 구현하기 쉽다. 그럼에도 불구하고 접미사 B-tree에서 배열을 이용하여 String B-tree만큼 효율적으로 분기를 찾을 수 있다. 결과적으로 문자열 알고리즘 분야에서 기본적이고 중요한 문제인 문자열 매칭을 String B-tree와 동일한 디스크 접근을 사용하여 수행할 수 있다. We propose a new external-memory index data structure, the Suffix B-tree. The Suffix B-tree is a B-tree in which the key is a string like the String B-tree. While the node in the String B-tree is implemented with a Patricia trie, the node in the Suffix B-tree is implemented with an array. So the Suffix B-tree is simpler and easier to be implemented than the String B-tree. Nevertheless, the branching algorithm of the Suffix B-tree is as efficient as that of the String B-tree. Consequently, the Suffix B-tree takes the same worst-case disk accesses as the String B-tree to solve the string matching problem, which is fundamental and important in the area of string algorithms.

미국 메소드 연기의 태동을 바탕으로 한 카메라 연기의 제안

박근수(Park, Kunsoo),김석래(Kim, Sukrae) 인제대학교 디자인연구소 2009 Journal of Integrated Design Research (JIDR) Vol.8 No.2

스타니슬라브스키가 소개되기 이전까지 영국을 비롯한 유럽의 연기훈련방법에 많은 영향을 받아왔던 미국의 연기훈련방법은 1920년대 몇 차례에 걸친 모스크바 예술극장(Moscow Art Theatre) 의 미국 순회공연과 러시아에서 이주해 온 리차드 볼라브스키(Richard Boleslavsk)가 그의 책 ‘Acting-The first six lessons’ 을 통해 스타니슬라브스키를 본격적으로 소개하면서부터 큰 전기를 맞이하게 된다. 1931년 마침내 헤롤드 클러맨(Harold Clurman), 케릴 크로포드(Cheryl Crawford) 그리고 리 스트라스버그(Lee Strasberg)는 모스크바 예술극장(Moscow Art Theatre)이 모델이 된 씨어터 그룹(Theatre Group)을 만들어 1941년 해체할 때까지 미국의 메소드 연기(The Method)를 연구하고 발전시키는 데 기초적 역할을 하게 된다. 이후 미국의 매소드 연기이론은 배우의 감정적 측면이 강조한 리스트라스버그(Lee Strasberg), 주어진 환경을 이용한 이성적이고 사회적인 측면을 강조한 스텔라 아들러(Stella Adler) 그리고 살아 있고 진실 된 행동을 만드는데 초점을 맞춘 샌포드 마이즈너(Sanford Meisner)에 의하여 지속적인 발전을 이루게 된다. 특히 행동의 사실(Reality of doing), 반복훈련(Repetition exercise), 반응(Reaction) 그리고 즉흥성(Improvisation) 등을 통하여 샌포드 마이즈너는 보다 사실적이며 진실 된 연기훈련방법을 발전시켰다. 그의 이런 독창적인 연기훈련은 그에게 배운 많은 배우들이 연극무대는 물론 영화에서 활발하게 활동하는 것을 통해 그 가치를 알 수가 있으며, 특히 그의 훈련방법은 영상 매체관련 산업이 커짐으로써 극도의 사실성, 반응 그리고 즉흥성과 순발력이 강조되는 요즘의 카메라연기에서 더욱 큰 의미를 찾을 수 있다고 본다. 이 글은 짧게나마 미국의 메소드 연기 형성과정을 통해 그것의 역사와 의미 그리고 그 속에서 샌포드 마이즈너의 의미와 가치를 알아보고 카메라 앞에서의 연기훈련에 도움을 주는데 그 의미가 있다. American acting training method that had been influenced by European acting training method including the Britain met the big change because of the introduce of Stainslavsky through the Moscow Art Theatre’s several tours in U. S. A and Richard Boleslavsk’s book ‘Acting-The first six lessons’. In 1931, finally Harold Clurman, Cheryl Crawford and Lee Strasberg formed Theatre Group that Moscow Art Theatre was the model, and They did essential role in studying and development of American method acting until disorganization in 1941. After disorganization, American method had developed continuously by Lee Strasberg who accomplished the method acting that emotional side of actor was emphasized, also by Stella Adler who made acting training method that emphasized rational and social side that used given environment and by Sanford Meisner who focused on true and living behavior. Especially, Sanford Meisner developed his own Method acting to create realistic and true behavior through Reality of doing, Repetition exercise, Reaction and Improvisation. We can know its value of his unique method acting if see that many actors who learned from him have acted in the play stage as well as movie, and specially, his training method that means a lot to extreme reality, response and moment-to-moment spontaneity is encouraged in camera work because industry related to image media has been increased in these days. This study examines history and meaning of method acting and value of Sanford Meisner through formation process of method acting, and also tries to present the way to develop the acting in front of the camera.

하이퍼텍스트에서 스트링 매칭 알고리즘

박근수(Kunsoo Park),김동규(Dong Kyue Kim) 한국정보과학회 1994 한국정보과학회 학술발표논문집 Vol.21 No.2B

본 논문에서는 비선형구조를 가지는 하이퍼텍스트에서의 스트링 매칭 알고리즘을 연구하였다. 먼저 하이퍼텍스트의 계산모델을 그래프 G=(V,E)형태로 제시하였으며, 하이퍼텍스트에서의 스트링 매칭문제를 다음과 같이 정의하였다: 그래프 G의 각 노드 V_i가 텍스트 T_(v_i)를 가질때 하이퍼텍스트 상에 나타난 모든 패턴을 찾으라, 패턴의 길이는 m이고, 텍스트들의 길이의 합은 N이다. 주어진 그래프가 트리(Tree)구조일 경우에는 선형시간에 패턴 스트링을 찾아내는 알고리즘이 알려져 있다. 본 논문에서는 대그(DAG)구조일 경우에 O(N+│E│)m시간에 모든 패턴 스트링을 찾는 알고리즘을 구하였다. 그리고 G가 임의의 그래프일 때의 스트링 매칭 알고리즘을 제시하였다.

“암호학 및 보안의 새로운 이슈” 특집을 내면서

박근수(Kunsoo Park),박정흠(Jung Heum Park),임형석(Hyeong Seok Lim) 한국정보과학회 2005 정보과학회지 Vol.23 No.1

윈도우 방법과 인수 방법을 혼합한 빠른 멱승 알고리즘

박희진(Heejin Park),박근수(Kunsoo Park),조유근(Yookun Cho) 한국정보보호학회 2000 정보보호학회논문지 Vol.10 No.4

윈도우 방법과 인수 방법을 혼합 적용하면 멱승 연산에 사용되는 곱셈 연산의 횟수를 줄일 수 있다. 지수가 512비트일 때 윈도우의 크기가 5인 윈도우 방법은 607번 정도의 곱셈 연산을 필요로 하는 데 반해 윈도우와 인수 방법을 혼합한 방법은 599번 정도의 곱셉연산을 필요로 한다. 이는 현실적으로 가능한 멱승 연산 중에서 가장 적은 수의 곱셈 연산을 요구하는 방법이다. We show how to reduce the number of multiplications required for an exponentiation by using a window method and a factor method. This method requires 599 multiplications for a 512-bit integer exponent while the window method with window size 5 requires 607 multiplications. This method requires fewest multiplications among practical exponentiation algorithms.

윈도우 방법과 인수분해 방법을 혼합한 빠른 멱승 알고리즘

박희진(Heejin Park),박근수(Kunsoo Park),조유근(Yookun Cho) 한국정보과학회 2000 한국정보과학회 학술발표논문집 Vol.27 No.2Ⅰ

윈도우 방법과 인수분해 방법을 혼합 적용하면 멱승 연산에 사용되는 곱셈 연산의 횟수를 줄임으로써 멱승 연산을 빠르게 수행할 수 있다. 지수가 512비트일 때 윈도우의 크기가 5인 윈도우 방법은 607번 정도의 곱셈 연산을 필요로 하는 데 반해 윈도우와 인수분해 방법을 혼합한 방법은 599번정도의 곱셈연산을 필요로 한다. 이는 현실적으로 가능한 멱승 연산 중에서 가장 적은 수의 곱셈 연산을 요구하는 방법이다.

K - 비대응 문제를 위한 선형 이하의 평균 시간 알고리즘

박경수(KyungSoo Park),박근수(KunSoo Park) 한국정보과학회 1995 정보과학회논문지 Vol.22 No.5

근사 스트링 매칭에서는 k 비대응 문제와 k 차이 문제가 연구되어져왔다. 길이가 n 인 텍스트 스트링, 길이가 m 인 패턴 스트링과 정수 k 가 주어졌을 때, k 비대응 문제는 텍스트에 나타나는 근사패턴을 찾는 문제인데 여기에서 근사 패턴이란 패턴과의 Hamming 거리가 K 이하인 부분스트링이다. 본 논문에서는 k 비대응 문제를 푸는 두 개의 알고리즘을 제시하는데, 두 알고리즘은 k = O(m/1og m) 를 만족하는 k 에 대하여 O(kn(1og m)m) 평균 시간과 O(m) 메모리를 사용하는 알고리즘이다. 이 두 알고리즘은 Quong이 개발한 O(kn(log m)²/(mlog log m)) 평균 시간과 O(m(log m)²/log log m) 메모리를 사용하는 알고리즘보다 우수한 것이다. In approximate string matching two problems have been considered in the literature, the k-mismatches problem and the k-differences problem. Given a text string of length n, a pattern string of length m, and an integer k, the k-mismatches problem is to find all approximate occurrences of the pattern in the text such that each occurrence has Hamming distance less than or equal to k with the pattern. We present two algorithms for the k-mismatches problem both of which take O(kn(log m)/m) expected time and use O(m) space for k=O(m/log m). These algorithms improve Quong′s O(kn(log m)²/(mlog log m)) expected time algorithm that uses O(m(log m)²/log log m) space.

CREW PRAM 에서 Red - Black 트리 병렬 알고리즘

박희진(Heejin Park),박근수(Kunsoo Park) 한국정보과학회 1995 한국정보과학회 학술발표논문집 Vol.22 No.2B

본 논문에서는 n 개의 아이템을 가지고 red-black 트리를 생성하는 알고리즘과 red-black 트리에서 k 개의 아이템을 검색, 삽입, 삭제하는 알고리즘을 제시한다. n 개의 아이템으로 red-black 트리를 만드는 데는 n 개의 처리기로 상수시간이 걸린다. n 개의 노드로 구성된 red-black 에서 k 개의 아이템을 검색하는 데는 O(log n) 시간이 걸리고 삽입과 삭제는 O(log n + log k) 시간이 걸린다. 검색, 삽입, 삭제 알고리즘 모두 k 개의 처리기를 사용한다.

안전한 전자봉인을 위한 인증 프로토콜 설계

박성수(Seongsoo Park),이문규(Mun-Kyu Lee),김동규(Dong Kyue Kim),박근수(Kunsoo Park),김호원(Howon Kim),정교일(Kyoil Chung) 한국정보과학회 2005 한국정보과학회 학술발표논문집 Vol.32 No.2

최근 국제물류에서 화물 컨테이너의 운송을 보다 안전하고 효율적으로 관리하기 위하여 수출입절차 규제가 강화되고, 도난, 밀매, 테러 등의 범죄를 예방하기 위한 새로운 정책과 기술이 도입되고 있다. 특히, 빠르게 실용화가 진행되고 있는, RFID 기술을 사용한 무선인식 전자봉인(e-seal)은 기존의 기계적 봉인장치를 대체함으로써 컨테이너 운송의 안전성을 보장하고, 선적 및 하선 절차의 효율을 높인다. 수년간 e-seal의 ISO 국제표준화가 진행되어 왔으며, 최근 e-seal의 데이터 보호에 대한 표준화가 진행 중이다. 본 논문에서는 e-seal의 실질적인 사용 환경과 기존의 명령어 표준규격을 고려하여 안전한 e-seal을 위한 새로운 명령어들을 설계하고, EAP를 응용하여 e-seal과 리더기간의 상호 인증 프로토콜을 제시한다. 그리고 이를 다시 효율적으로 개선하여 e-seal에 적합한 상호 인증 프로토콜을 제시한다.

볼록 이분할 그래프에서 최대 매칭을 찾기 위한 개선된 Boolean 회로

박은희(Eunhui Park),박근수(Kunsoo Park) 한국정보과학회 2006 한국정보과학회 학술발표논문집 Vol.33 No.1

Boolean 회로는 parallel 알고리즘을 위한 단순하면서도 실제적인 모델이다. Chung & Lee은 Boolean 회로 모델에서 볼록 이분할 그래프를 위한 최대 매칭을 찾는 O(log²n+logn · loglogn · logb)depth와 O(bn³) size의 알고리즘을 제시하였다. 본 논문에서는 prefix computaion 및 ASCEND, odd-even-merge의 방법을 이용하여 이를 개선한 O(log²n · logb) depth, O(bn²logn) size의 최대 매칭 알고리즘을 제시한다.