Algorithm/이론 정리 (6) 썸네일형 리스트형 [Algorithm] 가장 간단한 알고리즘 - 브루트 포스법 브루트 포스법 : brutu는 무식한, force는 힘이라는 뜻이다. 무식하게 힘으로 해결하는 방법. 즉, 가장 간단한 알고리즘으로 가능한 모든 경우의 수를 검사하는 알고리즘이다. 브루트 포스법은 문자열 검색 중 가장 가장 기초적이고 단순한 알고리즘이다. 문자열 검색 string searching 이란 ? : 어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사하고, 만약 포함되어 있다면 어디에 위치하는지 찾아내는 것. 텍스트 text : 검색되는 쪽의 문자열 패턴 pattern : 찾아내는 문자열 ex. 문자열 'yena'에서 'na'를 검색하면 성공, 'bibi'에서 'na'를 검색하면 실패. 여기서 텍스트는 'yena', 'jiyun'이 되고, 패턴은 'na'가 된다. 브루트 포스법 brute fo.. [Algorithm] 재귀 Recursion 재귀 recursion 재귀 알고리즘의 기본 재귀란 ? 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우 재귀를 사용하면 프로그램을 간결하고 효율성 좋게 작성할 수 있음 재귀 호출 recursive call '자기 자신과 똑같은 함수'를 호출한다. ex - 팩토리얼 구하기 factorial() 함수는 n - 1의 팩토리얼 값을 구하기 위해 다시 자기 자신과 똑같은 factorial() 함수를 호출한다. def factorial(n: int) -> int: """양의 정수 n의 팩토리얼을 구하는 과정""" if n > 0: return n * factorial(n - 1) else: return 1 if __name__ == '__main__': n = int(input('출.. [Algorithm] 탐색 Searching 탐색 범위를 반씩 좁혀가는 탐색 순차 탐색 Sequential Search : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있음. 순차 탐색 소스코드 # 순차 탐색 소스코드 구현 def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in range(n): # 현재의 원소가 찾고자 하는 원소와 동일한 경우 if array[i] == target: return i + 1 # 현재의 위치 반환(인덱스는 0부터 시작하므로 1 더하기) print("생성할 원소 개.. [Algorithm] 정렬 Sorting 정렬 sorting : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색 Binary Search가 가능해진다. 정렬은 이진탐색의 전처리 과정이기도 하다. '알고리즘의 효율성' 측면에서 정렬은 중요하다. 선택 정렬 selection sort : 매번 '가장 작은 것을 선택'한다. 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하여 정렬이 완료되는 것을 알 수 있다. 스와프(Swap): 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업. 파이.. [Algorithm] 복잡도 Complexity 복잡도 복잡도는 알고리즘의 성능을 나타내는 척도이다. 동일한 기능을 수행하는 알고리즘이 있다면 복잡도가 낮을수록 좋은 알고리즘이다. 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양 일반적으로 코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 중요하다. 따라서 최악의 경우의 시간 복잡도를 우선적으로 고려해야한다. Cf) Memorization 메모이제이션 : 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법 시간 복잡도와 공간 복잡도의 Trade-off 메모리를 많이 사용하는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다. 이때 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가.. [Algorithm] 알고리즘 설계와 분석의 기초 알고리즘 설계와 분석의 기초 알고리즘이란 문제를 해결하기 위한 단계적 절차를 말한다. 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것이다. 점근적 분석 점근적 분석이란 입력이 충분히 큰 경우에 대한 분석을 말한다. 컴퓨터는 빠른 처리 능력을 가지므로 입력의 크기가 작을땐 속도의 차이가 뚜렷하지 않다. 하지만, 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있다. 좋은 알고리즘 = 성능이 좋은 = 효율적인 = 같은 시간에서 더 빠른 알고리즘이다. 알고리즘 표현법 순서도를 이용한 표현 여러 종류의 상자와 상자를 이어 주는 화살표를 이용해서 명령 순서를 표현 간단한 알고리즘은 쉽게 표현할 수 있지만, 복잡한 알고리즘은 표현하기 어려운 경우가 많.. 이전 1 다음
