- 참치군
- ?
- stalk.io
- :: 2013년, 스리는 여섯살
- 웹 강좌
- 점프 투 파이썬
- 요니나의 대학생 재테크
- This is CS50
- 애자일 이야기
- isao의 IT,게임번역소
- 소프트웨어 이야기
- Color Scripter
- 어디를 가든지 마음을 다해 가라
- VisuAlgo
- 서울대 평생교육원
- 몽환
- RegExr: Learn, Build, & Test R…
- Hello, Stranger :D
- I Like Exploit
- Z3alous Security Story
- Project Euler
- Blog
- pieces of code
- window 쪼물딱 거리기
- IT - Informatics Alphabet
- rop
- 국제 정보교육센터 I2sec 대구 1기
- This is the moment. :)
- blackmoon
- z3alous는 세상에 소리 z3alous~
- Acord
- FORENSIC-PROOF
- 어셈블리
- Outsider's Dev Story
- Open Tutorials
- 코드라이언
- 컴퓨터 그래픽스와 3D 프린팅
- HACKABILITY
- Lee, Jae-Hong
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- 창의공학설계
- Packet
- Wireshark
- Debug
- 호출규약
- 추상데이터타입
- 오지총
- 베이스
- 염색
- 발표
- 컴파일러
- 공간복잡도
- Visual Studio
- C언어
- 버퍼오버플로우
- 시간복잡도
- 레지스터
- Calling Convention
- 알고리즘
- BOF
- Hello World
- 피보나치
- 블루블랙
- 펌
- 탈색
- ubuntu
- 파이썬
- 소켓
- 동대구
- 디버깅
- Today
- Total
c0smicb0y
[알고리즘] Backtracking (백트래킹) 본문
백트래킹
정의 : 여러 해들 중에 조건에 맞는 모든 해를 찾는 알고리즘.
알고리즘
1. 후보 해를 선택한다.
2. 조건에 따라 후보 해에 적절성 검사를 시행한다. 통과하지 못하면 지금 현재 선택한 후보 해를 버리고 1로 돌아가 후보 해를 다시 선택한다.
3. 적설성 검사가 통과한 경우 이 후보 해가 문제의 해가 되는지 검사한다. 검사를 통과하면 이것이 문제의 해이고, 검사를 통과하지 못하면 1로 돌아가 후보 해를 계속해서 선택한다.
백트래킹의 활용
1. 미로 탈출로 찾기
재귀함수를 통해 백트래킹으로 미로 탈출로를 찾아보자.
알고리즘
1. 시작점을 현재 위치로 지정하고, 이동방향을 북으로 설정한다.
2. 현재 위치에서 가고자 하는 이동 방향으로 이동이 가능한지 확인한다. 벽과 이미 지나온 길은 이동가능한 길이 아니다.
3. 현재 가고자 하는 이동 방향으로 이동이 가능하면 그곳으로 이동한다. 이동이 불가능하면 방향을 바꾸어 다시 2번을 수행한다. 모든 방향으로 이동이 불가능하면 이전 위치로 되돌아간다.
4. 출구에 다다르거나 미로 내의 모든 길을 방문할때까지 2, 3단계를 반복한다.
3번 과정에서 이동하는 부분을 재귀함수로 구현하면 될 것이다. 이동이 가능하면 재귀함수를 통해 그곳으로 이동하면 모든 방향으로 이동이 불가능하면 반환을 통해 재귀함수를 탈출하여 이전 상태로 돌아가면 될 것이다.
2. N개의 퀸
체스에서 퀸은 모든 방향으로 거리 제한없이 움직일 수 있는 말이다. N개의 퀸 문제는 N × N 크기의 체스판에서 N개의 말들이 서로 공격이 불가능하게 배치하는 모든 경우를 구하는 문제이다.
알고리즘
1. 첫 행, 첫 열을 시작점으로 지정한다.
2. 현재 지점에서 퀸을 놓으면 다른 퀸에게 위협을 받는지 검사한다. 이전 단계에서 놓은 퀸들 중에 현재 지점에서의 퀸의 행 값이 같으면 수평방향으로 위협을 받는 것이고, 열 값이 같으면 수직방향으로 위협을 받는 것이다. 행의 차와 열의 차가 같으면 대각선 방향으로 위협을 받고 있는 것이다.
3. 위협을 받고 있지 않다면 행의 값을 증가시키고 열의 첫번째 값으로 가서 2를 수행한다. 위협을 받고 있다면 열의 값을 증가시켜서 2를 수행한다. 열의 마지막 값에서도 위협을 받고 있다면 이전 단계의 퀸의 위치로 되돌아간다.
4. 마지막 행, 마지막 열에 다다르면 종료한다.
과정 3을 재귀함수로 구현하면 될 것이다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[알고리즘] Greedy Algorithm (탐욕 알고리즘) (5) | 2015.01.19 |
---|---|
[알고리즘] Dynamic Programming (동적 계획법) (2) | 2015.01.13 |
[알고리즘] Divide and Conquer (분할정복) (1) | 2015.01.11 |