스파르타코딩클럽 내일배움캠프 9일차

오늘 일과 간단 요약

1. 알고리즘 강의 1주차 완강
2. 알고리즘 특강 듣고 다시 복습
3. 코드업 100제 중 10문제
4. 프로그래머스 Level 0 5문제 (풀이 링크)

 

 

 

 

알고리즘 강의 1주차

시간 복잡도

• 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계
• 시간이 적게 걸리는 알고리즘이 더 좋다
• 예제) 최대값 찾기
  • 첫 번째 방법의 시간복잡도: N^2
  • 두 번째 방법의 시간복잡도: 2N+1 ☞ N

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


def find_max_num(array):
   for num in array:              # array 의 길이만큼 아래 연산이 실행
        for compare_num in array:  # array 의 길이만큼 아래 연산이 실행
            if num < compare_num:  # 비교 연산 1번 실행
                break
        else:
            return num


result = find_max_num(input)
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

def find_max_num(array):
    max_num = array[0] # 연산 1번 실행
	for num in array:      # array 의 길이만큼 아래 연산이 실행
		    if num > max_num:  # 비교 연산 1번 실행
		        max_num = num  # 대입 연산 1번 실행
    return max_num

result = find_max_num(input)
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

• N과 N^2는 N이 커질수록 더 큰 차이가 나므로 시간복잡도가 N인 방법이 더 효율적이다.

 

 

공간 복잡도

• 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계
• 대부분의 알고리즘 문제는 알고리즘의 성능이 공간에 의해서 결정되지 않아서 시간 복잡도를 더 신경 써야 한다.
• 예제) 최대값 찾기 의 공간복잡도
  • 첫 번째 방법 : 29
  • 두 번째 방법 : 30
  • 두 가지 방법 모두 상수라 공간 복잡도로 비교하는 대신 시간 복잡도를 더 신경써야 한다.

 

 

점근 표기법

• 알고리즘의 성능을 수학적으로 표기하는 방법
• 알고리즘의 ‘효율성’을 평가하는 방법
• 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다
• 종류
  • 빅오(Big-O)표기법 : O(N)
    • 최악의 성능이 나올 때 어느 정도 연산량이 걸릴 것인지 표기
  • 빅 오메가(Big-Ω) 표기법 : Ω(N)
    • 최선의 성능이 나올 때 어느 정도 연산량이 걸릴 것인지 표기

 

 

결론

1. 입력값에 비례해서 얼마나 늘어날지 파악해보자. 1 ? N ? N^2 ?

2. 공간복잡도 보다는 시간 복잡도를 더 줄이기 위해 고민하자.

3. 최악의 경우에 시간이 얼마나 소요될지(빅오 표기법)에 대해 고민하자

 

 

 

알고리즘 강의 2주차

Array & LinkedList

	Array	LinkedList
특정 원소 조회	O(1)	O(N)
중간에 삽입, 삭제	O(N)	O(1)
데이터 추가	데이터 추가 시 모든 공간이 다 찬 경우 새로운 메모리 공간을 할당받아야 함	모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가
정리	데이터에 접근하는 경우가 많을 경우 사용	삽입과 삭제가 빈번하다면 사용

 

 

 

 

 

짧은 일기

코드업 문제 10문제는 아직까지 입력하고 출력하는 문제들이라 간단하게 10문제를 풀었다.

중간중간 문제를 잘못 해석해서 틀리는 경우가 있었는데 문법 문제가 아닌 경우라서 따로 기록해 놓진 않았다.

 

대신 알고리즘 2주차로 넘어가게 되면서 본격적으로 어려워졌는데, 제공해준 알고리즘 강의를 제외하고

다른 쉬운 강의를 더 추가해서 들어야할 듯 하다. 아니면 책이나.

물론 특강도 듣고 있고 시간이 오래 걸리면 천천히 이해가 가긴 한다.

10시간 내내 집중하는 건 아니지만 알고리즘 강의를 수강하면서 이전보다 더 머리를 쓸 일이(?) 많아졌고,

그만큼 진도가 느려졌다.

그래서 강의를 가볍게 듣고 난 뒤, 여러번 들어서 이해할 것이냐

하나하나 천천히 나가야 하나 하는 고민이 든다.

 

2주차도 다 듣지 않고 저 정도만 듣고 직접 문제를 풀어보고자 프로그래머스 Level 0 문제를

자바스크립트로 풀어보았다.

파이썬으로 듣고 자바스크립트로 풀어보려니 여간 헷갈리는 게 아니라서,

아예 알고리즘 공부는 파이썬으로만 해야 하나 이것도 고민이다.

 

하나부터 열까지 다 고민이지만!

이런 시행착오를 겪어가면서 공부해야 오래 남을 것 같은 기분은 든다.

 

오늘 여기 적지 않은 알고리즘 문제는 따로 카테고리를 파서 글을 따로 적어놓을 예정이다.

알고리즘 강의 내에 있는 문제는 어떻게 기록할까 고민이라서 아직 적지 않았고,

프로그래머스에서 푼 문제들과 코드업 100제 중 헷갈리는 문제들은 계속 포스팅할 것이다.

 

그래야 나중에 알고리즘+자료구조를 조금 이해하게 되었을 때 문제 유형을 구분할 수 있지 않을까?

아직은 Level 0을 풀지만 나중에는 Level 2까지 풀어야 하니까 ㅎㅎ

역시 공부할 게 참 많다.

어느덧 목요일이고 내일은 금요일이니, 10일차가 되어간다.

 

점점 욕심이 생기는 것 같다.

더 잘하고 싶은 욕심. 그래도 의욕이 넘치면 안될 것 같으니까 천천히...다시 마음을 다잡아본다.ㅎ