LIS 알고리즘 - 최장 증가 부분 수열 찾기

  • LIS (Longest Increasing Subsequence) : 최장 증가 부분수열
    LIS란 임의의 수열이 주어졌을 때, 해당 수열에서 몇 개의 수들을 뽑아 만든 부분수열 중 오름차순으로 정렬된(strictly increasing) 가장 긴 수열을 뜻합니다.

이 때 LIS의 길이를 구하는 방법은 크게 세가지가 있습니다.

  • DP O(n2)
  • Binary Search O(nlogn)
  • Segment Tree O(nlogn)

오늘은 이 중 Binary Search, 즉 이분 탐색을 이용해 LIS의 길이와 수열을 찾는 방법을 알아보겠습니다.

Open Bw-Tree Performance Test

Test Case 생성기

instruction, thread 갯수와 insert ratio를 받아서 테스트 케이스가 적혀있는 tmp[num].txt 생성 (tmp1.txt, tmp2.txt …)

각 텍스트 파일에는 매 행마다 i num 혹은 d num 으로 입력, 삭제 할 키 값이 들어있음.

키 값은 랜덤으로 생성.

Sublime Text 세팅하기

서브라임 텍스트는 맥을 사며 코딩을 시작한 이후부터, 가장 오랫동안 가장 많이 사용해온 텍스트 에디터입니다.
기본 기능은 거의 없다시피 하지만 패키지 컨트롤과 약간의 설정을 더해주면 IDE 못지 않은 편의성을 제공해주기 때문에 매우 편리합니다.

Mac 클린 설치 이후 개발 환경 구축/세팅 하기

Mac osX은 매년 메이저 업데이트가 진행되며 올해에도 9월 25일에 High Sierra 에서 Mojave로 새로운 버전이 출시되었습니다. 기존의 OS에서 포멧 후 클린 설치를 하지 않는 업그레이드 기능을 지원하며 해당 기능을 통해 업데이트를 진행하는 것이 매우 간단하지만 그럼에도 불구하고 메이저 업데이트는 메이저 업데이트인지라 종종 예상치 못한 곳에서 해결하기 쉽지 않은 오류들을 생성해 내곤 합니다.

그렇기에 이러한 문제를 미연에 방지하고자 많은 맥 사용자들이 메이저 업데이트가 배포될 때마다 포멧후 클린 설치를 진행하곤 합니다. 저 또한 이러한 부류에 속하는 편인데 올해에는 귀찮음을 견디지 못하고 약 한달간 업데이트 상태에서 지속적으로 사용해 오다가 오늘 큰 마음을 먹고 포멧 후 재설치를 진행하였습니다.

앞으로도 매년 이러한 현상은 반복될 것이기에 무엇보다 미래의 귀찮음과 반복작업을 줄이기 위하여 이번 포스트를 마련해 보았습니다. 포멧 후 완벽하게 깨끗한 상태에서부터 어떠한 과정을 통해 다시 개발환경을 세팅할 것인지, 미래의 나를 위한 가이드라인입니다.

하지만 그 가이드라인이 사용된 적은 없었다고 합니다.

Mac Sublime Text C/C++/Python Build & Execute

서브라임 텍스트에서 C/C++/Python 빌드 / 실행 시키는 sublime-build 코드들은 쉽게 찾을 수 있지만 이들의 문제는 해당 프로그램이 루트 디렉토리에서 실행된 다는 것입니다.
코딩하다보면 상대경로가 월등히 편한경우가 많아 상대경로를 사용하도록 프로그램을 짰을 경우 이런 사소한 점이 큰 불편을 초래합니다.
그래서 쉘 스크립트와 ST의 빌드 시스템을 이용하여 컴파일 이후 프로그램이 위치한 폴더를 현재경로로 설정하여 프로그램이 실행하도록 만들었습니다.

Pagination


© 2021. All rights reserved.