본문 바로가기

알고리즘, 문제해결/알고리즘, 자료구조21

Longest Common Subsequence/Substring (LCS) Algorithm Dynamic Programming 카테고리의 알고리즘입니다. 두 개의 문자열이 있다고 가정합시다. 각각 subject, target이라고 부르겠습니다. subject = ACAYKP, target = CAPCAK이라고 합니다. 이 때, subject = ACAYKP의 부분 수열이라 함은 다음을 가리킵니다. 0, A, CAY, CYP, ACAYKP... 등등. 가장 작은 부분 수열은 공집합이며, 가장 큰 부분 수열은 문자열 그 자신입니다. 여기서 중요하게 짚고 넘어가야 할 점이 있습니다. LCS라는 표현을 쓸 때, longest common SUBSEQUENCE인지, longest common SUBSTRING인지 잘 확인해야 합니다. 번역하면 최장 공통 수열, 최장 공통 문자열이 되겠습니다. 이 둘의 .. 2020. 11. 15.
비트마스크 (Bitmask) 연산 "프로그래밍 대회에서 배우는 알고리즘 문제해결전략", 16장. 비트마스크 를 읽고 공부한 것을 기반으로 작성하였습니다. 우리가 사용하는 컴퓨터의 자료는 모두 2진수를 기반으로 이루어져 있습니다. 컴퓨터가 2진수를 이용한다 함은 보통은 컴퓨터를 사용하는 사람, 즉 우리에게는 큰 상관이 없지만, 프로그램 작성 시 연산 시간과 공간적 효율을 고려한다면 이진수를 직접 다루는 것이 효율적일 것입니다. 이러한 목적으로 이진수 표현을 자료구조로 쓰는 기법을 비트마스크 (bitmask) 라고 합니다. 비트마스크 기법은 아래와 같은 이점을 가진다고 합니다: 더 빠른 수행 시간. 대부분 O(1) 의 시간복잡도를 가져, 통상적인 다른 자료구조보다 훨씬 빠른 연산속도를 자랑합니다. 다만 비트마스크를 사용하는 경우 원소의 수가.. 2020. 5. 29.
문자열 인코딩 (Run Length Encoding; RLE Algorithm) 아주아주 오랜만에 쓰는 블로그 글. 편입학 준비를 하던 저에서 취업준비로 코딩 공부를 하는 저로 돌아왔습니다. 일이 꼬여서 한 반년~1년 정도 더 학교에서 전공 과목 듣고 졸업할 것 같아요. 오늘은 이번 주 토요일로 예정되어 있는 카카오 인턴십 코딩 테스트를 위한 공부를 하고 있었어요. 작년 하반기 신입 채용 기출 문제를 보고 있었는데, 그 중 1번 문제부터 막히는 바람에... 어떻게 접근할까 생각해 보다가 일단 기본이 되는 알고리즘부터 공부하기로 했습니다. 검색해 보니 RLE 알고리즘이라는 게 있더라구요. 이 블로그의 글을 보고 공부했습니다. 거의 코드를 따라 친 수준이긴 한데... 기본적으로 RLE 알고리즘이란, 동일한 패턴이 반복되는 문자열을 압축하는 알고리즘 입니다. aaabbcccccddee 라.. 2020. 5. 6.

티스토리툴바