Programming/Algorithm (20) 썸네일형 리스트형 알고리즘: 너비 우선 탐색 (Breadth First Search) 너비 우선 탐색(BFS) 알고리즘 기준점에서 가장 인접한 후보부터 탐색 한 길을 깊이 확인하는 깊이 우선 탐색 (DFS)와 비교됨 최단 경로 구하기에 주로 사용됨. 목적지 발견시 바로 종료할 수 있어 DFS에 비해 빠른 경우가 많음 재귀로 시스템 스택을 사용하는 DFS에 비해 queue를 사용해 스택오버플로우 (Stack over flow)에서 비교적 자유롭고, 힙(Heap) 공간을 넓게 사용할 수 있어 넓은 탐색 범위에 유리함 탐색 초기 Queue에 시작 좌표를 넣고 다음 과정 반복 Dequeue 좌표에서 이동 가능한 모든 경로를 Enqueue 함 다시 Dequeue 좌표에서 이동 가능한 모든 경로를 Enqueue함 도착 지점에 도달할 때까지 2 ~ 3과정 반복 - 양쪽으로 번갈아가며 탐색해 나가기에 .. 알고리즘: 재귀함수 (3) 응용: 미로찾기 미로찾기 조건 - 2차원 그리드(Grid)가 주어짐 - 크기: N * N - 입구 좌표: ( 0 , 0 ) - 출구 좌표: ( n-1, n-1 ) - 미로찾기 알고리즘 해결은 다양한 알고리즘이 있음. 재귀함수가 가장 적합하다는 것 같은데..?.. -- 내용 추가 (2021.03.16 23시 35분) - 개인적으로 가장 적합한 것은 아닌 것 같음. 우선 커리큘럼상 먼저 해당 방법으로 진행된 듯한데, 스택에 담아 탐색하는 경우 모든 경우의 수를 끝까지 가서 판별하기에 속도가 느림. - 반면에 BFS의 경우 큐(Queue) 자료구조로 기준점에서 물의 파동이 퍼져나가듯이 탐색함. 즉, 기준에 인접한 것에 먼저 도달하며 탐색해 나감. 그러다보니 다각도(?)로 진행되는데, 먼저 도달한 곳이 존재한다면 그 즉시 프로.. 알고리즘: 재귀함수 (2) Designing Recursion 설계 조건 적어도 하나의 Base Case가 존재해야 함. ( 종료되는 case ) 모든 case는 결국 Base Case로 수렴함. Recursion과 반복문 작성시 주목할 차이점 암시적 (implicit) 매개변수을 명시적 (explicit) 매개변수로 바꾸어라 예시 (1) 순차 탐색 [ Sequention Search ] int search(int []data, int target){ for(int i=0; i < data.length; i++){ if(data[i] == target) return i; } return -1; } 말 그대로 순차적으로 탐색하는 알고리즘으로 찾는 데이터가 어디에 위치하는지 index 번호 리턴하는 경우 만약 데이터가 정렬되어 있다면 이진검색 진행 만약 순차 검색을 위.. 알고리즘: 재귀함수 (1) Recursion Recursion : 순환 혹은 재귀함수라 칭함 특징 private void func(int n){ if(n 이전 1 2 3 다음
