끄적끄적 개발 블로그입니다.

2 분 소요

  • 자료의 가운데에 있는 항목의 키 값가 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법

    목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행함

  • 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.

  • 검색 과정🔎
    1. 자료의 중앙에 있는 원소를 고른다ㅏ.
    2. 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
    3. 중앙 원소의 값과 찾ㄱ고자 하는 목표 값이 일치하면 탐색을 끝낸다.
    4. 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 잦료의 오른쪽 반에 대해서 새로 검색을 수행한다.
    5. 찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다.

  • 알고리즘: 반복구조

    binarySearch(S[], n, key)
    start <-0
    end <- n-1
      
    WHILE start <=end
        mid <- (start+end)/2
        IF S[mid] ==key
        	RETURN mid
        ELIF S[mid] < key
        	start <- mid + 1
        ELIF S[mid] > key
        	end < mid - 1
    END WHILE
    RETURN -1

  • 알고리즘: 재귀구조

    binarySearch(S[], start,end, key)
    IF start >  end
    	RETURN -1
    ELSE
    	mid <- (start + end)/2
    	IF S[mid] ==key
    		RETURN mid
    	ELIF S[mid] <key
    		RETURN binarySearch(S[], mid+1,end, key)
    	ELSE
    		RETURN binarySearch(S[],start, mid-1,key)

백트래킹(Backtracking)

  • 백트래킹의 유명한 예시

    • nxn 서양 장기판에서 배치한 Queen들이 서로 위협하지 않도록 n개의 Queen을 배치하는 문제

      ➡ 8-Queens 문제

      • 어떤 두 Queen도 서로 위협하지 않아야한다.
      • Queen을 배치한 n개의 위치는?

백트래킹의 특성

  • 퇴각 검색
  • 모든 조합을 시도해서 문제의 해를 찾음
  • 해를 얻을 때까지 모든 가능성을 시도
  • 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지(선택지) 중에 해결책 존재
  • 여러가지(선택지)들이 존재하는 상황에서 하나의 가지를 선택
  • 선택이 이루어지면 새로운 선택지들의 집합이 생성
  • 이런 선택을 반복하면서 최종 상채에 도달
  • 보통 재귀함수로 구현

부분수열

수열(an)이 주어졌을때, 부분수열이란 (an)의 순서는 그대로 유지하면서 몇몇 하들을 제외하여 얻은 수열을 말한다.

DFS(Depth-First Search): 깊이 알고리즘

  • 깊이 우선 탐색(DFS, Depth-First Search)

    트리나 그래프를 탐색하는 기법 중 하나, 시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘

    깊이를 우선시하여 모든 경우의 수를 탐색

    ➡ 완전탐색 알고리즘에 속하지만 항상 완전탐색으로 사용되지 않음

    • 반복문을 활용하거나, 재귀문을 통하여 구현

DFS의 탐색 과정

특정 정점에서 시작하여 역추적(backtracking) 하기 전에 각 분기를 따라 가능한 멀리 탐색

  • 방법
    1. 현재 노드를 방문한 것으로 표시
    2. 방문한 표시가 되어 있지 않은 각각의 인접한 정점을 탐색
    3. 더 이상 방문하지 않은 정점이 없으면 이전 정점으로 역추적
    4. 모든 정점을 방문할 때까지 프로세스 반복

DFS의 장단점

  • DFS의 장점
    1. DFS는 현재 순회 중인 정점만 저장하는 스택 데이터 구조를 사용하기 때문에 BFS에 비해 메모리 공간을 덜 차지한다.
    2. DFS는 목표가 특정 정점(또는 모든 정점)에 최대한 빨리 도달하는 것일 때 유용하다.
    3. DFS를 사용하여 그래프에서 순환을 감지할 수 있다.
  • DFS의 단점
    1. 순환 그래프의 경우 DFS가 무한 루프에 빠질 수 있다.
    2. DFS는 두 정점 사이의 최단 경로를 찾으려는 경우 사용하기에 가장 좋은 알고리즘이 아닐 수 있다.

https://olrlobt.tistory.com/35

오늘 백트래킹 다시 공부하기..

BOJ 3109- 빵집

빵집.gif

업데이트:

댓글남기기

참고