📜 알고리즘 실시간 강의

:: ✍ 강창민 튜터님 실시간 강의

REPL (Read Eval Print Loop) 이란?
입력(read)
평가(eval)
출력(print) 
반복(loop)

컴파일 과정 없이 즉석에서 코드를 입력해 결과를 바로 알 수 있는 방식

:: LinkedList

• cur = 현재의 노드
• 링크드 리스트는 head부터 탐색
• cur - 순회
• 링크드리스트를 쓰면 삽입, 삭제가 아주 편함
• Linked 찾아가기 오래걸리지만 추가 수정이 쉬움
• 용도에 따라서 검색이 중요한지 수정과 추가가 중요한지를 결정 후 Array와 LinkedList 선택해서 사용
• index를 1로 추가했기 때문에 1이라고 칭함
• 예외처리를 가장 위에 두는 것
  • 예외가 들어왔을 경우 바로 먼저 실행
  • 불필요한 과정을 거치지 않음

:: 재귀함수

• 자기 자신을 호출하면서 코드 간결, 명확하게 할 수 있는 장점
• 터미널 컨디션
  • 항상 탈출 조건이 어떻게 되는지 고민
  • 코테에선 이걸 여러개 설정해야할 수도 있음
  • 안하면 무한루프 및 error

1. 팩토리얼

• 1부터 n까지 모두 곱한 것
• Tail recursion
  • stack memory를 과다사용하는 재귀호출의 문제점을 피하기 위한 방법
    • 스택에는 함수호출, Function Call에서 메모리 할당

2. 회문검사

회문 : 앞으로 읽어도 똑바로 읽어도 똑같은 단어와 문장

• 경우의 수
  연산자의 개수(5) ^ 숫자의 개수(2) = 2 5 = 32

:: ✍ 튜터님 문풀

• 경우의 수
  연산자의 개수 ^ 숫자의 개수 = 연산자 개수 숫자개수

더하거나 빼거나

Q. 주어진 배열(numbers)에 대해 더하거나 빼서 target_number가 나올 수 있는 경우의 수를 구하시오.

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

def get_all_combinations(numbers, curr_idx, curr_sum):
	# 1 (+-) 1 (+-) 1 (+-) 1 (+-) 1
    # 경우의 수 = 연산자의 개수(5) ^ 숫자의 개수(2) = 2^5 = 32
    
    if (curr_idx == len(numbers)):
    	return sums.append(curr_sum)
        
    get_all_combinations(numbers, curr_idx + 1, curr_sum + numbers[curr_idx])
    get_all_combinations(numbers, curr_idx + 1, curr_sum - numbers[curr_idx])
    
get_all_combinations(numbers, 0, 0) # 둘다 0부터 시작이니 0 두개 넣음
print(sums)

• 반복문으로도 할 수 있음
  • +와 -라는건 1과 0으로 표현 = binary
  • 연산자 개수가 두개라서 바이너리로 표현

1. 0~31 출력

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

def get_all_combinations(numbers):
	# +, - 는 각 1과 0으로 표현 -> binary
    # ----- ~ +++++
    
    for i in range(2 ** len(numbers)):
    	print(i)
    
    
get_all_combinations(numbers, 0, 0) # 둘다 0부터 시작이니 0 두개 넣음
print(sums)

2. 00000~11111 출력

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

def get_all_combinations(numbers):
	# +, - 는 각 1과 0으로 표현 -> binary
    # ----- ~ +++++
    
    for i in range(2 ** len(numbers)):
    	binary_val = '{:05b}'.format(i)
    	print('binary_val : + str(binary_val))
    
    
get_all_combinations(numbers, 0, 0) # 둘다 0부터 시작이니 0 두개 넣음
print(sums)

3. ['0', '0', '0', '0', '0'] ~ ['1', '1', '1', '1', '1']

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

def get_all_combinations(numbers):
	# +, - 는 각 1과 0으로 표현 -> binary
    # ----- ~ +++++
    
    for i in range(2 ** len(numbers)):
    	binary_val = '{:05b}'.format(i)
    	print('binary_val : + str(binary_val))
        operators = [el for el in list(binary_val)]
        print('operators', operators)
    
    
get_all_combinations(numbers, 0, 0) # 둘다 0부터 시작이니 0 두개 넣음
print(sums)

4. [0,0,0,0,0] ~ [1,1,1,1,1]

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

def get_all_combinations(numbers):
	# +, - 는 각 1과 0으로 표현 -> binary
    # ----- ~ +++++
    
    for i in range(2 ** len(numbers)):
    	binary_val = '{:05b}'.format(i)
    	print('binary_val : + str(binary_val))
        operators = [int(el) for el in list(binary_val)]
        print('operators', operators)
    
    
get_all_combinations(numbers, 0, 0) # 둘다 0부터 시작이니 0 두개 넣음
print(sums)

5. [-5, -3, -3, -1, -3, -1, -1, 1, -3, -1, -1, 1, -1, 1, 1, 3, -3, -1, -1, 1, -1, 1, 1, 3, -1, 1, 1, 3, 1, 3, 3, 5]

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


def get_all_combinations(numbers):
    # +, - 는 각 1과 0으로 표현 -> binary
    # ----- ~ +++++

    for i in range(2 ** len(numbers)):
        binary_val = '{:05b}'.format(i)
        operators = [int(el) for el in list(binary_val)]
        print('operators', operators)
        # 루프 돌아보자. numbers의 len
        # operator에 따라 1 또는 -1
        curr_sum = numbers[0] if operators[0] == 1 else -numbers[0]
        # 1~ len-1
        for j in range(1, len(numbers)):
            if operators[j] == 1:
                curr_sum += numbers[j]
            else:
                curr_sum -= numbers[j]
        sums.append(curr_sum)

get_all_combinations(numbers)
print(sums)

:: ⭐ Tip

어려울 때

• 손으로 펜으로 그림을 써보고 그려보면서 해보자
• 화물열차그림으로 해보자
• 노트나 필기구 사용하기

알고리즘은 뭘 해야할지 딱딱 빠르게 파악해야함

Meomo
return 은 조건에 맞는 결과가 있는거고 : 여기로 나오세여~ 
break 는 결과 없이 조건이 충족되면 함수를 중단 : 절벽 길없음