Just Do IT!

스파르타코딩클럽 내일배움캠프 12일차 본문

스파르타코딩클럽 내일배움캠프/TIL

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

MOON달 2022. 11. 15. 21:00
728x90
반응형
오늘의 일과 간단 요약
  1. 웹 퍼블리싱 강의 2주차 완강
  2. Git 강의 약간 + 이전 학습 복습
  3. 알고리즘 강의 4주차 완강
  4. 프로그래머스 Level 0 6문제 (풀이 링크)

 

 

 

 

 

웹 퍼블리싱 강의 2주차
form 태그
  • 사용자로부터 데이터를 입력할 수 있는 범위를 지정할 때 사용
  • (예) 로그인 창
<!DOCTYPE html>
<html>
  <head>
    <meta charset="UTF-8" />
    <script src="https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js"></script>
  </head>
  <body>
    <form id="login">
      <div>아이디 : <input type="input" id="username" /></div>
      <div>비밀번호 : <input type="password" id="password" /></div>
      <div>
        <label><input type="checkbox" id="checkbox"/> 아이디 패스워드 저장</label>
      </div>
      <button type="submit">제출</button>
    </form>

    <script>
      $('#login').submit(function (event) {
        event.preventDefault();  // 화면을 새로고침하는 동작을 막는다.
        var username = $('#username').val();
        var password = $('#password').val();
        var isChecked = !!$('#checkbox:checked').val();
        alert(username + ' / ' + password + ' / ' + isChecked);
      });
    </script>
    
  </body>
</html>

 

fieldset
  • 서로 관련이 있는 것들을 묶을 때 사용

 

간단 요약

웹 퍼블리싱 강의는 전부 완강하면 네이버 페이지를 만드는 것 같다.

아직 2주차라서 nav 와 검색어 창까지만 만들어봤는데, 오랜만에 하니까 실습하려니까 조금 헷갈렸다.

그래도 이게 재밌게 느껴지는 걸로 봐서는 내일배움캠프에 잘 온 것 같긴 한데...ㅋㅋㅋㅋ

어제처럼 알고리즘 강의 전에 들으니까 딱 좋았다. 아침에는 역시 재미있는 강의를 들어야 하는 것 같다.

 

 

 

 

 

 

알고리즘 강의 4주차
  • 선형구조
    • 큐(Queue), 스택(Stack)
    • 자료를 구성하고 있는 데이터들을 순차적으로 나열시킨 형태
    • 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있다
  • 비선형 구조
    • 트리 (Tree)
    • 데이터가 계층적 혹은 망으로 구성되어 있다

 

트리
  • 계층형 비선형 자료구조
  • Node : 트리에서 데이터를 저장하는 기본 요소
  • Root Node : 트리 맨 위에 있는 노드
  • Level : 최상위 노드를 Level 0으로 하였을 때, 하위 branch로 연결된 노드의 깊이를 나타냄
  • Parent Node : 어떤 노드의 상위 레벨에 연결된 노드
  • Child Node : 어떤 노드의 하위 레벨에 연결된 노드
  • Leaf Node (Terminal Node) : Child Node가 하나도 없는 노드
  • Sibling : 동일한 Parent Node를 가진 노드
  • Depth : 트리에서 Node가 가질 수 있는 최대 Level

  • 트리의 종류
    • 이진 트리 (Binary Tree) :각 노드가 최대 두 개의 자식을 가진다
    • 완전 이진 트리 (Complete Binary Tree) : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다는 것
      • 트리의 높이 : 루트 노드부터 가장 아래 리프 노드까지의 길이
      • 완전 이진 트리의 높이: 최대로 해봤자 O(log(N)) 

 

 

힙 (Heap)
  • 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete binary tree)
  • 항상 큰 값이 상위 레벨에 있고, 작은 값이 하위 레벨이 있도록 하는 자료구조
  • 부모 노드의 값 > 자식 노드의 값
  • 최대값을 맨 위로 올릴 수도 있고(= Max 힙) 최솟값을 맨 위로 올릴 수도 있다(= Min 힙).

예제 - 맥스 힙의 원소 삭제

