본문 바로가기
반응형

알고리즘4

Linear Search (선형검색) 선형검색이란? 선형(직선) 모양으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을 때까지 처음(맨 앞)부터 순서대로 검색하는 알고리즘 예제 다음과 같은 배열 주어졌을 때, 배열 내의 원소 중에서 7을 찾아라 [1,2,3,4,5,6,7,8,9,10] 위의 예제에서 선형 검색의 종료 조건은 다음과 같다. 검색할 값과 같은 요소를 발견한 경우 (검색 성공) 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 (검색 실패) 이 경우, 종료를 위한 판단 조건은 2개이다. 이때 종료를 위한 판단 조건을 줄일 수 있는 방법이 보초법이다. 검색할 키 가밧을 배열의 맨끝에 추가한다. 이 값을 보초(sentinel)라고 한다. 이 경우, 선형 검색의 종료는 무조건 검색할 값의 같은 요소를 발견함으로 1.. 2021. 10. 3.
Binary Search (이진검색) 이진검색이란? 원소가 오름차순 또는 내림차순으로 정렬된 배열에서 원하는 키값(또는 위치)을 찾아내는 알고리즘 배열은 정렬되어 있어야 한다. 정렬된 배열의 중간 임의의 값을 기준으로 찾고자하는 값의 크고 작음을 비교한다. 선택한 중간 임의이 값이 찾는 값보다 크면 그 값은 새로운 최대값이되고, 작으면 새로운 최소값이 된다. 예제 재귀함수로도 구현할 수 있다. 시간복잡도 O(logN) 2021. 10. 3.
DFS와 BFS 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. .. 2021. 8. 12.
BackTracking, DFS, BFS BackTracking "퇴각검색(backtrack)" Backtracking(퇴각검색)이란 한정 조건을 가진 문제를 해결하는 전략이다. - 출처 : wikipedia - 이번에 알고리즘 스터디를 진행하면서 가장 먼저 접한 내용이 backtracking이다. backtracking은 "한정 조건내의 모든 경우의 수를 고려하는 알고리즘" 이다. 구조적을 깊이우선탐색(DFS)를 기반으로 한다. 하지만 DFS는 모든 경우의 수를 다 구하기 때문에 굳이 한정 조건이 존재하는 환경에서는 비효율적이다. 그래서 이와 같이 조건에 부합하지 않는 수를 무시하고 조건을 만족하는 수를 구하는 방법이 백트래킹 알고리즘이다. 그렇다면 여기서 말하는 깊이우선탐색-DFS는 무엇일까? Depth-First Search "깊이우선탐색.. 2021. 8. 12.
반응형