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

오늘의 일과 간단 요약

1. 웹 퍼블리싱 강의 1주차 완강
2. 알고리즘 강의 3주차 완강
3. 프로그래머스 Level 0 5문제 (풀이 링크)

 

 

 

 

 

 

웹 퍼블리싱 강의 1주차

지난 주말을 보내고 나니 강의실에 Git 강의와 웹 퍼블리싱 강의가 추가되었다.

뭔가 지난 주에 알고리즘에 너무 빠져서 월요일 아침부터 하고 싶지는 않아서 기분전환도 할 겸,

웹 퍼블리싱 강의를 새로 시작했다.

이번주 금요일부터 새로운 팀원들과 함께 프로젝트를 시작할 텐데, 뭔가 웹 퍼블리싱 강의가 도움 될것 같기도 하고

또 알고리즘 보다야 재밌으니까 ㅋㅋㅋ

 

그래서 1주차를 빠르게 완강했는데,

간만에(?) 웹 페이지를 디자인하는 걸 배우니까 너무 좋았다.

 

하다가 또 안했다고 CSS를 까먹었는데, 다시 상기되기도 하고.

나는 웹페이지를 내 맘대로 만들 수 있다는 그 자체에 흥미가 생겨서 웹 개발 공부를 다짐했었는데,

그 다짐을 했던 때로 돌아간 것 같았다.

그래서 아침 시간에는 웹 퍼블리싱 강의를 듣고, 중간에 매니저님과 면담도 했다.

 

이건 지금은 넘어가고,

여하튼 1주차라서 특별히 더 배운 건 없었고 예전 웹 개발 종합반 들었던 기초와 더불어 CSS 추가 과정 정도였다.

더 배운 건 없어서 간단하게 느낌만 기록.

 

 

 

알고리즘 강의 3주차

매니저님과 면담을 하면서 알고리즘에 대한 고민을 이야기했었는데,

너무 이해하고 넘어가려고 하지 말고 한번 큰 틀을 쭉 훑어본다는 느낌으로 공부하기로 했다.

 

지난 2주차 회고에서도 너무 허둥대며 이것저것 했던 게 아쉬웠는데, 그거에 대한 답을 좀 찾은 기분.

알고리즘 강의가 너무 어렵다고 아예 다른 걸 할까 고민했었는데, 그러지 말고 그냥 가볍게 알아간다는 기분으로 강의를 듣기로 마음 먹었다. 큰 욕심 내지 않고, 그냥 알고리즘 종류는 뭐가 있는지 자료 구조가 뭔지 이런 걸 공부하는 걸로.

 

대학 갈 때 공부했던 것처럼, 아니 평소에 공부했던 방법을 계속 고수하려고 했던 것 같다.

이해하고 넘어가고, 다시 이해하고 넘어가고...코딩은 이렇게 공부하면 안되는데.

지난 튜터님과의 면담에서도 이야기나눴던 건데,

top-down 형식으로 공부하고 다시 down-top 형식으로 공부하는 것.

이렇게 공부해야 더 잘된다고 했었는데 그새 까먹었었나 보다.

 

전부 다 이해하고 넘어가고 싶어서 욕심을 부렸는데, 이제는 그러지 않기로.

 

그렇게 생각하고 나니 3주차를 공부하는 게 한결 더 쉬워졌다.

예제로 주어지는 걸 전부 풀고 넘어가려고 했었는데 이제는 강의에서처럼 2분 생각하고 안되면 정답 코드를 보고

코드를 이해하고 넘어가기 시작했다.

물론, 아직 어렵고 복잡하긴 마찬가지인데 임하는 내 마음가짐이 좀 달라졌으니까.

이 밑에는 3주차를 정리한 내용이다.

 

 

 

정렬의 의미

• 정렬 : 데이터를 순서대로 나열하는 방법
  • 이진 탐색을 가능하게도 하고, 데이터를 조금 더 효율적으로 탐색할 수 있게 만든다
  • 컴퓨터에게 정렬을 시키기 위해서는 명확한 과정을 설명해줘야 한다

 

버블 정렬

• 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식
• 맨 오른쪽을 옆과 비교하면서 최댓값이 찾아지면서 쌓아지는구나, 라고 생각하면 된다.
• 함수 구문 하나하나를 보지 않더라도, 2차 반복문이 나왔고, array 의 길이 만큼 반복 ⇒ 그러면 시간복잡도가 O(N^2)
• 예제

input = [4, 6, 2, 9, 1]


def bubble_sort(array):
		n = len(array)
    for i in range(n):
    	for j in range(n - i - 1):
        	if array[j] > array[j + 1]:
            	array[j], array[j + 1] = array[j + 1], array[j]
    return array


