1. 일치하는 글자 찾기

1.1 문제

• 한글로 구성된 list 2개(list_1, list_2)를 비교해서 list_2가 list_1에 포함되는지 확인하기

1.2 브레인 스토밍

① list_1과 list_2 를 동시에 접근하여 구성 내용이 일치하는지 확인하는 방법
② 이분 탐색을 이용하는 방법(막연하게 가능할 것 같다는 생각이 든다)

1.3 전략

• 첫 번째 방법을 이용해서 코드를 구현하도록 한다.
• 확실한 방법을 먼저 사용하고, 이분법으로 시도해보자.

1.4 슈도 코드

1) list_1에서 첫 번째를 선택한다. (for)
	2) (for) list_2에서 첫 번째를 선택한다. (for)
		3) (for, for) list_1 선택된 것과 list_2 선택된 것이 같으면 (if)
			4) (for, for, if) 따로 담아두기
    
5) 따로 담아둔 list와 list_2가 동일하면(if)
6) (if) true 반환하기
7) 그렇지 않으면(else:)
8) false 반환하기

1.5 코드 및 설명

list_1 = ["만", "떡", "오", "사", "콜"]
list_2 = ["오", "콜", "떡"]


def is_available_to_order(menus, orders):
    same_compo = []
    for a_menus in menus: 			# 1) list_1에서 첫 번째를 선택한다. (for)
        for a_orders in orders: 		# 2) (for) list_2에서 첫 번째를 선택한다. (for)
            if a_menus == a_orders: 		# 3) (for, for) list_1 선택된 것과 list_2 선택된 것이 같으면 (if)
                same_compo.append(a_orders)     # 4) (for, for, if) 따로 담아두기
    if len(orders) == len(possible_menu):       # 5) 따로 담아둔 list와 list_2가 동일하면(if)
        return True 				# 6) (if) true 반환하기
    else: 					# 7) 그렇지 않으면(else:)
        return False 				# 8) false 반환하기

result = is_available_to_order(list_1, list_2)
print(result)

1.6 시간 복잡도

① 결과: O(N^2) (= O(log2))
② 이유: for 문이 겹쳐서 2번 사용됨
③ 문제: 어느 list의 배열이 커지더라도 비교 횟수가 기하급수로 증가함
④ 해결: 이분 탐색을 사용하면 가능할 것 같다. 감은 있지만 코드로 구현하기 위해서는 조금 더 연구가 필요하다.

2. 원하는 숫자 만들기

2.1 문제

• 1이 5개가 존재하는 list([1,1,1,1,1])와 +,-를 활용하여 1,2,3,4,5를 모두 만들 수 있다. 이 때, 2를 만드는 방법은 총 몇 가지 인가?
  예) 4를 만드는 조합/ 가지 수: (+1 +1 +1 +1 -1), ..., (-1 +1 +1 +1 +1)/ 5 가지

2.2 브레인 스토밍

① + = 1로, - = -1로 변환해 풀 수 있는 방법은 없을까? (구체적인 방법이 떠오르지 않는다.)
② 나타나는 숫자 사이 어떤 관계가 있지 않을까? 있다. 찾았다.

• list 안에 있는 수를 모두 더하면 5다.
• 5 = 5 - 0이고, 5C0 = 1, 5!/(5!*0!), 조합 = (+,+,+,+,+) = 1가지
• 4 = 5 - 1이고, 5C1 = 5, 5!/(4!*1!), 조합 = (-,+,+,+,+), ... = 5가지
• 3 = 5 - 2이고, 5C2 = 10, 5!/(3!*2!), 조합 = (-,-,+,+,+), ... = 10가지
• 2 = 5 - 3이고, 5C3 = 10, 5!/(2!*3!), 조합 = (-,-,+,+,+), ... = 10가지
• 1 = 5 - 4이고, 5C4 = 5, 5!/(1!*4!), 조합 = (-,-,+,+,+), ... = 5가지

2.3 전략

• 두 번째 방법을 이용해서 코드를 구현하도록 한다.
• 결국 조합 문제로 변한다.
• 1들의 총합에서 목표하는 수를 뺀다. 그러면 나머지가 발생하는데, 5!을 나머지로 나눈다.
• 관계를 일반화하면 5!/(목표로 하는 수!*(5-나머지)!)로 표현할 수 있다.
• 코드를 간편하게 만들기 위해서는 팩토리얼이 필요하다.
• 팩토리얼은 재귀함수로 구현 가능하다.

2.4 슈도 코드

1) 팩토리얼을 사용하는 함수를 만든다.
2) 1을 모두 합한다.
3) 나머지를 구한다.
4) 분자에 factorial(총합)의 결과를 할당한다.  
5) 분모에 factorial(나머지) * factorial(목표하는 수) 결과를 할당한다.
6) 계산한다.
7) 결과를 반환한다.

2.5 코드 및 설명

numbers = [1, 1, 1, 1, 1]
target_number = 3


def factorial(number): 				# 1) 팩토리얼 생성하는 함수를 만든다.
    if number == 1: 				# 1-1) 인자가 1이면 1을 반환하고 함수를 빠져나온다.
        return 1
    return number * factorial(number - 1) 	# 1-2) 그렇지 않으면 인자와 (인자-1)을 인자로 하는 함수의 결과를 도출한다.


def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target):
    sum_array = sum(array) 			# 2) 1을 모두 합한다.
    rest_number = sum_array - target 		# 3) 나머지를 구한다.

    numerator = factorial(sum_array) 		# 4) 분자에 factorial(총합)의 결과를 할당한다.  
    denominator = factorial(rest_number) 	# 5) factorial(target) # 분모에 factorial(나머지) * factorial(목표하는 수) 결과를 할당한다.

    result = int(numerator / denominator) 	# 6) 계산하고 정수로 변환한다.

    return result 				# 7) 결과를 도출한다.


print(get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number))

2.6 시간 복잡도

① 결과: O(N)
② 이유: 1이 N개 있다면 최대 N번 각 자리를 접근할 것이다.

3. 느낀점

• 막연하게 가능할 것 같은 코드를 구현하지 않는 것은 현명한 행동 같다. 이러한 감을 믿고 따라가다 보면 막힐 가능성이 아주 높기 때문이다. 그래도, 시간이 나면 구현해보는 시도를 해보자.
• 코드를 작성하기 전 브레인스토밍을 하는 습관을 들이기로 했다. 문제를 처음 보는 순간 떠오르는 방법을 기억하고, 그것을 어떻게 적용하고, 어떤 방법이 필요한지 대략적으로 알아보기 위해서이다. 이 방법을 사용하니, 코드를 바로 작성하는 것에 비해 시간을 확연히 줄일 수 있었다. 브레인 스토밍을 하면서 내가 코드로 구현이 가능한지 알 수 있기 때문이다. 이러한 경험이 쌓이면 직관이 생기고, 문제를 해결하는 속도가 빨라지지 않을까?