알고리즘19 [개념] BFS(Breadth-First Search) - python BFS(Breadth Fisrt Search)은 너비 우선 탐색이라는 뜻으로, 하나의 정점으로부터 가까운 노드부터 탐색하는 알고리즘이다. BFS는 그래프 탐색의 일종이다. 그래프 탐색? - 하나의 정점으로부터 시작하여 모든 정점을 한번씩 방문하는 것 직관적인 이해를 위해 먼저 트리를 대상으로 살펴보겠다. BFS는 너비 우선 탐색이라는 이름에 맞게 가로 노드들을 순서대로 방문한다. 1번 행을 모두 탐색하면 2번 행, 2번 행을 모두 탐색하면 3번행... 순서로 탐색을 이어나간다. 탐색 순서: A - B - C - D - E - F 이제는 무향 그래프에서 수행하는 BFS를 살펴보겠다. 해당 정점을 기준으로 탐색을 시작한다. 첫 번째로 방문한 노드와 인접한 노드들을 방문한다. 두 번째로 방문한 노드와 인접한 .. 2022. 3. 20. [개념] 힙 정렬 - python 힙이란 무엇일까? - 최댓값 및 최솟값을 구하는 연산을 빠르게 수행하기 위해 고안된 완전 이진 트리를 기반으로 한 자료구조이다. 그렇다면 완전 이진 트리란 무엇일까? - 우선 트리는 계층적 관계를 표현하는, 노드로 이루어진 비선형 자료구조이다. 이진 트리는 모든 노드의 자식 노드가 2개 이하인 트리 구조를 말한다. 위와 같은 이진 트리 구조에서 마지막 디그리를 제외하고 모든 노드가 채워져 있는 구조를 완전 이진 트리라고 한다. 위 트리 그래프도 완전 이진 트리 형태이다. 이제 다시 힙에 대해 알아보자. 힙에는 두 가지 종류가 있다. 부모 노드의 키 값이 자식노드의 키 값보다 항상 큰 힙을 최대 힙, 부모 노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 최소 힙이라고 부른다. 최대 힙과 최소 힙에서 .. 2022. 3. 17. [BOJ] 1946 신입 사원 - python import sys T = int(sys.stdin.readline()) for _ in range(T): N = int(sys.stdin.readline()) score = [0]*N for i in range(N): # 공백을 기준으로 int형으로 나눠 각각 리스트로 저장한다. # 리스트 내에 리스트로 저장된다. score[i] = list(map(int,sys.stdin.readline().split())) # 첫번째 값을 기준으로 정렬된다. score.sort() # 서류 심사 1등은 합격이기 때문에 1로 초기화한다. count = 1 # 서류 심사 등수를 이미 정렬해놓았기 때문에, # 면접 심사에서 앞의 사람들보다 낮은 등수를 받았다면 탈락이다. # 따라서 이전에 나온 등수 최솟값(min)보다 .. 2022. 3. 16. [BOJ] 2108 통계학 - python 백준 2108번 통계학 문제이다. 계속해서 시간 초과가 나서 좀 오래 걸렸다. 최빈값을 구하는 부분에서 계속 시간 초과가 발생했다. 1차 코드 N = int(input()) array = [] for _ in range(N): array.append(int(input())) # 산술평균 print(round(sum(array)/N)) # 중앙값 array.sort() print(array[N//2]) # 최빈값 dict = {} # 전체 리스트의 값 별로 개수를 세어 딕셔너리 형태로 저장한다. for _ in array: dict[_] = array.count(_) # value값을 기준으로 내림차순으로 정렬한다. sorted_dict = sorted(dict.items(),key = lambda ite.. 2022. 3. 15. 이전 1 2 3 4 5 다음
