순열
: 서로 다른 것들 중 몇개를 뽑아서 한 줄로 나열하는 것
1. 단순하게 순열을 생성하는 방법
: {1, 2, 3} 을 포함하는 모든 순열을 생성하는 함수
>> 루프를 통한 순열
for i in range(1, 4):
for j in range(1, 4):
if i != j:
for k in range(1, 4):
if i != k and j != k:
print(i, j, k)
'''
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
'''
2. 최소 변경을 통한 방법
: 각각의 순열들은 이전의 상태에서 단지 두 개의 요소들 교환을 통해 생성
>> 재귀 호출을 통한 순열
def f(i, k):
# 깊이가 k이면 리턴
if i == k:
print(p)
else:
for j in range(i, k):
p[i], p[j] = p[j], p[i]
# 그 다음 원소를 결정하러 이동
f(i+1, k)
# 다시 원상복구 시켜주는 방법
p[j], p[i] = p[i], p[j]
'''
p[] -> 데이터가 저장된 배열
k -> 원소의 개수, N -> 선택된 원소의 개수
'''
N = 3
p = [i for i in range(1, N+1)]
f(0, N)
'''
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
'''
3. used 배열을 사용하는 방법
: 사용 여부를 확인하면서 사용하지 않은 숫자를 배열에 추가하는 방식
>> 재귀 호출을 통한 순열
'''
p[] -> 순열을 저장하는 배열, a[] -> 순열을 만드는데 사용할 숫자 배열
n -> 원소의 개수, i -> 지금까지 선택된 원소의 수
used[] -> 사용여부
'''
def f(i, k, r):
# 모든 자리가 다 정해 졌으면
if i == r:
print(p)
else:
for j in range(k):
# 아직 사용되지 않았우면
if used[j] == 0:
used[j] = 1 #사용됨으로 표시
p[i] = a[j] #p[i]는 a[j]로 결정
f(i+1, k, r) #p[i+1]값을 결정하러 이동
used[j] = 0 # 다른 자리에서 쓸 수 있도록 해제
N = 3
R = 3
a = [i for i in range(1, N+1)]
used = [0] * N
p = [0] * R
# nP3
f(0, N, R)
'''
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
'''
연습문제 - Baby-gin Game
설명
0-9 사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때, 3장의 카드가 연속적인 번호를 갖는 경우를 run이라 하고, 3장의 카드가 동일한 번호를 갖는 경우를 triplet이라고 한다.
그리고, 6장의 카드가 run과 triplet으로만 구성된 경우를 Baby-gin으로 부른다.
6자리의 숫자를 입력 받아 baby-gin 여부를 판단하는 프로그램을 작성하라.
완젼탐색,,ㅎ
'''
5
123123
124467
333444
444456
123444
'''
def f(i, k):
global ans
if i == k:
run = 0
tri = 0
if card[0] == card[1] and card[1] == card[2]:
tri += 1
if card[0] + 1 == card[1] and card[1]+1 == card[2]:
run += 1
if card[3] == card[4] and card[4] == card[5]:
run += 1
if card[3] +1 == card[4] and card[4]+1 == card[5]:
run += 1
# baby-gin를 만족하는 순열을 찾으면 return 1
if tri+run == 2:
return 1
else:
return 0
else:
for j in range(i, k):
card[i], card[j] = card[j], card[i]
if f(i+1, k):
return 1
card[j], card[i] = card[i], card[j]
return 0
T = int(input())
for test_case in range(1, T+1):
card = list(map(int, input()))
ans = f(0, 6)
if ans:
print(f'#{test_case} Baby Gin')
else:
print(f'#{test_case} Lose')
'''
#1 Baby Gin
#2 Lose
#3 Baby Gin
#4 Baby Gin
#5 Baby Gin
'''모든 조합을 다 고려하는 방법인듯,,,맞나,,,?
2번째 풀이
'''
5
123123
124467
333444
444456
123444
'''
T = int(input())
for test_case in range(1, T+1):
card = int(input())
# 3개를 연속으로 검사하기 위한 연장된 배열
c = [0] * 12
i = 0
while i < 6:
c[card % 10] += 1
card //= 10
i += 1
tri = 0
run = 0
i = 1
while i < 10:
if c[i] >=3 :
c[i] -= 3
tri += 1
# 더 있을 수 있으니 다시 찾아봐
continue
if c[i] >= 1 and c[i+1] >= 1 and c[i+2] >= 1:
c[i] -= 1
c[i+1] -= 1
c[i+2] -= 1
run += 1
continue
i += 1
if run+tri == 2:
print(f'#{test_case} Baby Gin')
else:
print(f'#{test_case} Lose')
'''
#1 Baby Gin
#2 Lose
#3 Baby Gin
#4 Baby Gin
#5 Baby Gin
'''
부분집합
: 집합에 포함된 원소들을 선택하는 것
- 다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 문제이다.
N개의 원소를 포함한 집합
- 자기 자신과 공집합 포함한 모든 부분집합의 개수는 2^n개
- 원소의 수가 증가하면 부분집합의 개수는 지수적으로 증가
1. 반복문으로 생성
org = [3, 7, 9]
# 반복문으로 부분집합 만들기
for i in [0, 1]:
for j in [0, 1]:
for k in [0, 1]:
# 원소가 늘어나면 for, print가 하나씩 늘어나야 한다...
# print(i, j, k)
if i == 1:
print(org[0], end= ' ')
if j == 1:
print(org[1], end=' ')
if k == 1:
print(org[2], end= ' ')
print()
'''
공백(공집합)
9
7
7 9
3
3 9
3 7
3 7 9
'''
2. 재귀를 통한 생성
# 재귀로 만들기
def par(k):
if k == N :
# print(result)
# 특정 작업을 수행하는 부분,, 여기서는 프린트
for i in range(N):
if result[i] == 1:
print(org[i], end=' ')
print()
return
for i in [0, 1]:
result[k] = i
par(k+1)
org = [3, 7, 9]
N = 3
result = [-1] * N
par(0)
'''
공백(공집합)
9
7
7 9
3
3 9
3 7
3 7 9
'''
3. 비트연산을 통한 생성
# 비트연산으로 만들기
arr = [3, 7, 9]
n = len(arr)
for i in range(1<<n):
for j in range(n):
if i & (1<<j): #j번 비트가 0이 아니면 arr[j]가 부분집합의 원소가 된다
print(arr[j], end=' ')
print()
'''
3
7
3 7
9
3 9
7 9
3 7 9
'''
댓글