Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
Tags
- 디비
- 알고리즘
- 컴퓨터보안
- 컴퓨터 보안
- rest docs
- API문서
- access control
- 컴퓨터
- IT
- 백트래킹
- S3
- DATABASE
- 스프링부트
- 되추적
- 백준
- 탐욕기법
- OS
- 보안
- node
- 노드
- 인터럽트
- 데이터베이스
- node.js
- ES6
- DB
- 병행제어
- 운영체제
- AWS
- NEST
- 자바스크립트
Archives
- Today
- Total
개발스토리
Backtracking_동전 던지기 본문
동전 던지기
- 3개의 동전들을 던질 때, 나올 수 있는 값들의 모든 가능한 조합들을 출력하는 문제
- 가정) 앞면 : 0, 뒷 면 : 1
- 알고리즘)
for (c1 = 0; c1<= 1; c1++)
for (c2 = 0; c2 <= 1; c2++)
for (c3 = 0; c3 <= 1; c3++)
//[c1, c2, c3]을 출력한다
동전 던지기의 상태 공간 트리
순열 생성
- <1, 2, . . . , N>의 모든 순열을 생성하라.
- 예: N = 3인 경우
<1, 2, 3>, <1, 3, 2>, <2, 1, 3>,
<2, 3, 1>, <3, 1, 2>, <3, 2, 1>
아이디어
배열의 첫 번째, 두 번째와 세 번째 요소를 각각 첫 번째 요소와 교환한 후 배열의 나머지 부분에 대해 순열을 생성하는 일을 재귀적으로 반복한다.
되추적 알고리즘
permute(A[ ], k) // <A[k], A[k + 1], ⋯ , A[N – 1]>의 모든 순열을 생성
// 입력: A[0 . . N – 1] – 순열을 저장하는 배열, k – 배열 A의 지수
// 출력: <A[k], A[k + 1], ⋯ , A[N – 1]>의 모든 순열
1 if (k = N) { A[0 . . N – 1] 을 출력한다; return }
2 for (i = 1; i <= N; i++) // A[k]를 i로 정하기 전에 가능한지 확인
3 if (promising(A, k, i)) { // A[k]를 i로 정하는 것이 가능한 경우
4 A[k] = i
7 permute(A, k + 1) } // <A[k+1], ⋯ , A[N–1]>의 모든 순열을 생성
// 최초 호출: permute(A, 0)
'알고리즘' 카테고리의 다른 글
크루스칼 / 다익스트라 알고리즘 (0) | 2020.11.20 |
---|---|
최소 비용 신장 트리 정의와 프림 알고리즘 (0) | 2020.11.20 |
되추적(Backtracking) (1) | 2020.11.12 |
탐욕 기법 (0) | 2020.10.19 |
계단 오르기 (0) | 2020.10.06 |
Comments