1️⃣ BOJ 1051 - 숫자 정사각형
문제
N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.
최적화 이전 코드
n, m = map(int, input().split())
L = []
for i in range(n):
S = input()
l = []
for j in S:
l.append(int(j))
L.append(l)
res = 0
for i in range(n-1):
for j in range(m-1):
for k in range(j+1, m):
if L[i][j] == L[i][k]:
dif = k-j
if i+dif < n and L[i+dif][j] == L[i+dif][k] == L[i][j]:
res = max(res, dif)
print((res+1)**2)정사각형의 윗 꼭지점 기준 크기가 최소 2인 관계만 조사하도록 반복문을 작성했다.
IndexError: list index out of range 가 나오지 않도록 index에 신경쓰려고 했다.
다소 헤맸던 부분이라면 여느 input과는 다르게 숫자가 붙어있는 채로 input이 들어왔기 때문에
list(map(int,input().split())) 으로 입력 받았다간 그냥 큰 수 하나만 받는 꼴이 된다.
그래서 붙어있는 숫자를 list로 분리하는 코드가 필요했다.
당장에 이쁜 코드가 생각나지 않아서 지저분하게 작성했지만 풀고나서 알아보니 1줄로 간결하게 작성할 수 있었다.
L.append(list(map(int,input())))정답
n, m = map(int, input().split())
L = []; res = 0
for i in range(n):
L.append(list(map(int, input())))
for i in range(n-1):
for j in range(m-1):
for k in range(j+1, m):
if L[i][j] == L[i][k]:
dif = k-j
if i+dif < n and L[i+dif][j] == L[i+dif][k] == L[i][j]:
res = max(res, dif)
print((res+1)**2)2️⃣ BOJ 1120 - 문자열
문제
두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.
1. A의 앞에 아무 알파벳이나 추가한다.
2. A의 뒤에 아무 알파벳이나 추가한다.
이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.
정답
a, b = input().split()
dif = len(b) - len(a)
min_cnt = 51
for i in range(dif+1):
cnt = 0
for j in range(len(a)):
if a[j] != b[j+i]:
cnt += 1
if min_cnt > cnt:
min_cnt = cnt
print(min_cnt)길이가 같을 때 탐색이 끝난다는 이유로 A의 뒤에 아무 알파벳이나 추가한다라는 연산이 존재하는데 그냥 B보다 길이가 작거나 같은 A를 한칸씩 옮겨가면서 최소 차이를 구하면 되는 간단한 문제이다.
3️⃣ BOJ 1174 - 줄어드는 수
문제
음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다.
N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 만약 그러한 수가 없을 때는 -1을 출력한다. 가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.
정답
N = int(input())
res = set()
num = []
def DF():
if num:
res.add(int(''.join(map(str, num))))
for i in range(10):
if not num or num[-1] > i:
num.append(i)
DF()
num.pop()
DF()
res = sorted(res)
print(res[N-1] if N <= len(res) else -1)실버4 풀고 너무 쉬워서 골드5로 점프하니까 이렇게 어려울 줄은 몰랐다;;
문제는 왼쪽부터 자리수가 감소하는 수를 정렬할 때 N번째 수를 구하는 문제이다.
줄어드는 수는 9762처럼 오른쪽으로 갈 수록 숫자가 줄어야 한다.
955 처럼 같은수가 있어선 안 된다.
그리고 줄어드는 수는 9876543210이 가장 큰 수이다.
생각 과정
처음엔 재귀함수로 일의자리부터 왼쪽으로 이동하면서 숫자를 늘리려고 했지만 일의 자리수가 가장 많이 바뀌기 때문에 재귀 끝에 있어야 한다.
그래서 첫 자리부터 오른쪽으로 이동하는 방식으로 재귀함수를 작성하려고 했다.
이 때 고려해야 할 게 한 두가지가 아니었는데
- 리턴 값은 어떻게 해야하는가?
- N번째가 되면 재귀에서 어떻게 빠져나가야 하는가?
- 작아야 한다는 조건은 어디에 어떻게 배치해야하나?
- 0~9에서 10~98, 10~98에서 210~987은 어떻게 넘어가야 하나?
이러한 여러가지 조건들을 계속 생각하면서 짜다보니 재귀를 짜기 너무 복잡했다.
특히 N번째 수에서 재귀를 빠져나가는 부분은 알 수가 없었다.
한 2시간 넘게 고민하다가 너무 오래걸리는 것 같아 모범 답안을 참고하기로 하였다.
이 답안을 보고 깨달은 점이 2가지이다.
- 메모리 제한은 생각보다 널널하다. 즉, 모든 경우의 수를 미리 담고 골라내도 된다.
- 모든 경우의 수가 그렇게 크지 않다면 set에 넣고 sorted list로 변환해도 충분하다.
너무 모범 답안이라 아직까지 저 재귀함수의 동작 방식이 100% 이해가 되진 않았다.
백트래킹을 하면서 재귀함수를 많이 만들어봐야 할 것 같다.
배운 점
num = []
if num:
print("배열이 비어있으면 False다")배열을 if에 넣으면 비어있으면 False, 아니면 True이다.
num = [1,2,3]
res = int(''.join(map(str, number)))
print(res) # 123join과 map을 이용해 숫자 배열을 이어진 숫자로 변환할 수 있다.
4️⃣ BOJ 1182 - 부분수열의 합
문제
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
오답
N, S = map(int,input().split())
L = list(map(int,input().split()))
cnt = 0
for i in range(N):
for j in range(0,N-i):
if sum(L[j:j+i+1]) == S:
cnt += 1
print(cnt)처음엔 부분수열이 뜻하는 것이 연속적인 수로 만든 부분수열을 뜻하는 줄 알고 배열 슬라이싱으로 구현했다.
정답
from itertools import combinations
N, S = map(int,input().split())
L = list(map(int,input().split()))
cnt = 0
for i in range(1,N+1):
for c in combinations(L,i):
if sum(c) == S:
cnt += 1
print(cnt)부분수열을 모두 Combination으로 조사한 후 합을 조사하고 cnt를 갱신한다.
파이썬에 있는 itertools 라이브러리를 통해 조합을 쉽게 구현할 수 있다.