class MaxHeap:
    def __init__(self):
        self.items = [None]

    def insert(self, value):
        self.items.append(value)
        cur_index = len(self.items) - 1

        while cur_index > 1:  # cur_index 가 1이 되면 정상을 찍은거라 다른 것과 비교 안하셔도 됩니다!
            parent_index = cur_index // 2
            if self.items[parent_index] < self.items[cur_index]:
                self.items[parent_index], self.items[cur_index] = self.items[cur_index], self.items[parent_index]
                cur_index = parent_index
            else:
                break

    # 1. 루트 노드와 맨 끝에 있는 원소를 교체한다
    # 2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다. 이 때, 끝에 반환해줘야 하니까 저장
    # 3. 변경된 노드와 자식 노드를 비교한다. 두 자식 중 좀 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꾼다
    # 4. 자식 노드들 보다 부모 노드가 더 크거나 가장 바닥에 도달하지 않을 때까지 3을 반복한다
    # 5. 2번에서 제거한 원래 루트 노드를 반환한다
    
    def delete(self):
        self.items[1], self.items[-1] = self.items[-1], self.items[1]  # 루트 노드와 맨 끝의 원소 교체
        prev_max = self.items.pop() # 삭제하는 원래 루트 노드를 prev_max에 저장 (반환해줘야 하니까)
        
        cur_index = 1  # 꼭대기에 있는 루트 노드의 위치기 때문에 1로 설정
        
        while cur_index <= len(self.items) - 1:
            left_child_index = cur_index * 2
            right_child_index = cur_index * 2 + 1
            max_index = cur_index
            
            if left_child_index <= len(self.items) -1 and self.items[left_child_index] > self.items[cur_index]:
                max_index = left_child_index
                
            if right_child_index <= len(self.items) -1 and self.items[right_child_index] > self.items[cur_index]:
                max_index = right_child_index
                
            if max_index == cur_index:
                break
            
            self.items[cur_index], self.items[max_index] = self.items[max_index], self.items[cur_index]
            cur_index = max_index
            
        return prev_max  # 8 을 반환해야 합니다.


max_heap = MaxHeap()
max_heap.insert(8)
max_heap.insert(6)
max_heap.insert(7)
max_heap.insert(2)
max_heap.insert(5)
max_heap.insert(4)
print(max_heap.items)  # [None, 8, 6, 7, 2, 5, 4]
print(max_heap.delete())  # 8 을 반환해야 합니다!
print(max_heap.items)  # [None, 7, 6, 4, 2, 5]

 

 

 

그래프
  • 연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구조
  • 연결 관계에 초점이 맞춰져 있다
  • Node : 연결 관계를 가진 각 데이터를 의미 (=정점(Vertex))
  • Edge : 노드 간의 관계를 표시한 선
  • Adjacent Node (인접 노드) : 간선으로 직접 연결된 노드(또는 정점)
  • 그래프의 표현 방법
    1. 인접 행렬(Adjacency Matrix) : 2차원의 배열로 그래프의 연결 관계를 표현
    2. 인접 리스트(Adjacency List) : 링크드 리스트로 그래프의 연결 관계를 표현

 

 

DFS (Depth First Search)
  • 탐색할 때 끝까지 파고드는 것
  • 그래프의 최대 깊이만큼의 공간을 요구
  • 공간을 적게 쓰지만, 최단 경로를 탐색하기 쉽지 않다
  • 예제 - 재귀함수
# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
visited = []  # 방문한 걸 저장하기 위한 인덱스

# 1. 시작 노드(루트 노드)인 1부터 탐색합니다.
# 2. 현재 방문한 노드를 visited_array에 추가합니다
# 2. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문합니다

def dfs_recursion(adjacent_graph, cur_node, visited_array):
    visited_array.append(cur_node)
    
    for adjacent_node in adjacent_graph:
        if adjacent_node not in visited_array:
            dfs_recursion(adjacent_graph, adjacent_node, visited_array)
    return


dfs_recursion(graph, 1, visited)  # 1 이 시작노드입니다!
print(visited)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!
  • 예제 - 스택
# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
visited = []  # 방문한 걸 저장하기 위한 배열
stack = 1  # 시작 노드에 1을 넣어둔다

# 1. 시작 노드를 스택에 넣는다
# 2. 현재 스택의 노드를 빼서 visited에 추가
# 3. 현재 방문한 노드와 인접한 노드 중에서 방문하지 않은 노드를 스택에 추가


def dfs_stack(adjacent_graph, start_node):
    stack = [start_node]
    visited = []
    
    while stack:
        current_node = stack.pop()
        visited.append(current_node)
        for adjacent_node in adjacent_graph[current_node]:
            if adjacent_node not in visited:
                stack.append(adjacent_node)
    return visited


print(dfs_stack(graph, 1))  # 1 이 시작노드입니다!
# [1, 9, 10, 5, 8, 6, 7, 2, 3, 4] 이 출력되어야 합니다!

 

 

 

BFS (Breadth First Search)
  • 갈라진 모든 경우의 수를 탐색해보고 오는 것
  • 최단 경로를 쉽게 찾을 수 있다
  • 모든 분기되는 수를 다 저장하다보니 공간을 많이 써야 하고, 시간이 더 오래 걸릴 수 있다.
  • 예제 - 큐
# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 3, 4],
    2: [1, 5],
    3: [1, 6, 7],
    4: [1, 8],
    5: [2, 9],
    6: [3, 10],
    7: [3],
    8: [4],
    9: [5],
    10: [6]
}

# 1. 시작 노드를 큐에 넣는다
# 2. 현재 큐의 노드를 빼서 visited에 추가
# 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다


def bfs_queue(adj_graph, start_node):
    queue = [start_node]
    visited = []
    
    while queue:
        current_node = queue.pop(0)  # 0번째 코드를 뽑아오겠다는 의미
        visited.append(current_node)
        
        for adjacent_node in adj_graph[current_node]:
            if adjacent_node not in visited:
                queue.append(adjacent_node)
    
    return visited


