백트래킹

백트래킹이란?

백트래킹은 직관적으로 말하면 갈 수 있을 때까지 가보고 안되면 돌아와서 다음에 할 수 있는걸 하는 방식입니다.
이전의 상태로 돌아가서 다음 행동을 이어간다는 특징과 호출 스택으로 메서드 호출 이전의 상태를 관리할 수 있는 재귀의 특징이 잘 맞아서 백트래킹은 보통 재귀를 이용해서 구현합니다.

얼핏보면 모든 후보를 검사하는 것처럼 보이지만, 매 단계마다 정답을 찾을 수 있는지에대한 판단을 합니다.

재귀를 이용하기 때문에 백트래킹의 과정은 상태공간 트리 형태로 관리할 수 있습니다.
상태공간 트리의 경로에 있는 노드가 답이 될 수 있는지 확인해보고 답이 될 수 없다면, 더이상 진행하지않고 부모노드로 되돌아간 후 다음 자식 노드로 가서 확인을 계속 합니다.

상태공간 트리에대해서 깊이 우선 탐색을 실시하는데, 그 이유는 부모노드에서 할 수 있는 것을 다 살펴보면, 완전탐색과 다를게 없으며, 자식노드를 타고 내려가면서 불가능한 애들을 쳐내야지만, 불필요한 연산을 줄일 수 있기 때문입니다.

재귀와 백트래킹의 차이점

그렇다면, 백트래킹과 재귀는 똑같은 방식으로 동작하는데 무슨 차이가 있는 것이지? 라는 의문을 가질 수 있습니다.
둘의 가장 큰 차이는 각 단계에서 정답이 될 수 있는지를 체크를 해서 되돌아가는지의 여부입니다. 백트래킹은 기저조건까지 안가도 리턴할 수 있습니다. 문제에서 주어진 정답의 조건을 기저조건처럼 사용합니다. 그렇기 때문에, 재귀호출과 다르게 호출의 최대횟수까지 가지 않고도 알 수 있는 정보를 이용할 수 있습니다.

이런 백트래킹 덕분에 말하지않아도 틀렸는지 알 수 있는 연산들을 피해서 수행시간을 줄일 수 있습니다.

그렇다면 이런 백트래킹 알고리즘은 어떻게 접근하고 설계해야할까요?

백트래킹 알고리즘 접근 방식 및 설계 방법

기본적인 완전탐색의 골격을 만든 후에, 정답의 가능성을 확인하고 정답의 가능성이 0%인 조건에대해서 가지치기하는 식으로 코드를 짜는 것이 유리합니다.
처음부터 백트래킹 방식을 적용하면서 코드를 짜면, 논리적 오류를 범해서 잘못된 결과를 만들어냅니다.(경험담)
그렇기 때문에 기본적으로 완전 탐색으로 접근하고 설계를 한 후에, 모든 가능한 경우의 수 중에서 특정한 조건(정답이 될 수 없는 조건)을 만족하는 경우만 살펴보고 정답이 될 수 있는 가능성이 0%라면 거기서 멈추고 부모노드로 돌아가 다른 선택지를 확인하는 방식으로 코드를 작성할 수 있습니다.

알고리즘 효율성

1. 가지치기가 가능한지 확인합니다. 가지치기는 조건을 확인해서 그 뒤로 탐색을 계속해도 가망이 없는 애들은 더 확인하지않고 배제시키는 것을 의미합니다.

2. 중복 호출되는 애들은 메모이제이션을 통해서 불필요한 추가 연산을 줄일 수 있습니다.

3. 불필요한 작업이 있는지 확인합니다. 가끔 코드를 짜다보면 1번만 비교해도 되는데 불필요하게 여러 번 체크하거나 조건문에 중첩된 조건문에서 상위 조건을 한 번 더 체크하는 경우도 이에 해당합니다.

에스크로

최근 주변에서 에스크로라는 말을 접하는 기회가 많아졌습니다.
특히 거래가 들어가는 서비스와 관련된 내용들을 보다보면 어렵지않게 에스크로라는 말을 볼 수 있었습니다.
그렇다면 도대체 에스크로가 뭘까요??

에스크로란?

에스크로 서비스란 "구매자와 판매자 간 안전한 거래를 보장하기 위해서 도입한 서비스로 구매자의 결제대금을 제3자에게 예치하고 있다가 배송이 완료되면 판매자에게 결제대금을 지급하는 서비스입니다. 에스크로 서비스는 기존 소비자와 판매자 사이에 생긴 주문/배송 거래에서 사기를 방지하기위해서 믿을 수 있는 제 3자가 개입하는 결제안전장치입니다.
아래의 그림(출처)를 보시면 이해에 도움이 될 것입니다.

에스크로 서비스는 고객들의 불편함을 해소하는 방법 중 하나로 중국의 알리바바가 소비자의 신뢰 부족을 해결하고 중국 최대의 온라인 커머스 업체로 도약함과 동시에 알리페이를 세계 최대의 핀테크 기업으로 성장시켰습니다.

에스크로 업체의 신뢰성만 보장된다면 정말 강력한 안전장치라고 생각합니다.
ㅇㅇ페이와 같은 이름을 가진 서비스들이 지속적으로 나오는 것을보면 에스크로 서비스는 다가올 미래의 산소와 같은 존재가 될 것 같습니다.

이번 게시글은 여기서 마치겠습니다.
글 읽어주셔서 감사합니다.