내일배움캠프 TIL(221122): 알고리즘 문제 시작

오늘 한 일

스파르타에서 제공해준 자바스크립트 공부를 끝내고, 드디어 알고리즘 강의를 시작했다. 자바스크립트는 초초초초 기초 문법을 설명해준 거라서 한번 쭉 들었고...
이제부터가 정말 지옥문.

어제 유데미에서 파이썬 부트캠프 강의를 3일차까지 들어서 약간의 두려움은 사라진 상태였다. (내가 왜 이런 말을 썼지..?)

오늘 목표는 1주차 알고리즘 끝내기!

파이썬 알고리즘 문제 정리

최댓값 찾기

주어진 배열에서 최댓값을 찾는 문제다.

[나의 답안]

input = [3, 5, 6, 1, 2, 4]


def find_max_num(array):
    output = 0
    for num in array:
        if output < num:
            output = num
    return output


result = find_max_num(input)
print(result)

스파르타에서는 모범 답안으로 2가지 코드를 설명해주는데,
1) 하나는 배열 내 숫자를 하나씩 꺼내서 다른 숫자들과 비교해서 가장 큰 것을 출력
2) 다른 하나는 최댓값을 변수로 지정하고 다른 값들보다 비교해서 크면 그 변수에 최댓값을 할당하는 것

나는 2번째 답안과 비슷하게 작성했다.
나는 output = 0 으로 초기화했는데 강의에서는 output = array[0] 으로 지정했다.

[모법 답안 1]

input = [3, 5, 6, 1, 2, 4]

def find_max_num(array):
	for num in array: 				# 배열에서 숫자 하나 꺼내줌 (num)
    	for compare_num in array: 	# 비교하기 위한 다른 숫자를 꺼냄 (compare_num)
        	if num < compare_num:	# 조건문으로 두 숫자 비교
            	break				# compare_num이 num보다 크면 멈춤
        else: 
        	return num				# 위의 조건들을 한번도 만족하지 않으면 num 반환

중첩 if문이 도무지 이해가 안 가서 thonny 프로그램에 코드를 넣고 실행해봤다.
내가 이해한 바로는 다음과 같다.

예를 들어 첫 번재 for문에 array를 넣고 num으로 3을 꺼낸다. 그런 다음 두 번째 for문에 array를 넣고 compare_num으로 3을 꺼낸다. if문으로 비교했을 때 num이 compare_num보다 작지 않으므로 (3=3 이므로) 다시 두 번째 for문으로 돌아간다.

이번에는 compare_num으로 5를 꺼내서 비교한다.
num(3)보다 compare_num(5)이 크기 때문에 if문이 True가 되므로, break가 실행된다.

이런 식으로 반복했을 때 num이 모든 수보다 같거나 클 때까지 반복된다.
그러면 else 조건에 해당하므로 num(=최대값)이 반환된다.

학생 키 평균값 구하기

알고리즘 문제를 이해하고 있자니 반복문에 약하다는 생각이 들어서 유데미 파이썬 강의 문제를 풀어봤다.

학생의 평균 키를 구하는 문제다.
물론 파이썬에는 합계를 구하는 sum 함수가 있기 때문에 배열의 길이를 구하는 len 함수와 함께 쓰면 간단하게 풀 수 있지만... 그러지 말고 (굳이 어렵게) 반복문을 이용해서 풀어보자 ^^!

# 학생들의 키를 띄어쓰기 형태(ex. 156 167 178 ...)로 입력 받아서 저장
student_heights = input("Input a list of student heights ").split()
for n in range(0, len(student_heights)):
	student_heights[n] = int(student_heights[n])

# 반복문으로 학생 키 합계 구하기
total_heights = 0 
for height in student_heights:
	total_heights += height

먼저 구하려는 키 합계를 total_heights 라는 변수에 0으로 초기화한다.
그 다음 반복문을 이용해서 각 학생 키들을 total_heights 에 하나씩 더한다.
처음부터 끝까지 반복하면 전체 학생 키가 더해진다.

