Coursera - Algorithmic Toolbox : week.1

그동안 수많은 알고리즘 강의나 책을 사놓고 그대로 방치해놨는데.... 매주 마감일과 진도가 체크되니까 그래도 좀 하지 않을까 하는 생각에 등록했다.
특화과정의 첫 강의는 Algorithmic Toolbox고 해당 과정에선 탐욕알고리즘, 분할정복, 다이나믹 프로그래밍 등을 다루고 있으며 2주차까진 알고리즘적인 발상을 하는 방법에 대해서 다루고 있다.
첫 주에는 간단한 프로그래밍 문제를 통해 프로그래밍하는 방법에 대해 소개하고 있다.

첫번째 문제는 입력받은 숫자 두 개의 합이다.
이 강의에선 자바, C++, 파이썬 이렇게 세 개의 언어를 지원하고 있으며, 각 언어로 해당 문제에 대한 해답도 제공되어있다. 쉬운 문제이므로 직접 풀어도 되고, 제공된 파일을 그대로 제출해도 첫번째 과제는 통과된다.

def sum_of_digits(first_digit, second_digit):
	return first_digit + second_digit
if __name__ == ’__main__’:
	a, b = map(int, input().split())
	print(sum_of_digits(a, b))

두번째 문제는 주어진 배열 상에서 두개의 수를 곱했을 때, 가장 큰 값을 구하는 문제다. 
이번 문제는 좀 더 생각할 여지를 주는데, 솔루션이 정확할 뿐 아니라 시간적으로도 효율적이어야 하기 때문이다.
그래서 처음엔 단순하게 접근하는 방법을 알려주고, 두번째로는 그보다 효율적인 방법을 소개해준다. 단순하게 접근하는 방법은 다음과 같다.

 

solution 1. 단순 접근

MaxPairwiseProductNaive(A[1...n]):
	product ← 0
	for i from 1 to n:
		for j from 1 to n:
		if i , j:
			if product < A[i] · A[j]:
				product ← A[i] · A[j]
	return product

 

1. 리스트의 0번째 요소부터 끝에서 두번째까지 도는 루프를 만든다
2. 해당 루프 안에서 리스트의 1번째 요소부터 끝까지 도는 루프를 만든다.
3. 이 안에서 elem[i] * elem[j] 의 값을 계산해서, 이전의 값보다 크면 해당 값을 result에 할당한다.

중첩된 루프가 있으므로 시간복잡도를 분석하자면 O(n^2)이 된다.
이 방법대로 하면 답을 얻을수는 있지만 매우 비효율적이다.

 

solution 2. 좀 더 효율적
사실 생각해보면 제일 큰 값 * 두번째로 큰 값을 곱하는 것이 가장 큰 값이 되는 것이 당연하다.
때문에 두번째 해법에서는 먼저 리스트를 정렬한 다음에, 맨 뒤의 요소와 뒤에서 두번째 요소를 곱한 값을 리턴한다.
시간복잡도를 분석하자면 O(nlogn)이 된다.

강의상에선 이 또한 완벽한 정답은 아니고, 다른 답도 생각해보라고 했지만 강의가 밀려서...일단 패스 (...)

 

이 다음에는 테스트 방식에 대해서 다루고 있다.

아무래도 이 과정에서 첫번째 강의라 그런가 최대한 다양한 케이스로 테스트를 실행해보라는 얘기와 여러 예를 만들어서 실행하는 것 정도까지만 알려주고 있다.

결론은 테스트는 최대한 꼼꼼하게 하자 정도..?