20200303 알고리즘
1. 스토쿠 검사
스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9 개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.
위 그림은 스도쿠를 정확하게 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오 고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색 깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다. 완성된 9×9 크기의 수도쿠가 주어지면 정확하게 풀었으면 “YES”, 잘 못 풀었으면 ”NO”를 출 력하는 프로그램을 작성하세요.
▣ 입력설명 첫 번째 줄에 완성된 9×9 스도쿠가 주어집니다.
▣ 출력설명 첫째 줄에 “YES” 또는 ”NO”를 출력하세요
▣ 입력예제 1
1 4 3 6 2 8 5 7 9
5 7 2 1 3 9 4 6 8
9 8 6 7 5 4 2 3 1
3 9 1 5 4 2 7 8 6
4 6 8 9 1 7 3 5 2
7 2 5 8 6 3 9 1 4
2 3 7 4 8 1 6 9 5
6 1 9 2 7 5 8 4 3
8 5 4 3 9 6 1 2 7▣ 출력예제 1
YES
Solution1
import sys
sys.stdin = open("input20.txt", "rt")
def check(a):
for y in range(9):
ch1 = [0]*10
ch2 = [0]*10
for x in range(9):
ch1[a[y][x]] = 1
ch2[a[x][y]] = 1
if sum(ch1) != 9 or sum(ch2) != 9:
return False
for y in range(3):
for x in range(3):
ch3 = [0]*10
for y2 in range(3):
for x2 in range(3):
ch3[a[y*3+y2][x*3+x2]] = 1
if sum(ch3) != 9:
return False
return True
a = [list(map(int, input().split())) for _ in range(9)]
if check(a):
print('YES')
else:
print('NOT')Solution2 ( 집합 이용 )
import sys
sys.stdin = open("input20.txt", "rt")
a = [list(map(int, input().split())) for _ in range(9)]
s1 = set()
s2 = set()
s3 = set()
isAnswer = True
for y in range(9):
for x in range(9):
if a[y][x] in s1:
isAnswer = False
break
if a[x][y] in s2:
inAnswer = False
break
else:
s1.add(a[y][x])
s2.add(a[x][y])
s1.clear()
s2.clear()
for i in range(3):
for j in range(3):
for p in range(3):
for q in range(3):
if a[i*3+p][j*3+q] in s3:
isAnswer = False
break
else:
s3.add(a[i*3+p][j*3+q])
print(s3)
s3.clear()
if isAnswer:
print('YES')
else:
print('NOT')2. 격자판 회문수
1부터 9까지의 자연수로 채워진 7*7 격자판이 주어지면 격자판 위에서 가로방향 또는 세로방향으로 길이 5자리 회문수가 몇 개 있는지 구하는 프로그램을 작성하세요. 회문수란 121과 같이 앞에서부터 읽으나 뒤에서부터 읽으나 같은 수를 말합니다.
빨간색처럼 구부러진 경우(87178)는 회문수로 간주하지 않습니다.
▣ 입력설명 1부터 9까지의 자연수로 채워진 7*7격자판이 주어집니다.
▣ 출력설명 5자리 회문수의
▣ 입력예제 1
2 4 1 5 3 2 6
3 5 1 8 7 1 7
8 3 2 7 1 3 8
6 1 2 3 2 1 1
1 3 1 3 5 3 2
1 1 2 5 6 5 2
1 2 2 2 2 1 5▣ 출력예제 1
3
Solution1
import sys
sys.stdin = open("input21.txt", "rt")
a = [list(map(int, input().split())) for _ in range(7)]
cnt = 0
for i in range(3):
for j in range(7):
tmp = a[j][i:i+5]
if tmp == tmp[::-1]:
cnt += 1
for k in range(2):
if a[i+k][j] != a[i+5-k-1][j]:
break
else:
cnt += 1
print(cnt)- 파이썬에서는 변수의 이름이 달라도 그 값이 같다면 비교를 했을 때 참이다. ( 같은 id 값을 갖기 때문이다. )
Solution2
import sys
sys.stdin = open("input21.txt", "rt")
a = [list(map(int, input().split())) for _ in range(7)]
def check(list):
for i in range(2):
if list[i] != list[4-i]:
return False
else:
return True
cnt = 0
for y in range(7):
for x in range(3):
tmp = a[y][x:5+x]
if check(tmp):
cnt += 1
for x in range(7):
for i in range(3):
tmp = list()
for y in range(5):
tmp.append(a[y+i][x])
if(check(tmp)):
cnt += 1
print(cnt)3. 이분검색
임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요.
▣ 입력설명 첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다. 두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.
▣ 출력설명 첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.
▣ 입력예제 1 8 32 23 87 65 12 57 32 99 81
▣ 출력예제 1
3
Solution
import sys
sys.stdin = open("input22.txt", "rt")
n, target = map(int, input().split())
a = list(map(int, input().split()))
start = 0
def binarySearch(start, end, target, data):
if start > end:
return None
mid = (start + end) // 2
if target == data[mid]:
return mid + 1
elif target > data[mid]:
start = mid + 1
else:
end = mid-1
return binarySearch(start, end, target, data)
print(binarySearch(start, n-1, target, sorted(a)))Solution2
import sys
sys.stdin = open("input22.txt", "rt")
n, target = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
start = 0
end = n-1
while start <= end:
mid = (start + end) // 2
if a[mid] == target:
print(mid+1)
break
elif a[mid] > target:
end = mid - 1
else:
start = mid + 14. 랜선자르기
엘리트 학원은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이 다. 선생님은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm 은 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
편의를 위해 랜선을 자를때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수 길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
▣ 입력설명 첫째 줄에는 엘리트학원이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다.
▣ 출력설명 첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.
▣ 입력예제 1
4 11
802
743
457
539▣ 출력예제 1
200
Solution
import sys
sys.stdin = open("input23.txt", "rt")
n, m = map(int, input().split())
a = list()
largest = 0
for i in range(n):
tmp = int(input())
a.append(tmp)
largest = max(largest, tmp)
def check(l):
tot = 0
for i in a:
tot += i//l
return tot
res = -2147000000
start = 1
end = largest
while start <= end:
mid = (start + end) // 2
if check(mid) >= m:
res = mid
start = mid + 1
else:
end = mid - 1
print(res)5. 뮤직비디오
지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다. DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지 되어야 한다. 순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다.
지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기 로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.
▣ 입력설명 첫째 줄에 자연수 N(1≤N≤1,000), M(1≤M≤N)이 주어진다. 다음 줄에는 조영필이 라이브에서 부른 순서대로 부른 곡의 길이가 분 단위로(자연수) 주어진다. 부른 곡의 길이는 10,000분을 넘지 않는다고 가정하자.
▣ 출력설명 첫 번째 줄부터 DVD의 최소 용량 크기를 출력하세요.
▣ 입력예제 1
9 3
1 2 3 4 5 6 7 8 9▣ 출력예제 1
17
Solution
import sys
sys.stdin = open("input24.txt", "rt")
n, m = map(int, input().split())
a = list(map(int, input().split()))
start = 1
end = 0
for i in range(m):
end += a[-1-i]
def check(v, musics):
cnt = 1
tmp = 0
for m in musics:
if tmp + m > v:
tmp = m
cnt += 1
else:
tmp += m
return cnt
min = -2147000000
maxx = max(a)
while start <= end:
mid = (start + end) // 2
if maxx <= mid and check(mid, a) <= m:
min = mid
end = mid - 1
else:
start = mid + 1
print(min)- dvd 한 장의 최소 길이는 리스트 원소의 최대값 ( 조건 잘 생각하자 !)
![[HongDongUk]](/static/a60d793d17c3aad0361c9192a3b51381/a12fc/profile.png)