그런 다음, 평균값은 당연하게도 여기서 배열의 길이만큼 나눠주면 나온다.
하지만 len 함수를 사용하면 안 되기 때문에 다시 한번 반복문으로 학생의 수(=배열의 길이)를 구해보자.

# 반복문을 학생 수(배열의 요소 개수) 구하기 
number_students = 0
for number in student_heights:
  number_students += 1

앞서 키의 합계를 구했기 때문에 학생 수는 쉽다.
키의 합계는 반복문이 돌 때 각 요소를 차례대로 더해주면 되는 반면,
학생 수는 1씩 더해주면 된다. (number_students += 1)

반복문을 이용해서 복잡하게 구한 학생 키 합계에 학생 수를 나눠주면 평균값 구하기 끝!

최빈값 찾기

alphabet_occurrence_array = [0] * 26

[숫자] * n 을 하면 동일한 숫자 n개 담긴 배열이 생성된다고 한다.

알파벳을 아스키코드로 변환해야 하는 이 문제는 나에게 아직 넘사벽이라 느껴져 다른 쉬운 문제부터 풀어보기로 했다.

배열에서 특정 요소 찾기

반복문을 활용한다면, 배열에서 각 요소를 꺼내서 내가 지정한 수와 같은 지 if문으로 비교해보면 될 것 같았다. 비교해서 같으면 True 반환, 그렇지 않으면 False 반환.

[나의 답안]

array = [3, 5, 6, 1, 2, 4]

def check(num2):
    for num in array:
        if num == num2:
            print(True)
        else:
            print(False)

check(2)

이렇게 하면 결과가 True 하나로만 표시되지 않고 이런 식으로 표시된다.

False
False
False
False
True
False

(끙... 응용이 너무 안 됨.)

[모범 답안]

array = [3, 5, 6, 1, 2, 4]

def check(number, array):
    for element in array:
        if number == element:
            return True

    return False

result = check(3, array)
print(result)

print의 위치가 문제였다.
for문 안에 print를 하면 배열의 요소들이 반복될 때마다 print가 된다.
따라서, True 값만 반환하고 print는 함수 밖에서 써주면 된다.

else도 그냥 return으로 처리해주면 된다.

매개변수에 array 부분도 넣어줘야 한다. 배열이 변경될 수도 있기 때문이다.

배열의 수를 곱하거나 더해서 가장 큰 수 만들기

Q. 다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오.

단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.

문제를 보고 가장 먼저 든 생각은 '0을 곱하면 결과값이 0이 되고, 1을 곱하면 결과값이 똑같으므로 0이나 1이 있으면 더하고, 그 외에 숫자들은 곱하면 되지 않을까'였다.

[나의 답안]

array = [0, 3, 5, 6, 1, 2, 4]

def max_cal(array):
    for num in array:
        if num != 0 or num != 1:
            num += num
        else:
            num *= num

result = max_cal(array)

print(result)

입코딩은 잘 되나 역시나 직접 써보면 한번에 구현되는 일이 잘 없다. ^^

[모범 답안]

def max_cal(array):
    sum = 0			# 합계를 변수로 할당, 0으로 초기화
    for num in array:
        if num <= 1 or sum <= 1:	
        # 합계가 0으로 초기화되어 있으므로, 0 또는 1일 때(sum <= 1)는 더한다는 조건을 추가
            sum += num
        else:
            sum *= num
    return sum
    
result = max_cal(array)

print(result)

우선, 나의 답안이 잘못된 이유를 비교해보면 예상대로 합계를 변수로 지정하지 않은 것이 첫 번째 오류.
'합계를 0으로 초기화하면 곱할 때 0으로 곱해질 텐데 어떡하지?'라는 단순한 생각과 함께 빠뜨림... 아주 단순무식한 생각...

그런 경우를 대비해 '합계가 1보다 작거나 같을 때'도 if문에 같이 포함시켜줘야 한다.
그리고 함수 마지막에는 반드시 합계를 return 해주기!!!!

To-do list

• 스파르타 알고리즘 1주차 강의 복습 (최빈값 문제 포함)
• 유데미 파이썬 부트캠프 5일차 공부
• 내일 오전은 드디어 알고리즘 실시간 수업...ㅎㅎ