2. 로봇이 벽에 부딪히면 -1점, 목적지에 도달하면 +10점 → 점점 더 잘 움직이게 됨
4. 머신러닝 구성 요소
특징(Features) : 입력 데이터의 속성
레이블(Label) : 정답
샘플(Sample) : 입력 데이터 1개 단위
5. 머신러닝 과정 요약
1. 데이터 수집 2. 데이터 분할 : 학습용 (train) / 테스트용 (test) – 보통 80:20 또는 70:30 3. 모델 선택 : 선형 모델, SVM, 신경망 등 4. 학습 (Training) : 모델을 데이터에 적합하게 학습 5. 평가 (Evaluation) : 테스트 데이터를 이용하여 성능 확인 6. 예측 (Prediction) : 실제 사용 상황에서 입력에 대한 출력 예측
입력: 음이 아닌 정수 쌍
출력: 이항계수 의 값
binomialCoef(n, k):
C = [[0 for x in range(k+1)] for x in range(n + 1)]
for i in range(n + 1):
for j in range(min(i, k) + 1):
if j == 0 or j == i:
C[i][j] = 1
else:
C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
return C[n][k]
입력: 무작위로 생성하는 좌표의 개수 n
출력: 원주율 π의 근사 값
# 부채꼴 내의 좌표의 개수
a = 0
# 생성할 전체 좌표의 개수
n = int(input("생성할 전체 좌표의 개수: "))
# 전체 좌표의 수 만큼 반복한다.
for i in range(0, n):
# [0, 2]내의 x, y를 무작위 생성한다.
x = random() * 2
y = random() * 2
# 부채꼴내의 좌표의 개수를 증가한다.
if (x * x + y * y) <= 4.0:
a += 1
# 원주율 pi를 계산한다.
pi = float(a / n) * 4
print(pi)
solve(parameters)
{
generate all possible solutions;
ans = select most feasible solution;
return ans;
}
generate all possible solutions : 가능한 모든 경우를 만든다
select most feasible solution : 가장 적합한(문제를 만족하는) 해를 선택
return : 그 해를 반환
2.2. 구조 (python)
from itertools import permutations
def is_valid(board):
n = len(board)
for i in range(n):
for j in range(i + 1, n):
if abs(board[i] - board[j]) == abs(i - j): # 대각선 충돌
return False
return True
def solve_n_queens_bruteforce(n):
count = 0
for perm in permutations(range(n)):
if is_valid(perm):
count += 1
return count
print(solve_n_queens_bruteforce(8)) # 8-Queen 정답 개수: 92
permutations를 이용해 모든 경우의 수를 만들어서, is_valid()로 유효한지 검사한다
시간 복잡도 : O(n!)
3. 백트래킹 (Backtracking)
3.1. 정의
해를 찾는 과정에서 가능성이 없는 경로를 조기에 차단하고 들어가서 다른 경로를 시도하는 방식
3.2. 구성요소
1. 상태 공간 트리
- 가능한 모든 선택(해 후보)을 트리 구조로 나타낸다
- 루트부터 리프까지 내려가며 해를 구성한다
2. 유망 함수
- 현재 선택이 앞으로 정답이 될 가능성이 있는지 판단한다
- 가능성이 없으면 해당 가지를 더이상 탐색하지 않는다
3. 되돌아가기 (Backtracking)
- 유망하지 않은 경로를 만나면 한 단계 이전으로 되돌아 간다
- 그 위치에서 다음 가능한 선택지를 탐색한다
3.3. 의사코드
expand(node v):
node u
for (each child u of v):
if (promising(u)):
if (there is a solution at u):
write the solution
else:
expand(u)
1. expand(node v): v는 현재 탐색 중인 노드 (예: N-Queen에서 현재까지 여왕을 놓은 상태)
2. node u 자식 노드를 표현할 변수 u 선언
3. for (each child u of v): 현재 노드 v의 모든 자식 노드(u)를 순회하면서 자식 하나하나를 후보 상태로 간주하고 처리
4. if (promising(u)):
현재 자식 상태 u가 가능성 있는(유망한) 상태인지 검사
여기서 가능성이 없다고 판단되면 더 이상 안 내려감
5. if (there is a solution at u): write the solution
u가 완전한 해(최종 상태)라면, 즉 더 이상 놓을 게 없고 조건을 만족한다면, 이 상태를 정답으로 출력
6. else:
expand(u)
아직 해가 아니지만 유망하다면, 재귀적으로 다음 단계로 넘어간다
3.4. N-Queen 문제
n x n 체스판에 n개의 여왕을 놓는 문제
단, 서로 공격하지 못하게 놓아야 한다
*참고
체스에서 여왕은 말 중 가장 강력하므로, 한 번에 가로, 세로, 대각선으로 원하는 만큼 이동할 수 있다
그래서 여왕 두개가 같은 행, 열, 대각선에 함께있으면 안된다
과정
1. 한 행에 하나씩 여왕을 놓는다
2. 각 행마다 어느 열에 놓을지 결정한다
3. 가능한 열을 다 시도하면서 다른 여왕들과 충돌하는지 검사한다
4. 충돌하면 되돌아가서 다른 열 시도 (백트래킹)
5. 충돌하지 않으면 다음행으로 넘어간다
6. 마지막 행까지 다 놓으면 완료
python 코드
입력
- Q : 여왕의 위치를 기록할 리스트
- K : 현재 배치할 여왕의 행 번호
- n : 체스판 크기이자 여왕 개수
출력
- 공격받지 않게 여왕을 놓은 모든 방법
nQueens(Q, k, n):
if k == n:
print(Q)
return
i = 0
while i < n:
Q[k] = i
if Promising(Q, k):
nQueens(Q, k + 1, n)
i += 1
# 유망함수
Promising(Q, k):
i = 0
while i < k:
if Q[k] == Q[i] or abs(Q[i] - Q[k]) == (k - i):
return False
i += 1
return True
pq.enqueue(start_node, g(start_node) + h(start_node))
while pq is not empty:
node = pq.dequeue
if node == goal_node:
break
for next_node in (next_node_begin...next_node_end):
pq.enqueue(next_node, g(node) + cost + h(next_node))
return goal_node_dist