print(bfs_queue(graph, 1))  # 1 이 시작노드입니다!
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

 

 

 

Dynamic Programming (동적 계획법)
  • 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
  • 문제를 쪼개서 정의할 수 있으면 사용하면 된다 ⇒ 그 결과를 기록하고 이용한다
  • Memoization : 결과를 기록하는 것 = 각 구간마다의 시간을 계산하면 최적의 시간을 구할 수 있는 것
  • Overlapping Subproblem (겹치는 부분 문제) : 문제를 쪼갤 수 있는 구조 = 이미 실험했던 내용을 기록해두고 쓰면 된다는 것
  • 겹치는 문제일 경우 동적 계획법을 사용하면 되는데, 이 때 사용하는 방법이 메모이제이션이다.
  • 예제 - 피보나치 수열
input = 50

# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
    1: 1,
    2: 1
}

# 1. 만약 메모에 있으면 그 값을 바로 반환하고
# 2. 없으면 아까 수식대로 구한다
# 3. 그 값을 다시 메모에 기록한다

def fibo_dynamic_programming(n, fibo_memo):
    if n in fibo_memo:
        return fibo_memo[n]
    
    nth_fibo = fibo_dynamic_programming(n - 1, fibo_memo) + fibo_dynamic_programming(n - 2, fibo_memo)
    fibo_memo [n] = nth_fibo
    return nth_fibo


print(fibo_dynamic_programming(input, memo))

 

 

 

 

 

 

 

짧은 일기

어제부터 큰 기대 안하고(?) 알고리즘 강의를 듣고 있는데, 오히려 그러니까 더 이해가 잘 되는 것 같다(?)

문제를 풀 수 있다는 소리는 아니고, 그냥 이게 이런거구나 하고 생각하고 강의 듣고 예제 문제를 보니까

뭔가 코드의 흐름을 조금이나마 알 수 있게 되었다. 그렇다고 내가 풀 수 있단 건 아니고...

이런 형식을 BFS라고 하는구나, 동적 계획법이 이런 거구나...하면서 고개를 끄덕이고

나중에 문제 유형들을 모아 놓은 걸 보면 그래도 그게 생각날 것 같다는 말이다.

큰 욕심을 안부리고 딱 요 정도만 알고 넘어갔음면 좋겠다.

(솔직히 이렇게 지금 생각해도 나중에 막상 문제를 마주하면 기억 못할 거지만...ㅋㅋㅋ 

한번 보고 넘어간 거랑 아예 모르는 거랑은 다를 테니까...)

 

웹퍼블리싱 → 알고리즘 → 프로그래머스 level 0 

이 형식으로 이틀 공부해봤는데 괜찮은것 같다. 여기에 중간에 git 강의를 잠깐 듣다 말았는데,

인국님이 괜찮다고 하니까 나도 들어봐야지..

아 근데 이렇게 계속하다 보니까 시간이 너무 없는 것 같기도 하고?

내일부터는 특강이 있던데.

 

한번 보고 내일은 알고리즘 강의를 진도표대로 들어야겠다.

프로그래머스 문제도 내일부터는 그렇게 많이 풀지는 못할 것 같다.

새로운 걸 배우면 거기에 또 시간을 쏟을 테니까...

level 0부터 푸는 게 좋은 것 같다. 자바스크립트로 푸니까 까먹지도 않고(?)

 

여튼.

그래도 점점 알고리즘에 대한 경계가 무너지는것 같다.

이렇게 말하니까 너무 잘 아는 것처럼 느껴지지만 그건 절대절대 아니고.

어제 매니저님이랑 면담하면서 들었던 것처럼 '아 이런게 있구나' 정도?

나중에 다시 돌이켜서 공부하면 지금같이 얇은 지식층이 조금 더 두꺼워지겠지, 하는 정도로?

뭔가 흘러가듯이 강의를 듣는것 같아서...약간 그렇지만 그래도 듣고 넘어가는 게 좋으니까.

 

내일부터는 실시간 특강이 있어서 어떤 식으로 개인 시간을 보내야할지 모르겠지만,

어제 오늘과 비슷한 패턴일것 같다. 이제 슬슬 프로젝트에 대한 생각도 해야 하니까.

728x90

'스파르타코딩클럽 내일배움캠프 > TIL' 카테고리의 다른 글

스파르타코딩클럽 내일배움캠프 14일차  (1) 2022.11.17
스파르타코딩클럽 내일배움캠프 13일차  (1) 2022.11.16
스파르타코딩클럽 내일배움캠프 11일차  (1) 2022.11.14
스파르타코딩클럽 내일배움캠프 10일차  (0) 2022.11.11
스파르타코딩클럽 내일배움캠프 9일차  (2) 2022.11.10
'스파르타코딩클럽 내일배움캠프/TIL' Related Articles more