250x250
250x250
JinSeopKim
Hello World!
JinSeopKim
전체 방문자
오늘
어제
  • 분류 전체보기 (168)
    • Artificial intelligence (14)
      • DeepDiveToAI (3)
      • Pytorch (3)
      • Etc (8)
    • Back-end (19)
      • Spring (10)
      • JPA (9)
    • Language (24)
      • Python (3)
      • Java (11)
      • Swift (10)
    • Math (4)
      • Linear Algebra (4)
    • CodingTest (79)
      • Algolithm (12)
      • Backjoon (25)
      • Programmers (42)
    • Etc (27)
      • Book Review (3)
      • Adsp (6)
      • Life (2)
      • Docker (1)
      • odds and ends (15)
    • AI Life (0)
      • 생각 넓히기 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • GitHub

인기 글

태그

  • 문제풀이
  • 개발자
  • 선형대수
  • 프로그래머스
  • data
  • 머신러닝
  • Front-end
  • 알고리즘
  • 코딩테스트
  • 카카오
  • 파이썬
  • BOJ
  • JPA
  • 구현
  • 자바
  • uArm
  • DP
  • 개발
  • 백준
  • ADsP
  • AI
  • ios
  • swift
  • 브루트포스
  • BFS
  • java
  • Python
  • SpringMVC
  • JAVA8
  • certificate

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
JinSeopKim
CodingTest/Algolithm

브루트포스(2) 재귀

브루트포스(2) 재귀
CodingTest/Algolithm

브루트포스(2) 재귀

2021. 11. 2. 02:10
728x90
728x90

재귀를 쓰면

재귀를 쓰면 모든 경우의 수를 확인하도록 만들 수 있다.

재귀를 써서 모든 경우를 확인하는 경우는 두가지이다.

 

1. 순서가 있는 경우(P)

n개의 수를 나열하는 방법의 수이다.(중복가능)

-> O(n!)

/**
* index -> 현재 수를 놓는 위치
* arr -> 확인하려고 만드는 배열
*/
public void recursive1(int index, int[] arr){
	if(index == arr.length){
		//종료 조건
    }
	for(int i = 1; i <= n; i++){
    	arr[index] = i;
        recursive1(index+1,arr)
	}
}

 

2. 위치(C)

1~n 중 몇개를 사용할 지 판단한다.

-> O(2^n)

/**
* index -> 현재 수를 놓는 위치
* arr -> 확인하려고 만드는 배열
*/
public void recursive2(int cnt, int[] arr, int value, int n){
	if(index == arr.length){
		//종료 조건
    }
    
    if(value > n) return; //종료조건
   
    arr[cnt] = value
    recursive2(cnt+1,arr,value+1,n) // 해당 값을 사용한 경우
    
    recursive2(cnt,arr,value+1,n) // 해당 값을 사용하지 않은 경우
}

 

백 트래킹

불필요한 재귀를 돌지 않도록 조건이 맞지 않으면 사전에 종료시켜버리는 방법이다.

728x90
728x90
저작자표시 비영리 (새창열림)

'CodingTest > Algolithm' 카테고리의 다른 글

비트마스크 알고리즘  (0) 2021.11.10
브루트포스(3) 순열  (0) 2021.11.03
브루트포스(1) - 무작정 해보기  (0) 2021.10.12
최대, 최소공배수 그리고 소수  (0) 2021.10.10
약수  (0) 2021.10.07
  • 재귀를 쓰면
  • 백 트래킹
'CodingTest/Algolithm' 카테고리의 다른 글
  • 비트마스크 알고리즘
  • 브루트포스(3) 순열
  • 브루트포스(1) - 무작정 해보기
  • 최대, 최소공배수 그리고 소수
JinSeopKim
JinSeopKim
기록📚

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.