로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.
예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])
집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.
출처: 백준 온라인 저지
<정답 코드>
from heapq import heapify, heappop
from itertools import combinations
while True:
inp = list(map(int, input().split()))
if inp == [0]:
break
n = inp[0]
inp = inp[1:]
com = list(combinations(inp, 6))
heapify(com)
while com:
print(*heappop(com))
print()
combinations를 통해 구현하는 간단한 문제였다.
접근은 아래와 같다.
입력 받은 배열을 k와 S로 구분한 후, combinations를 이용해 6개를 뽑는 집합을 만든다.
🔎 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.
입력 - 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) - 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력 - 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. - 수열은 사전 순으로 증가하는 순서로 출력해야 한다.
드디어 브루트포스 1번 카테고리를 끝내고 N, M 시리즈로 넘어왔다.
이 전에 문제들을 풀면서 N과 M 문제를 4번까지 끝내놔서 바로 5번으로 넘어왔는데, 1번 카테고리에서 고생한 것과 달리 좀 쉬운 문제가 나와서 한숨을 돌렸다.
<정답 코드>
from itertools import permutations
n, m = map(int, input().split())
arr = list(map(int, input().split()))
for p in sorted(permutations(arr, m)):
print(*p)
접근은 따로 설명하지 않겠다.
이번 문제에서는 순열이라는 언급이 바로 나왔으며, 모든 가능한 경우의 수를 출력하고 N과 M이 8 이하라는 조건이 있었기에 망설임 없이 permutations를 이용했다.
ㅇ후에 올라올 N과 M시리즈는 정답률이 50% 미만인 것 들에 대해서만 포스팅 하기로 결정했다.
🔎 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. - 정사각형은 서로 겹치면 안 된다. - 도형은 모두 연결되어 있어야 한다. - 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
출처: 백준 온라인 저지
아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
(테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.)
처음에는 문제를 잘못 읽어서 저것들을 하나씩 다 놔야하는 줄 알고, 이렇게 어려운 문제가 기초 강의 문제라고..? 생각했다.
물론 문제를 푸는 것이 쉽지는 않았으나, 다행히 저 도형들 중 하나만 놓아도 돼서 비교적 많이 쉬워졌다.
배열 원소 값은 상관없었고, N과 M은 500이라는 비교적 작은 숫자여서 완전 완전 탐색으로 진행했다.
product를 이용해서 갈 수 있는 모든 방향에 대해 구했고, (product의 길이는 64였다.) product를 탐색하면서 가장 큰 값을 구하는 그런 방법이었다.
product배열로는 'ㅗ, ㅜ, ㅓ, ㅏ' 모양을 구현할 수 없었기에 해당 방식을 구현하는 함수를 또 작성해준 후에야 정답에 접근할 수 있었다.
import sys
from itertools import product
inp = sys.stdin.readline
def place(x, y):
val = 0
for c in case:
temp = paper[x][y]
nx, ny = x, y
visit = set()
visit.add((nx, ny))
flag = False
for dx, dy in c:
nx = nx+dx
ny = ny+dy
if (nx, ny) in visit:
flag = True
break
if 0 <= nx < n and 0 <= ny < m:
temp += paper[nx][ny]
visit.add((nx, ny))
else:
flag = True
break
if not flag:
val = max(val, temp)
return val
def last_place(x, y):
moves = [[[0, 1], [0, 1], [-1, -1]], [[0, 1], [0, 1], [1, -1]], [[1, 0], [1, 0], [-1, 1]], [[1, 0], [1, 0], [-1, -1]]]
val = 0
for move in moves:
flag = False
nx, ny = x, y
temp = paper[nx][ny]
for dx, dy in move:
nx, ny = nx+dx, ny+dy
if 0 <= nx < n and 0 <= ny < m:
temp += paper[nx][ny]
else:
flag = True
if not flag:
val = max(temp, val)
return val
n, m = map(int, inp().split())
paper = [list(map(int, inp().split())) for _ in range(n)]
answer = 0
case = list(product([[1, 0],[-1, 0],[0, 1],[0, -1]], repeat=3))
for i in range(n):
for j in range(m):
answer = max(answer, place(i, j))
answer = max(answer, last_place(i, j))
print(answer)
작성한 코드는 python3로는 통과하지 못했고, pypy3로는 통과했다. 실행시간과 메모리 사용량 모두 불만족스러웠다. Python3로도 통과하지 못했기 때문에 프로그래머스였다면 정확성만 통과한 코드라 취급하고 다른 방법을 모색했다.
진짜 정답 코드에서는 원리는 같지만 dfs를 활용했고, max값을 이용해 불필요한 계산을 하지 않았다는 점이 내 코드와 차이가 있었다.
<정답 코드>
def dfs(x, y, depth, cur):
global answer
if cur + max_val*(4-depth) <= answer:
return
if depth == 4:
answer = max(answer, cur)
return
for dx, dy in moves:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m and not visit[nx][ny]:
# 'ㅗㅜㅓㅏ' 구현
if depth == 2:
visit[nx][ny] = True
dfs(x, y, depth+1, cur + paper[nx][ny])
visit[nx][ny] = False
visit[nx][ny] = True
dfs(nx, ny, depth+1, cur + paper[nx][ny])
visit[nx][ny] = False
n, m = map(int, input().split())
paper = [list(map(int, input().split())) for _ in range(n)]
answer = 0
visit = [[False]*m for _ in range(n)]
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
max_val = max(map(max, paper))
for i in range(n):
for j in range(m):
visit[i][j] = True
dfs(i, j, 1, paper[i][j])
visit[i][j] = False
print(answer)
접근은 아래와 같다.
모든 좌표에서 dfs를 실행한다.
갔다가 다시 되돌아오는 경우도 있기 때문에 visit을 통해서 방지한다.
모든 도형은 총 4개의 작은 사각형으로 이루어져 있기 때문에 탈출 조건은 아래와 같다.
현재 값에서 가장 큰 값을 가능한 많이 더해도 현재 answer 값 보다 작으면 return한다.
깊이(depth)가 4가 되면 answer을 업데이트한 후 탈출한다.
'ㅗ, ㅜ, ㅓ, ㅏ'는 무조건 갔던 길을 한번 되돌아와야하기 때문에 분기점인 depth=2에서 현재 위치에 대한 재귀를 또 한번 수행한다.
한번의 도형 탐색이 끝나면 방문했던 경로들을 초기화 시켜준다.
일반적으로 재귀 함수는 실행 속도가 느리지만, 탈출 조건이 명확하고 depth가 4밖에 안되기 때문에 빠르게 돌아갔다.
실행속도가 10배 넘게 빨라졌고 메모리 소비량도 1/3가량으로 줄었다.
혹시나 해서 내가 작성했던 'ㅗ, ㅜ, ㅓ, ㅏ'를 확인하는 함수로 진행했을 때는 어떤가 확인해봤더니
그냥 중간정도로 나왔다. Python3로 통과되는 것에 의의를 두기로 했다.
탈출 조건을 잘 설정하는 것만으로도 시간을 많이 단축할 수 있다는 사실이 좀 놀라웠고, dfs는 이제 학을 땠다라고 생각했지만 여전히 모르는 것 투성이었다.
🔎개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 "불량 사용자"라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 "프로도" 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다. "무지"와 "프로도"는 불량 사용자 목록에 매핑된 응모자 아이디를 "제재 아이디" 라고 부르기로 하였습니다.
출처: 프로그래머스
문자열 처리 문제는 언제나 귀찮음을 동반한다.
그리고 해당 문제는 브루트포스가 아닌 방법으로 접근하면 상당히 어렵게 느껴졌다.
제한사항을 잘 읽어보고 바로 브루트포스를 떠올렸다면 상당한 침착한 실력자임이 분명하다..
<정답 코드>
from itertools import permutations
import re
def solution(user_id, banned_id):
n = len(banned_id)
answer = set()
banned_id = [i.replace('*', '.') for i in banned_id]
for per in permutations(user_id, n):
tmp = list(per)
for i in range(n):
if not(re.match(banned_id[i], tmp[i]) and len(tmp[i]) == len(banned_id[i])):
break
else:
tmp.sort()
answer.add(tuple(tmp))
return len(answer)
개인적으로 permutations, combinations를 사용하지 않는 것을 선호하지 않는다.
옛날에 처음 itertools를 알게 됐을 때 신나게 사용하다가 항상 시간초과를 먹었기 때문에 친하지 않다..
하지만 이 문제에서는 배열의 길이가 최대 8이므로 permutation을 이용해도 시간을 많이 잡아먹지 않아 결국은 사용하게 됐다.
접근은 아래와 같다.
user_id에서 banned_id 길이 만큼의 아이디를 순열로 추출한다.
순열로 추출하는 이유: user_id 배열의 순서와 상관없이 banned_id가 구성되었기 때문
추출된 순열 전체를 탐색하면서 banned_id 전체와 매칭되는지 확인한다.
매칭되는가는 re 모듈을 활용해서 진행한다.
re.match 함수는 '.'이 입력된 자리에는 어떤 문자든 대체 가능하기 때문에, 우선적으로 banned_id의 원소를 구성하는 '*'을 '.'로 대체하는 작업을 진행하고 순회한 것이다.
또한, match는 길이와 상관없이 "해당 문자들로 시작한다면 True"이기 때문에 길이 검사를 따로 해줘야한다.
처음에는 match도 직접 구현하려하고, permutation이 아닌 match되는 문자들을 추출한 다음 조합하려했으나, 결국은 banned_id의 길이만큼 반복해야한다는 것이 permutation과 같은 복잡도를 가져 그냥 가져다 쓰게 되었다.
파이썬이라는 언어가 가진 훌륭한 특징인 라이브러리들은 문제 해결에 큰 도움을 줄 수 있지만, 어떻게 동작하는지 정확히 파악하지 않고 쓰면 오히려 문제 해결에 방해가 될 수 있는 것 같다.
🔎1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다. (1 ≤ N ≤ 100,000,000) 1234567891011121314151617181920212223... 이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오. (제한 시간: 0.15초, 파이썬은 0.5초)
해당 문제의 분류가 브루트포스로 되어있어서 설마 진짜 다 작성하고 len으로 구하는건가? 생각이 들어 작성해보니 역시나 시간초과가 떴다.
다른 방법을 생각했으나 해당 방법이 브루트포스인지는 명확하지 않다.
<정답 코드>
n = input()
cur = 1
answer = 0
while cur < len(n):
answer += cur * (10**cur - 10**(cur-1))
cur += 1
answer += cur * (int(n) - 10**(cur-1) + 1)
print(answer)
접근은 아래와 같다.
한 자리 수 부터 시작해 입력 받은 수의 자릿수 -1까지 (자릿수 * 해당 자릿수에 존재하는 숫자 개수)만큼을 더한다.
입력받은 수의 자릿수에 대해서는 (자릿수 * (입력받은 수 - 입력받은 수의 자릿 수의 첫번째 수))를 더한다.
한자리수일 때는 1~9, 9개가 존재하고, 두자리수일 때는 10~99, 90개, 세자리수는 100~999, 900개가 존재한다. 이와 같은 방법으로 계속 더 해나가는 것이다.
예를 들어 n = 1001이면 9+90+900+(4*2) = 1007이 되는 것이다.
내가 작성한 코드도 정답인 코드지만, 조금 더 직관적으로 작성하려면 while문 안에서 cur을 이용하기 보다 9로 시작해 9*10**(cur-1)로 진행해도 될 것 같다.
모든 숫자를 고려해야한다는 것은 사실이나, 기존 브루트포스 문제들과 같이 진짜 모든 경우를 방문하지 않는다는 점에서 브루트포스 문제인지 헷갈렸다.
🔎왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.
아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
리스트의 길이가 9로 고정된 비교적 간단한 브루트포스 문제였다. 7명의 키의 합이 100이 되는 경우 중 한가지만 출력하면 된다.
7명을 선택하는 방법은 $$ _{9}\mathrm{C}_{7} $$ 로 36가지만 검토하면 되므로 Combination(조합)을 이용해서 풀어도 시간 제약에 걸리지 않고 통과할 것이다.
코딩 테스트 도중이라면 위 방법이 먹힘을 확인하고 바로 넘어갔겠지만, 통과하지 못하는 시간 제약이 있을 수도 있어 stack을 이용한 풀이까지 해서 총 2가지 방법으로 풀어보았다.
<정답 코드1>
import sys
from itertools import combinations
inp = sys.stdin.readline
heights = []
for _ in range(9):
heights.append(int(inp()))
heights.sort()
kinds = list(combinations(heights, 7))
for i in kinds:
if sum(i) == 100:
print(*i, sep='\n')
break
우선은 조합을 이용한 풀이다.
itertools에서 제공하는 combinations를 활용해 가능한 모든 조합을 도출하고, 조합 안에서 합이 100인 리스트가 존재하면 출력하고 종료하는 것으로 매우 간단한 코드다.
<정답 코드2>
import sys
inp = sys.stdin.readline
heights = []
for _ in range(9):
heights.append(int(inp()))
heights.sort()
for i in range(9):
for j in range(i, 9):
if sum(heights) - (heights[i]+heights[j]) == 100:
heights.pop(j)
heights.pop(i)
print(*heights, sep='\n')
exit()
반복문을 통해 조합을 구현하되, 7명이 아닌 2명을 선택하고, 최악의 경우는 모든 조합을 검토하지만 최선의 경우에는 한번만 점검해도 답이 도출된다는 점에서 combinations보다 빠를 것으로 기대된다.
접근방법은 아래와 같다.
1. 출력이 오름차순으로 되어야하므로 미리 정렬시켜놓는다.
2. 이중 반복문을 통해 2명을 선택할 수 있는 모든 경우의 수를 순회한다.
3. 순회 도중 합이 100임을 만족하는 선택지가 있으면 해당 2명을 pop한 후 프로그램을 종료한다.
