1️⃣ BOJ 1198 - 삼각형으로 자르기
문제
볼록 다각형이 있고, 여기서 3개의 연속된 점을 선택해서 삼각형을 만든다. 그 다음, 만든 삼각형을 다각형에서 제외한다. 원래 다각형이 N개의 점이 있었다면, 이제 N-1개의 점으로 구성된 볼록 다각형이 된다. 위의 과정은 남은 다각형이 삼각형이 될 때까지 반복한다.
볼록 다각형의 점이 시계 방향순으로 주어진다. 마지막에 남은 삼각형은 여러 가지가 있을 수 있다. 이때, 가능한 넓이의 최댓값을 구하는 프로그램을 작성하시오.
정답
from itertools import combinations
N = int(input())
L = []
def calc(a, b, c):
return (abs(a[0] * b[1] + b[0] * c[1] + c[0] * a[1] - a[1] * b[0] - b[1] * c[0] - c[1] * a[0])) / 2
for i in range(N):
L.append(list(map(int, input().split())))
max_num = 0
for l in combinations([i for i in range(N)], 3):
max_num = max(calc(L[l[0]], L[l[1]], L[l[2]]), max_num)
print(max_num)모든 꼭짓점에서 세 꼭짓점을 골랐을 때 최대 넓이를 구하면 되는 문제다.
그래서 꼭짓점 중 3개를 고르기 위해 itertools 라이브러리의 combinations를 사용해서 3개의 꼭짓점을 뽑고 넓이를 구하는 식으로 답을 구했다.
세 좌표로 넓이를 구하는 방법은 신발끈 공식을 사용했다.
오답
from itertools import combinations
N = int(input())
L = []
def calc(a, b, c):
a1 = abs(a[0] - b[0]) * abs(a[1] - b[1])
a2 = abs(b[0] - c[0]) * abs(b[1] - c[1])
a3 = abs(c[0] - a[0]) * abs(c[1] - a[1])
tri = (a1 + a2 + a3) / 2
rect = max(abs(a[0] - b[0]), abs(b[0] - c[0]), abs(c[0] - a[0])) * max(abs(a[1] - b[1]), abs(b[1] - c[1]), abs(c[1] - a[1]))
return rect - tri
for i in range(N):
L.append(list(map(int, input().split())))
max_num = 0
for l in combinations([i for i in range(N)], 3):
max_num = max(calc(L[l[0]], L[l[1]], L[l[2]]), max_num)
print(max_num)이 경우에는 삼각형 넓이를 구하는 공식이 잘못되어 틀렸다.
해당 공식은 사각형에서 삼각형을 빼는 식으로 구하는 방법인데 일부 둔각삼각형에서는 먹히지 않는다.
2️⃣ BOJ 1342 - 행운의 문자열
문제 설명
민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다.
정답
from collections import Counter
S = input()
L = []
def BT(pre, idx):
cnt = 0
if idx == len(L):
return 1
for i in check.keys():
if pre == i or check[i] == 0:
continue
check[i] -= 1
cnt += BT(i, idx+1)
check[i] += 1
return cnt
for i in S:
L.append(i)
check = Counter(S)
res = BT("", 0)
print(res)이 문제는 파이썬이 얼마나 느린 언어인지 깨닫게 해주는 문제였다.
밑에 적은 오답처럼 Permutation을 써보기도 하고 백트래킹 방식으로 풀어보기도 했지만 죄다 최악의 케이스인 abcdefghij에는 굉장히 느린 답변을 내놓았다.
아무리 생각해봐도 풀리지 않아 다른 사람들이 채택한 Counter를 이용한 풀이 방법을 써보기로 했다.
아무래도 딕셔너리를 사용하는 만큼 메모리적인 면이나 시간적인 면에서 유리할 것 같았다.
하지만 이 방법으로도 비슷한 처리시간으로 Python에서는 시간초과가 났지만 PyPy3에서는 이전 방법보단 빠르고 효율적이게 돌아가는 코드인 것 같다.
오답
from itertools import permutations
S = input()
L = []
for i in S:
L.append(i)
cnt = 0
for i in set(permutations(L, len(L))):
for j in range(1,len(i)):
if i[j-1] == i[j]:
break
if j == len(i) - 1:
cnt += 1
print(cnt)10P10은 10!과 같기 때문에 탐색 수가 대략 최대 3천만이 넘게 된다.
이 코드로 abcdefghij를 넣으면 18초정도 걸리게 된다.
PyPy3으로 돌린다 해도 메모리 초과가 나오는 코드였다.
S = input()
L = []
res = set()
def BT(str):
if sum(check) == len(L):
res.add(str)
for i in range(len(L)):
if check[i] == 0 and (True if len(str) == 0 else L[i] != str[-1]):
check[i] = 1
BT(str+L[i])
check[i] = 0
for i in S:
L.append(i)
check = [0 for _ in range(len(L))]
BT("")
print(len(res))그럼 재귀를 쓰면 어떨까? 했지만 여전히 탐색횟수는 10!이 되는 것 같다.
이 경우도 abcdefghij를 넣었을 때 18초정도 걸렸다.
PyPy3으로 돌렸을 때 통과가 된다.
배운 점
from collections import Counter
S = "Hello, World!"
D = Counter(S)
# {'l': 3, 'o': 2, 'H': 1, 'e': 1, ',': 1, ' ': 1, 'W': 1, 'r': 1, 'd': 1, '!': 1}collections 라이브러리에서 Counter라는 것을 사용하면 문자열의 각 개수를 dict로 반환하는 기능을 쓸 수 있다.
def BT(pre, idx):
# 자신보다 하위 단계 함수들의 결과값을 누적시키기 위한 cnt 변수
cnt = 0
# 기저조건 (깊이idx가 문자열 길이와 같아졌을 때)
if idx == len(L):
return 1
# 백트래킹을 위한 반복문
for i in check.keys():
# 백트래킹 조건
if pre == i or check[i] == 0:
continue
# cnt 변수에 결과값 누적, 백트래킹을 위한 변수 컨트롤
check[i] -= 1
cnt += BT(i, idx+1)
check[i] += 1
return cnt백트래킹을 하면서 재귀함수를 짜게 되는데 위 코드처럼 cnt를 통해 자신보다 하위 단계 함수들의 결과값을 누적시키기 위한 변수를 사용하는 방법을 알게 되었다.
3️⃣ BOJ 1235 - 학생 번호
문제 설명
학생들을 더욱 효율적으로 관리하기 위해 학생마다 고유한 학생 번호를 부여하기로 하였다. 학생 번호는 0부터 9 사이의 숫자로 이루어진 문자열로, 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같다.
학생들의 번호가 주어 졌을 때, 뒤에서 k자리만을 추려서 남겨 놓았을 때 모든 학생들의 학생 번호를 서로 다르게 만들 수 있는 최소의 k를 구하는 프로그램을 작성하시오.
정답
import sys
input = sys.stdin.readline
L = []; res = 0
for i in range(int(input())):
L.append(int(input()))
for i in range(1, len(str(L[0]))+1):
S = set()
for j in L:
S.add(j % 10**i)
if len(S) == len(L):
res = i
break
print(res)하나라도 서로 같은게 있는지 판별하려면 Set에 넣고 중복으로 걸러진 것이 있는지 Set의 길이로 구별하면 된다.
문자열에서 슬라이싱을 쓰거나 정수형에서 나머지 연산으로 뒤에서 k자리를 구할 수 있으므로 반복문을 통해 Set에 넣고 중복된 것이 없다면 break으로 빠져나오도록 코드를 구성했다.
이 문제는 input이 1000개정도로 많은 편이기에 sys.stdin.readline을 썼다.
4️⃣ BOJ 1189 - 컴백홈
문제
한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.
cdef ...f ..ef ..gh cdeh cdej ...f bT.. .T.e .Td. .Tfe bTfg bTfi .Tde a... abcd abc. abcd a... a.gh abc. 거리 : 6 6 6 8 8 10 6위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.
정답
R, C, K = map(int, input().split())
L = []; res = []
for i in range(R):
L.append(input().rstrip())
check = [[0 for i in range(C)] for _ in range(R)]
check[R-1][0] = 1
dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def dfs(y, x, depth):
if y == 0 and x == C-1:
res.append(depth)
for i in dir:
nx, ny = x + i[0], y + i[1]
if nx < 0 or ny < 0 or nx >= C or ny >= R:
continue
if check[ny][nx] == 1 or L[ny][nx] == 'T':
continue
check[ny][nx] = 1
dfs(ny, nx, depth+1)
check[ny][nx] = 0
dfs(R-1, 0, 1)
print(res.count(K))도착지점에 도착하면 정답배열에 append하고, 지나간 자리는 check배열을 통해 체크하는 식으로 재귀로 풀었다
실수
2차원 백트래킹의 경우 개념 자체는 최근에 풀어봤던 문제가 있어서 금방 해결될 줄 알았지만 실수들이 있어서 디버깅하는데 반절은 쓴 것 같다.
2차원 배열을 다루다 보면 0~N-1 과 1~N과 같은 인덱스 범위나 [x][y]와 [y][x] 같이 실수 유발하는 포인트들이 있다. 그리고 재귀 이후 check배열을 다시 0으로 초기화하지 않는 실수나 맨처음 집 위치는 이미 지나간 자리라 1로 초기화 하지 않은 실수가 있었다.