bubble_sort(input)
print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!

 

 

선택 정렬

• 선택해서 정렬한다
• 전체에서 최솟값을 선택하는 방법
• 함수 구문 하나하나를 보지 않더라도, 2차 반복문이 나왔고, array 의 길이 만큼 반복 ⇒ 그러면 시간복잡도가 O(N^2)
• 예제

input = [4, 6, 2, 9, 1]


def selection_sort(array):
    n = len(array)
    for i in range(n - 1):
    	min_index = 1
        for j in range(n - i):
        	if array[i + j] < array[min_index]:
            	min_index = i + j

		array[i], array[min_index] = array[min_index], array[i]

    return array


selection_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

 

 

삽입 정렬

• 전체에서 하나씩 올바른 위치에 삽입하는 방식
• 필요할 때만 위치를 변경하므로 선택 정렬보다 더 효율적인 방식이다
• 시간 복잡도가 O(N^2) 만큼 걸리지만, 최선의 경우에는 Ω(N) 만큼의 시간 복잡도가 걸린다
• 예제

input = [4, 6, 2, 9, 1]


def selection_sort(array):
    n = len(array)
    for i in range(1, n):
    	for j in range(i):
        	if array[i - j - 1] > array[i - j]:
            	   array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
		else:
            	  break
    return array


selection_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

