🚩 221026 TIL[Today I Learned]

221026 TIL

백준

Class2

• • • 1012번 문제_유기농 배추
    • 1654번 문제_랜선 자르기
    • 2108번 문제_통계학

---

프로그래머스

Level1

Level2

Level3

---

CS

---

오늘 배운 내용

• Counter 함수

  • Counter 생성는 여러 형태의 데이터를 인자로 받는데 먼저 중복된 데이터가 저장된 배열을 인자로 넘기면 각 원소가 몇번씩 나오는지가 저장된 객체를 얻게 된다.

    from collections import Counter
    >>> Counter(["hi", "hey", "hi", "hi", "hello", "hey"])
    Counter({'hi': 3, 'hey': 2, 'hello': 1})

• BFS / DFS

  • 깊이 우선 탐색(DFS)
    • 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
  • 너비 우선 탐색(BFS)
    • 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
    • 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택

    • DFS(깊이 우선 탐색)	BFS(너비 우선 탐색)
      > 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	> 현재 정점에 연결된 가까운 점들부터 탐색
      스택 또는 재귀 함수로 구현	큐를 이용해서 구현

• BFS

from collections import deque
def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

• DFS

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=" ")
    for i in graph[v]:
        if not visited:
            dfs(graph, i, visited)

• 이분 탐색(Binary Search)
  • 시간복잡도 : O(logN)
  • 정렬된 자료를 반으로 나누어 탐색하는 방법
  • 주의점
    • 자료는 오름차순으로 정렬된 자료여야 한다.