문돌이 Theo

고지식한 알고리즘 (Brute Force) 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작 시간 복잡도 최악의 경우 모든 위치에서 패턴을 비교해야 하므로 O(MN)이 됨 비교횟수를 줄일 수 있는 방법은 무엇이 있을까? 예시 코드 p = 'is' # 찾을 패턴 t = 'This is a book~!' # 전체 텍스트 M = len(p) N = len(t) def BruteForce(p, t): i = 0 # t의 인덱스 j = 0 # p의 인덱스 while j < M and i < N: if t[i] != p[j]: i = i - j j = -1 i = i + 1 j = j + 1 if j == M: return i - M # 검색 성공 else: ret..

설명 저장되어 있는 자료로부터 k번째로 큰 혹은 작은 원소를 찾는 방법 최소값, 최대값, 중간값 등을 찾는 알고리즘을 의미하기도 함 선택 과정 셀렉션은 아래와 같은 과정으로 구성 정렬 알고리즘을 이용하여 자료 정렬 원하는 순서에 있는 원소 선택 k번째로 작은 원소를 찾을 때, 1번부터 k번째까지 작은 원소들을 찾아 배열의 앞쪽으로 이동, 배열의 k번째를 반환 시간 복잡도: O(kn) - k가 비교적 작을 때 유용 예시 def select(list, k): for i in range(0, k): minIndex = i for j in range(i+1, len(list)): if list[minIndex] > list[j]: minIndex = j list[i], list[minIndex] = list[m..

설명 검색이란 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업 목적하는 탐색 키를 가진 항목을 찾는 것 탐색 키(search key): 자료를 구별하여 인식할 수 있는 키 검색의 종류 순차 검색 (sequentail search) 이진 검색 (binary search) 순차 검색 (Sequential Search) 일렬로 되어 있는 자료를 순서대로 검색하는 방법 가장 간단하고 직관적인 검색 방법 배열이나 연결 리스트 등 순차구조로 구현된 자료구조에서 원하는 항목을 찾을 때 유용함 알고리즘이 단순하여 구현이 쉽지만, 검색 대상의 수가 많은 경우에는 수행시간이 급격히 증가하여 비효율적 2가지 경우 정렬되어 있지 않은 경우 정렬되어 있는 경우 정렬되어 있지 않은 경우 검색 과정 첫 번째 원소부터 순서대로 ..

설명 유한 개의 정수로 이루어진 집합이 있을 때, 이 집합의 부분집합 중에서 그 집합의 원소를 모두 더한 값이 0이 되는 경우가 있는지를 알아보시오. 예: [-7, -3, -2, 5, 8]의 경우 [-3, -2, 5]라는 부분집합이 참이 된다. 위와 같은 문제가 존재할 때, 완전검색 기법으로 접근해야 할 것이다. 우선 집합의 모든 부분집합을 생성하고, 각 부분집합의 합을 계산해야 한다. 부분집합의 수 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개 각 원소를 부분집합에 포함시키거나, 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 동일 {1, 2, 3, 4} 의 경우 2 X 2 X 2 X 2 = 16 총 16개의 부분집합이 존재 각 원소가 부분집합에 포함되었는지를 for..

설명 행과 열을 교환하여 얻는 행렬 즉, 주대각선을 축으로 하는 반사 대칭을 가하여 얻는 행렬 예시 # i : 행의 좌표, len(arr) # j : 열의 좌표, len(arr[0]) arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # 3*3 행렬 for i in range(3): for j in range(3): if i [[1, 4, 7], [2, 5, 8], [3, 6, 9]]

설명 2차 배열의 한 좌표에서 4방향(혹은 8방향 등 필요 요소)의 인접 배열 요소를 탐색하는 방법 예시 arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # 상하좌우 delta_row = [-1, 1, 0, 0] delta_col = [0, 0, -1, 1] # 상하좌우 한번에 할당 delta_row_col = [[-1, 0], [1, 0], [0, -1], [0, 1]] # 추가 - 대각선의 경우는? 좌상, 우상, 우하, 좌하 delta_diagonal = [[-1, -1], [-1, 1], [1, 1], [1, -1]] # 5(1, 1)의 위치를 기준 r = 1 c = 1 for i in range(4): next_row = r + delta_row[i] next_col = c..

설명 배열 순회 : n X m 배열의 n * m개의 모든 원소를 빠짐없이 조사하는 방법 행 우선 순회, 열 우선 순회 등 다양한 방법 존재 예시 N : 행의 길이 M : 열의 길이 행 우선 순회 방식 for i in range(N): for j in range(M): print(arr[i][j]) # 역행 순회 for i in range(N): for j in range(M-1, -1, -1): print(arr[i][j]) 열 우선 순회 방식 for j in range(M): for i in range(N): print(arr[i][j]) # 역행 순회 for j in range(M): for i in range(N-1, -1, -1): print(arr[i][j]) 지그재그 순회 for i in ra..

설명 탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그것이 최종적인 해답으로 적합하다는 보장은 없음 일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy적인 접근 동작 과정 해 선택: 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합(Solution Set)에 추가 실행 가능성 검사: 새로운 부분해 집합이 실행 가능한지 확인 즉, 문제의 제약 조건 등을 위반하지 않는지를 검사 해 검사: 새로운 부분해 집합이 문제의 해가 되는지를 확인 아직 전체 문제의 해가 완성되..

설명 완전 검색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법 Brute-force 혹은 generate-and-text 기법이라고도 불린다. 모든 경우의 수를 테스트한 후, 최종 해법을 도출 일반적으로 경우의 수가 상대적으로 작을 때 유용 알고리즘 학습 초기에는 완전 검색으로 시작! 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률은 적음 평가 등에서 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직한 접근

설명 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘 제한 사항 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능 각 항목의 발생 횟수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 함 시간 복잡도 $O(n+k)$ : n은 리스트의 길이, k는 정수의 최대값 예시 [0, 4, 1, 3, 1, 2, 4, 1]을 카운팅 정렬하는 과정 - 1단계: Data에서 각 항목들의 발생 횟수를 세고, 정수 항목들로 직접 인덱스 되는 카운트 배열 counts에 저장 - 2단계: 정렬된 집합에서 각 항목의 앞에 위치할 항목의 개수를 반영하기 위해..