본문 바로가기
728x90

알고리즘

[알고리즘] 최장 공통 부분 수열 (LCS, Longest Common Subsequence)
Algorithm/정리 2022. 7. 2. [알고리즘] 최장 공통 부분 수열 (LCS, Longest Common Subsequence) 최장 공통 부분 수열 LCS (Longest Common Subsequence) 주로 최장 공통 부분수열(Longest Common Subsequence)을 나타내지만 최장 공통 문자열(Longest Common Substring)을 말하기도 한다. 최장 공통 문자열(Longest Common Substring)은 반드시 부분 문자열이 연결된 형태여야한다. banana, vbankn 최장 공통 부분수열(Longest Common Subsequence)은 떨어져있어도 상관없다. bdanvv, vbkkanm 이번에 다룰 LCS 알고리즘은 최장 공통 부분수열(Longest Common Subsequence)이다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종..
CS/Algorithm 2021. 10. 29. 알고리즘의 개요 알고리즘이란? 주어진 문제를 해결하기 위한 잘 정의된 동작들의 유한 집합 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것 문제를 풀거나 작업을 수행하기 위한 단계적인 방법 자료구조와 알고리즘의 차이점 알고리즘 : 문제 해결의 방법을 정의 자료구조 : 행위의 객체(무엇을) 알고리즘을 사용하는 이유 효율성 - 성능과 가장 연관이 있다. (code size를 작게 한다.) 추상화 - 중요한 기능들을 사용자들로부터 보지 못하게 한다. (숨긴다.) 재사용성 - 문맥을 자유롭게 재사용 가능하다. 모듈화 알고리즘으로 어떤 문제를 푸는가? 네비게이션 시스템 두 지점 간의 최단 경로 검색 최단 시간이 걸리는 경로 검색 인터넷 검색 원하는 결과를 최대한 빨리, 최대한 만족스럽게 제공 기본..
728x90

티스토리툴바