알고리즘과 자료구조 02 Brute-force 전략 (1)

 

 

Brute-force 전략

 

 

1. brute-force(억지) 전략

 

1) brute-force(억지) 전략의 개요

- 답을 찾기 위해 모든 가능한 경우를 전부 확인 또는 수행하는 단순한 방법

- 주로 반복 기법 활용

- 컴퓨터의 빠른 성능 활용

 

2) 예시1. 1-100까지 합계 구하기

- sum = 1+2+3+...+100

- 반복문으로 구현

 

3) 예시2. 9ⁿ을 구하기

- result = 9*9*9*...*9

 

 

2. brute-force(억지) 전략 예시

 

1) 오름차순으로 정렬된 숫자들의 리스트에서 최대값을 찾는 방법

- 첫번째 값을 max로 초기화

- 리스트의 두번째부터 마지막 원소를 현재의 max와 비교해 max가 작으면 max를 리스트의 원소값으로 변경

 

2) 서울에서 출발해 대전, 부산, 광주를 모두 방문하고 다시 서울로 돌아오는 최단경로(방문순서는 상관없음)

- 경로 1: 서울-대전-부산-광주-서울

- 경로 2: 서울-대전-광주-부산-서울

...

-> 최소값 경로 선택

 

 

3. brute-force(억지) 전략 특성

 

- easy to design

- 광범위한 문제에 적용 가능

- 입력(데이터)의 크기(개수)가 작은 경우 효과적

- 입력(데이터)의 크기(개수)가 큰 경우 시간 복잡도가 높을 수 있음(낮은 성능)

- 더 효율적인 알고리즘을 통해 성능 개선 가능

 

 

합계 구하기

 

 

<1부터 자연수 N까지의 합계 구하기>

 

1) 알고리즘: 반복, 조건문을 활용해 표현(의사코드)

sum = 0 for num in 1-N: sum = sum+num

- 최악 시간복잡도: O(N)

 

2) 알고리즘1: 파이썬

sum = 0 for num in range(1, N+1):    sum=sum+num print(sum)

 

2) 알고리즘2: 파이썬 함수

def cal_sum(N)    sum=0    for num in range(1, N+1):       sum=sum+num    return sum print(cal_sum(10))

- 함수를 만들어 사용하면 재사용이 쉽다

 

 

최대값 찾기

 

 

<N개의 숫자를 저장한 리스트에서 가장 큰 값을 출력하기>(파이썬)

 

파이썬 리스트

list=[5, 3, 2, 1, 7, 9, 6]

 

1) 의사코드

max=list[0] for num in list[1]~list[N-1]:    if(max<num):       max=num return max

- 최악 시간복잡도: O(N)

 

2) 파이썬 코드

def find_max(list):    max=list[0]    for num in list:       if(max<num):          max=num    return max print(find_max([5, 3, 2, 1, 7, 9, 6]))

 

 

약수의 개수

 

 

<자연수 N의 약수의 개수>

 

1) 의사코드

count=0 for num in 1~N:    if(N%num == 0):       count=count+1 return count

- 최악 시간복잡도: 

 

2) 파이썬 코드

def count_divisors(N):    count=0    for num in range(1, N+1):       if(N%num==0):          count=count+1    return count print(count_divisors(10))