컴공생의 다이어리

너비 우선 탐색(BFS, Breadth First Search) BFS는 가까운 노드부터 우선적으로 탐색하는 방식이며 레벨(level) 순서대로 접근한다. BFS는 최단 경로를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용된다. 큐를 활용해서 구현한다. 장점 노드 수가 적고 깊이가 얕은 해가 존재 할 때 유리 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있음 단순 검색 속도가 DFS보다 빠름 단점 재귀호출을 사용하는 DFS와 달리 큐를 이용해 다음에 탐색 할 노드들을 저장하기 때문에 노드의 수가 많을 수록 필요없는 노드들까지 저장해야 하기 때문에 더 큰 저장공..

깊이 우선 탐색(DFS, Depth First Search) DFS는 그래프에서 깊은 부분(자식들)을 우선적으로 탐색하는 방식이다. DFS는 스택이나 재귀 함수를 사용해서 구현할 수 있다. 탐색 과정이 한없이 진행되는 것을 막고 싶다면 깊이 제한(depth bound)를 사용해서 한업이 진행되는 탐색을 막을 수 있다. 장점 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적음 최선의 경우, 가장 빠른 알고리즘. 운 좋게 항상 해에 도달하는 올바른 경로를 선택한다면, 깊이 우선 탐색이 최소 실행시간에 해를 찾음 찾으려는 노드가 깊은 단계에 있다면 BFS보다 빠르게 찾을 수 있음 단점 찾은 해가 최단 경로가 된다는 보장이 없음 최악의 경우, 가능한 모든 경로를 탐험하고서야 해를 찾으므로, 해..

선형 탐색(Linear Search) 선형 탐색은 일렬로 된 자료를 왼쪽부터 오른쪽으로 차례대로 탐색하는 알고리즘이다. 순차 탐색(Sequential Search)이라고도 한다. 파이썬 코드 def linear_search(arr, search): # for문 사용 for i in range(len(arr)): if arr[i] == search: return True return False linear_search([3, 110, 8, 13, 2], 5) # False 반환 linear_search([3, 110, 8, 13, 2], 13) # True 반환 혹은 def linear_search(arr, search): # while문 사용 i = 0 while i < len(arr): if arr[i..

이진 탐색(Binary Search) 이진 탐색은 정렬된 리스트에 적용할 수 있는 간단한 고속 탐색 기법이며 이분 탐색이라고도 불린다. 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 사람들이 숫자를 맞춰가는 업다운 게임과 같은 방식이다. 참고 : 업다운 게임 - 무한도전 니가 가라 하와이편 탐색 과정 이진 탐색은 데이터가 정렬되어있는 상태에서 진행된다. 시작점과 끝점 사이에 중간점을 정함 (만일, 중간점이 실수라면 소수점 이하를 버림) 중간점에 해당하는 값과 찾고자 하는 값을 비교 찾고자 하는 값이 중간점에 해당하는 값보다 작다면 중간점을 기준으로 왼쪽 부분을, 찾고자 하는 값이 중간점에 해당하는 값보다 크다면 중간점을 기준으로 오른쪽 부분에 해당하는 데이터 범위를 가..

문제 네 가지 기능(배열의 정보 추가, 삭제, 검색 및 정렬)이있는 프로그램을 작성하시오. 배열은 크기 2 * 6 (행 * 열) 정수 유형의 2 차원 배열이다. 첫 번째 열에는 학생 ID가 포함되고 두 번째 행에는 해당 수학 점수가 포함된다. 프로그램이 시작되면 배열이 비어 있다. 사용자의 명령에 따라 반복적으로 수행되는 기능으로 'End'를 입력하면 프로그램이 종료된다. 네 가지 기능 각각에 대한 기능을 만드시오. Append(추가) : 사용자가 입력한 학생 ID와 수학 점수 쌍을 배열 끝에 추가한다. 추가하고 나서 배열을 2차원 모양으로 인쇄한다. Delete(삭제) : 사용자가 입력한 학생 ID와 일치하는 학생ID와 수학 점수 쌍을 삭제한다. 삭제 한후 배열을 2차원 모양으로 인쇄한다. Search..