[알고리즘] 완전 탐색 & 재귀함수

알고리즘 스터디 2회차

[일곱 난장이]

* 스페셜 저지 : 답이 여러가지가 있을 수 있다.

문제해결법1

1. 7개를 선택하는 완전 탐색 알고리즘 설계

2. 모든 경우의 수를 진행

3. 만족하는 답이 한 개라도 발견되면 문제 해결

문제해결법2

1. 9개 중에서 7개를 선택해야 한다는 것은 2개를 선택하지 않는 것

2. 선택하지 않는 것을 선택해보자

3. 전체의 합에서 2개를 선택해 빼서 100이 되게 만들자.

[홀수 문제]

1. 주어지는 수들의 합을 구하자

2. 주어지는 수들

[악수구하기]

문제해결법

1. N의 약수를 어떻게 구할 것인가?

2. 가장 쉬운 방법은 1-N까지 전부 확인

3. 조금 더 빠른 방법은?

 --> N이 십억, 20억일 때 좀 더빠른 밥버이 있을까?? 

문제해결법2

1. 각각의 약수는 서로 매칭되는 약수가 있음

2. N의 약수가 X라면 

[수이어가기]

1. 수열이 어떻게 만들어지는지 이해

2. F(N) = F(N-2) - F(N-1)

3. F(N)이음수가 되는 순간 수열의 끝

문제 해결1

1. 수열의 길이를 구하는건 시키는 것 그대로 작성하면 된다.

2. 하지만 수열의 길이를 최대로 만드는 F(2)를 구하는 방법은?

3. N의 크기가 30000으로 작기 때문에 0부터 30000까지 전부 해본다

4. F(2)는 N을 초과할 이유가 없다. 왜 일까?

[숫자게임]

문제해결

1. 5개의 수 중 3개를 선택하는 것은 완전탐색으로 해결

2. 그렇다면 최대값의 인덱스를 구하는 과정은?

3. 최대값이 두 개 이상이라면 큰 인덱스를 구하는 과정은?

4. maxValue, idxOfMaxValue와 같이 두 개의 변수를 이용해서 해결

지은님 코드 피드백

- number = sum(numbers) 5개중 3개를 선택해야 하는 데 5개 모두를 더했다

- number = int(str(number)[1]) 1이 5개일 때 모두 합하게 되면 1의자리수인데 index 1에 숫자가 없는경우가 있어서 런타임 에러 발생

[임시반장]

문제해결

1. 같은 반이었던 친구 수  구하는 것은 단순구현

2. 후보들 중 가장 작은 인덱스 출력은?

3. maxValue, idxOfMaxValue 두 개의 변수로 해결

[후보추천하기]

1. 

[대표 자연수]

문제해결법1

1. 사실은 중앙값을 구하는 문제

2. median이 왜 차이를 최소로 만들까?

* 중앙값 : 수열에서 가장 중앙에 있는 값.

[수열]

문제 해결1

1. 가능한 모든 시작지점에 대해서 해보자

2. N은 10만, 제 시간내에 들어오지 않는다.

3. 5개 중 4개는 겹친다.

문제 해결2

1. 바로 전 단계에서 계산된 값을 활용

2. 슬라이딩 윈도우 기법

3. 계산된 값 - 빠진 원소 + 추가된 원소

4. 

** 후보추천하기 수열 문제 2개는 꼭 풀어보기

[스타트와 링크]

1. 재귀를 짤 때는 항상 기저사례를 작성하라

2. 

[클락싱크]

1. 

다이나믹 프로그래밍

- 내가 이미 계산한 것에 대해서 다시 계산할 필요가 없다.

1) 반복문을 이용한 것

2) 재귀를 이용한 것

* 파도반 수열

- 규칙이 없는 것들이 기저사례가 된다

f(n) = f(n-1) + f(n-5)  점화식 세우는 것이 가장 중요하다.

- 

동전2 : https://www.acmicpc.net/problem/2294

그리디를 사용하는 문제가 아니다.

예제 입력을 보면 딱 봐도 아니다.

그렇다면 이 문제를 어떻게 접근할 것인가??