정화 코딩

1. LCS 알고리즘 설명어떤 두 문자열이 얼마나 유사한지를 수치화하기 위해 longest common subsequence(LCS)를 구한다. LCS란 공통 문자열 중 길이가 가장 긴 문자열을 말한다. 이 때 공통 문자열을 이루는 문자들 사이에 다른 문자열이 있어도 상관없으며 공통 문자열을 이루는 문자들의 순서만 동일하면 된다. LCS가 길수록 두 문자열이 유사도가 높다고 할 수 있다. 이 LCS의 길이와 LCS를 구하는 알고리즘이 LCS 알고리즘이며, 이를 직접 코드로 구현해보고자 한다. 2. LCS 알고리즘 구현 코드 (python)입력: 첫번째 줄에 문자열 X를 입력하고 두번째 줄에 문자열 Y를 입력한다. (문자열을 입력할 때는 문자와 문자 사이에 공백을 두고 입력한다.) 출력: 첫번째 줄에 LC..

구현 개요 파이썬으로 구현하는 이진 탐색은 2가지 방법이 있다. 첫 번째는 재귀 함수를 사용하는 것이고, 두 번째는 반복문을 이용하는 것이다. 구현을 위한 준비 target : 찾고자 하는 값 data : 오름차순으로 정렬된 list start : data의 처음 값 인덱스 end : data의 마지막 값 인덱스 mid : start, end의 중간 인덱스 구현 1. 반복문을 사용한 구현 def binary_search(target, data): start = 0 end = len(data) - 1 while start target: end = mid - 1 else: start = mid + 1 return None 2. 재귀 함수를 사용한 구현 def binary_search(target, data,..

탐색 (Search) 여러 데이터들 중에서 원하는 값을 찾는 알고리즘 1. 순차 탐색 (Linear Search) 💡 정의 리스트의 항목들을 처음부터 마지막까지 하나씩 순서대로 검사하는 알고리즘 💡 과정 1️. 맨 앞 데이터와 찾으려는 데이터가 같은지 비교한다. 2️. 다르다면 다음 데이터와 찾으려는 데이터가 같은지 비교한다. 3. 같은 데이터를 찾기 전까지 2의 과정을 반복하고, 같은 데이터를 찾으면 종료한다. 💡 특징 - 정렬되지 않은 리스트에도 적용 가능하다. - 시간복잡도: O(n) 2. 이진 탐색 (Binary Search) 💡 정의 배열을 반으로 쪼개어 찾으려는 값이 왼쪽에 있는지 오른쪽에 있는지를 찾아 탐색 범위를 좁혀가며 탐색을 진행하는 알고리즘 💡 과정 1️. 시작 인덱스와 마지막 인덱스..

파이썬으로 스택 구현하기 (by 리스트) class Stack : def __init__(self) : self.items = [] def push(self, item) : self.items.append(item) def pop(self) : if not self.isEmpty() : return self.items.pop() else : print("Stack underflow") exit() def peek(self) : return self.items[-1] def isEmpty(self) : return not self.items def size(self) : return len(self.items) def clear(self) : self.items = [] 파이썬으로 큐 구현하기 (by 리스..

정렬 (Sorting) 특정한 기준에 따라 데이터를 늘어놓는 알고리즘 (아래에 제시한 정렬들은 모두 오름차순 기준) 1. 선택 정렬 (Selection Sort) 💡 정의 순차적으로 가장 작은 수를 선택하고 교환하는 것을 반복하는 정렬 💡 과정 1. 리스트에서 가장 작은 수를 선택한다. 2. 가장 왼쪽의 원소와 교환한다. 3. 반복한다. 💡 특징 - 시간복잡도: worst, average, best 모두 O(n^2) 2. 삽입 정렬 (Insertion Sort) 💡 정의 자신보다 작은 수가 나올 때 까지 오른쪽로 밀어 삽입하는 정렬 💡 과정 1. 자신의 왼쪽에 자신보다 작은 수가 나올 때까지 오른쪽으로 민다. 2. 왼쪽에 자신보다 작은 수가 나오면 삽입한다. 3. 반복한다. 💡 특징 - 시간복잡도: wo..

스택 (Stack) 💡 정의 자료의 입력과 출력을 한 곳(방향)으로 제한한 자료구조 💡 특징 - 후입선출 구조: 마지막(Last)에 들어온(In) 데이터가 먼저(First) 나간다(Out) → Last-in-first-out(LIFO) - 시간복잡도: 삽입 삭제 연산 O(1) - top을 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠르다. - top 위치 이외의 데이터에 접근할 수 없으므로 탐색할 수 없다. 탐색하려면 모든 데이터를 꺼내면서 진행해야 한다. 💡 관련 용어 - top(peek): 가장 최근에 저장된 데이터이자 먼저 삭제 될 데이터 - push: 데이터 넣기/삽입. (삽입 된 데이터는 삭제시 가장 먼저 삭제 될 데이터가 됨.) - pop: 데이터 꺼내기/삭제. (가장 최근에 저장된 데..

💡 자료구조 데이터를 어떠한 형태로 저장하고 관리할 것인지에 대한 방법. 어떻게 효율적으로 자료를 저장할 것인가? ex) 배열, 스택, 큐, 덱, 그래프, 트리, ··· 💡 알고리즘 저장된 데이터를 찾거나 변형하거나 수정할 때 필요한 방법. 문제를 어떻게 해결할 것인가? ex) 재귀적 알고리즘, 탐욕 알고리즘, 검색 알고리즘, 정렬 알고리즘 ··· [출처 및 참고] https://velog.io/@kmg2933/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%98-%EC%B0%A8%EC%9D%B4