print("정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ",insertion_sort([5,8,4,7,7]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",insertion_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",insertion_sort([100,56,-3,32,44]))

 

 

병합 정렬

• 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 작업을 반복하는 알고리즘
• 병합 정렬 - merge
  • 예제

    array_a = [1, 2, 3, 5]
    array_b = [4, 6, 7, 8]
    
    def merge(array1, array2):
        result = []
    		array1_index = 0
    		array2_index = 0
    
    		while array1_index < len(array) and array2_index < len(array2):
    				if array1[array1_index] < array2[array2_index]:
    						result.append(array1[array1_index])
    						array1_index += 1
    				else:
    						result.append(array2[array2_index])
    						array2_index += 1
    
    		if array1_index == len(array1):
    				while array2_index < len(array2):
    						result.append(array2[array2_index])
    						array2_index += 1
    
    		if array2_index == len(array2):
    				while array1_index < len(array1):
    						result.append(array1[array1_index])
    						array1_index += 1
    
        return result
    
    print(merge(array_a, array_b))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!
    
    print("정답 = [-7, -1, 5, 6, 9, 10, 11, 40] / 현재 풀이 값 = ", merge([-7, -1, 9, 40], [5, 6, 10, 11]))
    print("정답 = [-1, 2, 3, 5, 10, 40, 78, 100] / 현재 풀이 값 = ", merge([-1,2,3,5,40], [10,78,100]))
    print("정답 = [-1, -1, 0, 1, 6, 9, 10] / 현재 풀이 값 = ", merge([-1,-1,0], [1, 6, 9, 10]))
    

• 병합 정렬 - mergeSort
  • 분할 정복(Divide and Conquer)의 개념을 적용
    • 분할 정복 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
    • (예) [5, 4] 라는 배열이 있다면 이 배열을 [5] 와 [4] 를 가진 각각의 배열로 작은 2개의 문제로 분리해서 생각하는 것 ⇒ 둘을 합쳐서 정렬하면 전체의 정렬된 리스트가 된다
  • “0부터 N까지 정렬한 걸 보기 위해서는 0부터 N/2 까지 정렬한 것과 N/2부터 N까지 정렬한 걸 합치면 된다”라는 개념
  • MergeSort(0, N) = Merge(MergeSort(0, N/2) + MergeSort(N/2, N)) ⇒ 재귀적인 코드
  • 시간 복잡도 : O(Nlog_2N) = O(NlogN) 이 된다

 

 

스택 (stack)

• 한쪽 끝으로만 자료를 넣고 뺄 수 있는 구조
• Last In First Out (LIFO)
• 컴퓨터의 되돌리기 기능 ⇒ 내가 했던 행동들을 순서대로 기억해야 하므로 스택을 사용한다
• 데이터 넣고 뽑는 걸 자주하는 자료 구조 (링크드 리스트와 유사하게 구현가능)
• 스택의 구현
  • push(data) : 맨 앞에 데이터 넣기
  • pop() : 맨 앞의 데이터 뽑기
  • peek() : 맨 앞의 데이터 보기
  • isEmpty() : 스택이 비었는지 안 비었는지 여부 반환해주기
  • 예제

    def pop(self):
            if self.is_empty():                  # 만약 비어있다면 에러!
                return "Stack is empty!"
            delete_head = self.head              # 제거할 node 를 변수에 잡습니다.
            self.head = self.head.next           # 그리고 head 를 현재 head 의 다음 걸로 잡으면 됩니다.
            return delete_head                   # 그리고 제거할 node 반환
    

    def peek(self):
            if self.is_empty():
                return "Stack is empty!"
    
            return self.head.data
    

    def is_empty(self):
            return self.head is None
    

  • def push(self, value): # 현재 [4] 밖에 없다면 new_head = Node(value) # [3] 을 만들고! new_head.next = self.head # [3] -> [4] 로 만든다음에 self.head = new_head # 현재 head의 값을 [3] 으로 바꿔준다.
• 실제 파이썬코드에서는 파이썬의 list를 이용해서 스택으로 사용

 

 

큐 (queque)

• 한쪽 끝으로 자료를 넣고 반대쪽에서는 자료를 뺄 수 있는 자료 구조
• First In First Out (FIFO)
• 순서대로 처리되어야 하는 일에 필요 (예) 주문이 들어왔을 때 먼저 들어온 순서대로 처리해야 할 때 등
• 큐의 구현
  • enqueue(data) : 맨 뒤에 데이터 추가
  • dequeue() : 맨 앞의 데이터 뽑기
  • peek() : 맨 앞의 데이터 보기
  • isEmpty() :큐가 비었는지안 비었는지 여부 반환
  • 시작과 끝의 노드를 전부 가지고 있어야 하므로 self,head와 self.tail을 가지고 시작한다

 

 

해쉬

• 해쉬 테이블
  • 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인 연관 배열 추가에 사용되는 자료구조
  • 해시 함수를 사용하여 색인(index)를 버킷(bucket)이나 슬롯(slot)의 배열로 계산
  • 시간은 빠르되 공간을 대신 사용하는 자료구조
  • 파이썬의 딕셔너리와 같다
  • 키를 통해 데이터를 바로 받아올 수 있으므로 속도가 획기적으로 빨라진다
  • 딕셔너리 내부적으로는 배열을 사용한다
• 해쉬 함수
  • 임의의 길이를 갖는 메세지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수
  • 파이썬에서 hash(object)로 제공하고 있다
  • 배열에 넣는 방법 ⇒ 배열의 길이로 나눈 나머지 값을 쓰면 된다
  • put(key, value) : key에 value 저장하기
  • get(key) : key에 해당되는 value 가져오기

 

 

 

 

 

 

 

 

짧은 일기

분명 저번주까지만 해도 알고리즘 자체가 너무 힘들었는데, 다행히(?) 오늘은 그나마 나았다.

오전에 환기할 겸 웹 퍼블리싱 들으니까 다시 의욕이 생겨서ㅎ

사실 그 웹 퍼블리싱 덕분에 내일배움캠프도 하고 있는 거니까...내 입장에서는 그렇다.

우연히 HTML, CSS로 웹페이지 만드는 걸 배우고 나니까 더 깊은 걸 배우고 싶어졌었는데,

그 때의 그 기분을 다시 느낄 수 있었다.

물론! 그것도 오전에만 그랬고 다시 알고리즘으로 돌아오니까 어려워졌지만...

 

그래도 아예 100% 이해한다는 생각을 버리니 훨씬 괜찮아졌다.

오늘 3주차를 들었으니까 내일 4주차, 그다음 5주차...완강한다고 다는 아니니까.

다 들어놓고 큰 틀과 용어들만 짚고 넘어가고,

기초 문제부터 풀면서 '아 이런게 이 문제에서 쓰일 수 있겠구나' 하고 알게 되는 날이 올 거라고 믿는다.

아직은 잘 모르겠지만.

 

오늘도 프로그래머스에서 level 0문제를 풀었는데 그 중에서도 영 오래 걸리는 문제도 있고,

쉽게 풀리는 문제도 있었으니까.

같은 레벨인데 난이도는 천차만별이다. 오늘 한 문제를 꽤 오래 붙잡고 있었어서 시간이 더 빨리 지나갔다.

 

그래도 이것저것 허둥거리던 지난주보다 오늘 월요일이 더 각잡혀서(?) 공부한 기분이다.

지난주에는 9시 시작 전에 투두리스트를 만들어놓고 그대로 하지 않았는데,

오늘은 그래도 그 투두리스트대로 한 느낌?

 

내일도 오늘처럼 웹 퍼블리싱을 듣고, 알고리즘 듣고 문제푸는 하루를 이어갈것 같다.

중간에 너무 어렵거나 집중이 안되면 다른 강의로 넘어가고.

 

자꾸 파이썬을 하니까 자바스크립트를 까먹을것 같기도 하고? 이것도 방법 찾는다고 해놓고 아직 고민중이네.

여튼, 아직 갈길이 멀지만...일단 월요일은 잘 보냈다...!