🪄 DNA
Hamming Distance의 합이 가장 작은 DNA를 구하는 문제
n, m = map(int, input().split())
arr = [str(input()) for i in range(n)]
count = 0
result = ''
for i in range(m):
DNA = [0, 0, 0, 0] # A,T,G,C
# n개의 DNA 중에서 가장 많이 나온 뉴클레오티드 구하기
for j in range(n):
if arr[j][i] == 'A':
DNA[0] += 1
elif arr[j][i] == 'C':
DNA[1] += 1
elif arr[j][i] == 'G':
DNA[2] += 1
elif arr[j][i] == 'T':
DNA[3] += 1
idx = DNA.index(max(DNA))
# Hamming Distance의 합이 가장 작은 DNA 구하기
if idx == 0:
result += 'A'
elif idx == 1:
result += 'C'
elif idx == 2:
result += 'G'
elif idx == 3:
result += 'T'
# Hamming Distance 계산하기
count += n - max(DNA)
print(result)
print(count)Hamming Distance의 합이 가장 작은 DNA == N개의 DNA에서 가장 많이 나온 뉴클레오티드로 구성한 DNA라고 생각하면 된다. 그 후, 만든 DNA와 다른 뉴클레오티드를 가지고 있는 DNA의 개수를 구해서 Hamming Distance를 계산하면 된다.
🪄 체스판 다시 칠하기
8×8 크기의 체스판으로 잘라낸 후에 다시 칠해야 하는 정사각형의 최소 개수를 구하는 문제
n, m = map(int, input().split())
arr = [str(input()) for i in range(n)]
count = []
# 8X8 체스판이 가능한 시작점 범위
for a in range(n - 7):
for b in range(m - 7):
idx1 = 0
idx2 = 0
# 8X8 체스판으로 범위 설정
for i in range(a, a + 8):
for j in range(b, b + 8):
# 체스판의 짝수칸 / 홀수칸은 같은 색을 가진다
if (i + j) % 2 == 0: # 짝수
if arr[i][j] != 'W':
idx1 += 1
if arr[i][j] != 'B':
idx2 += 1
else:
if arr[i][j] != 'B':
idx1 += 1
if arr[i][j] != 'W':
idx2 += 1
print(idx1, idx2)
count.append(min(idx1, idx2))
print(min(count))체스판의 짝수 칸 / 홀수 칸은 같은 색을 가진다는 것을 생각하면서 문제를 풀면 된다.
🪄 영화감독 숌
N번째 영화의 제목에 들어가는 N번째로 작은 "666"를 구하는 문제
n = int(input())
count = 0
num = 1
while True:
if "666" in str(num):
count = count + 1
if count == n:
print(num)
break
num = num + 1영화 제목의 순서는 666, 1666, 2666, 3666, 4666, 5666, 6660, 6661 ... 이라는 것을 이해하고 풀면 된다.
🪄 Four Squares
모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다. n을 최소 개수의 제곱수 합으로 표현하는 문제
import math
def fourSquares(n):
# √n이 정수일 때
if int(math.sqrt(n)) == math.sqrt(n):
return 1
# √(n - i^2)이 정수일 때
for i in range(1, int(math.sqrt(n)) + 1):
if int(math.sqrt(n - i**2)) == math.sqrt(n - i**2):
return 2
# √(n - i^2 - j^2)이 정수일 때
for i in range(1, int(math.sqrt(n)) + 1):
for j in range(1, int(math.sqrt(n - i**2)) + 1):
if int(math.sqrt(n - i**2 - j**2)) == math.sqrt(n - i**2 - j**2):
return 3
# 남은 경우는 4
return 4
n = int(input())
print(fourSquares(n))정답은 1, 2, 3, 4 중에 무조건 있다는 것을 생각하면서 풀면 된다. 대충 찍으면 되는 거 아냐...?
🪄 필터
이미지가 주어졌을 때, 필터링된 이미지를 구하고, 값이 T보다 크거나 같은 픽셀의 수를 구하는 문제
r, c = map(int, input().split())
arr = [[*map(int, input().split())] for _ in range(r)]
t = int(input())
count = 0
# 3X3 필터가 가능한 시작점 범위
for a in range(r - 2):
for b in range(c - 2):
median = 0
filter = []
# 3X3 필터로 범위 설정
for i in range(a, a + 3):
for j in range(b, b + 3):
filter.append(arr[i][j])
filter.sort()
if(filter[4] >= t):
count += 1
print(count)위에서 풀었던 체스판 다시 칠하기 문제와 비슷한 유형이다 ! 체스판보다 이게 더 쉽다.
🪄 숫자 정사각형
직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 문제
n, m = map(int, input().split())
arr = []
for _ in range(n):
arr.append(list(map(int, input())))
num = min(n, m) # 가질 수 있는 최대 크기의 제곱근
size = 1
for i in range(n):
for j in range(m):
for k in range(1, num):
# N X M 범위를 넘지 않을 때
if i + k < n and j + k < m:
vertex = arr[i][j]
if vertex == arr[i+k][j] and vertex == arr[i][j+k] and vertex == arr[i+k][j+k]:
size = max(size, (k + 1)**2)
print(size)가질 수 있는 최대 크기는 N과 M 중에서 작은 수의 제곱이라는 것을 생각하면서 풀면 된다.
🪄 차이를 최대로
직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 문제
from itertools import permutations as pm
n = int(input())
nums = list(map(int, input().split()))
sum = 0
# nums의 순열의 경우들로 반복문
for ans in pm(nums):
temp = 0
# 모든 경우의 수를 확인
for i in range(n-1):
temp += abs(ans[i] - ans[i + 1])
sum = max(sum, temp)
print(sum)괜히 완전탐색 문제에 포함되어있는 것이 아니었다. 모든 경우의 수를 확인해야 된다. 이러면 최댓값이겠지 하면서 멋대로 푸니까 안된다.🙄
