목록전체 글 (601)
sm 기술 블로그
N, M = map(int, input().split()) cardNum = list(map(int, input().split())) max = 0 for i in range(0, N-2): for j in range(i+1, N): for k in range(j+1, N): sum = cardNum[i]+cardNum[j]+cardNum[k] if(sum > max and sum 너비 우선 탐색(BFS, breadth first search) brute 무식한 force 힘이다. 완전탐색 알고리즘으로 모든 경우의 수를 모.." data-og-host="smhope.tistory.com" data-og-source-url="https://smhope.tistory.com/196" data-og-url="..
브루트 포스(brute force) => 너비 우선 탐색(BFS, breadth first search) brute 무식한 force 힘이다. 완전탐색 알고리즘으로 모든 경우의 수를 모두 탐색하면서 요구 조건에 충족되는 결과만을 가져온다. 완전탐색이기 때문에 예외없이 100%확률로 정답만을 출력한다. 문제해결 방법 주어진 문제를 선형 구조로 구조화 구조화된 문제공간을 적절한 방법으로 해를 구성할 때 까지 탐색 구성된 해를 정리한다. 예시 4자리 숫자로 된 핸드폰 암호는 0000~9999까지 총 1만개이다. 이를 하나씩 대입해가면서 핸드폰 암호를 확인하는 것이다. 단점 자원이 문제이다. 위의 예시에서 비밀번호가 한자리가 늘어날 때 마다 기하 급수적으로 차지하는 자원이 많아지며 복잡도가 증가한다.
let input = require("fs").readFileSync("ex.txt").toString().split(" "); N = parseInt(input[0]); let result = ""; const Hanoi = (A, B, C, N) => { if (N === 1) { result += A + " " + C + "\n"; return; } Hanoi(A, C, B, N - 1); result += A + " " + C + "\n"; Hanoi(B, A, C, N - 1); }; console.log(2 ** N - 1); Hanoi(1, 2, 3, N); console.log(result); console.log를 이용하면 느려 시간초과가 발생한다. 따라서 result에 받아서 한번에 출..
N = int(input()) def Hanoi(A, B, C, N): # A:1 B:2 C:3 if N == 1: print("{0} {1}".format(A, C)) # 처음 print라고 정의함 return Hanoi(A, C, B, N-1) print("{0} {1}".format(A, C)) # 마지막 print 라고 정의함 Hanoi(B, A, C, N-1) print((2**N)-1) Hanoi(1, 2, 3, N) 먼저 이동 순서를 한번 보자. 하노이탑 n = 3 일때 위와 같이 이동한다. 어떻게 이동 되는지 이해가 됐는가? 그럼 설명에 들어간다. 재귀 함수를 사용하여 하노이탑 문제를 풀어야한다. 기본적으로 총 움직이는 횟수는 2의 들어온 값의 제곱 - 1 이다. => (( 2**n )-1..