이따 11시부터 있을 SK텔레콤 코테 대비 머리 가열시켜놓기.
✅ BOJ - BackTracking
🎈 9663 N-Queen
nxn 크기의 체스판 위에 퀸 n개가 있을 때 서로 공격할 수 없게 놓을때 퀸을 최대로 놓을 수 있는 개수를 세는 문제.
n = int(input())
# row : 몇 번째 줄에 몇 번째 칸에 있는가
row = [0] * n
answer = 0
# i: 인덱스 행, row[x]가 열이고, 같은 행, 같은 열, 대각선이 일치하면 False
def checking(x):
for i in range(x):
if row[x] == row[i] or abs(x-i) == abs(row[x]-row[i]):
return False
return True
def dfs(x):
global answer
# 모든 row 탐색 완료 시 + 1
if x == n:
answer += 1
return
else:
for i in range(n):
row[x] = i
if checking(x):
dfs(x+1)
dfs(0)
print(answer)< 풀이 과정 >
전형적인 백트래킹 문제.
checking 함수로 열, 행, 대각선에 같은 퀸이 있는지 확인해주고, dfs함수로 모든 row에 대해 탐색을 진행해준다.
🎈 14888 연산자 끼워넣기
n개의 수로 이루어진 수열 A가 주어지고 수와 수 사이에는 N-1개의 연산자가 주어진다. 마지막 줄로 덧셈, 뺄셈, 곱셈, 나눗셈의 개수가 주어질 때, 만들 수 있는 결과의 최댓값과 최솟값을 이어서 출력하는 문제.
import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
plus, minus, prod, div = map(int, input().split())
maxi = -1 * float("infinity")
mini = float("infinity")
def dfs(plus, minus, prod, div, arr, i):
global maxi, mini
if i == n:
maxi = max(maxi, arr)
mini = min(mini, arr)
else:
if plus:
dfs(plus-1, minus, prod, div, arr+num[i], i+1)
if minus:
dfs(plus, minus-1, prod, div, arr-num[i], i+1)
if prod:
dfs(plus, minus, prod-1, div, arr*num[i], i+1)
if div:
dfs(plus, minus, prod, div, int(arr/num[i]), i+1)
dfs(plus, minus, prod, div, num[0], 1)
print(maxi)
print(mini)< 풀이 과정 >
재귀함수를 반복하여 주어진 숫자와 연산자들을 조합해 최댓값과 최솟값을 구하는 문제.
dfs 함수 내 변수로 덧셈, 뺄셈, 곱셈, 나눗셈, 초기 숫자, 숫자 갯수를 변수로 넣어주고 숫자 갯수가 n과 일치하면 최댓값, 최솟값 계산을 진행해준다.
그렇지 않은 경우 덧셈, 뺄셈, 곱셈, 나눗셈 개수가 있는 경우 dfs 재귀 탐색을 진행한다.
🎈 15686 치킨 배달
크기가 nxn인 도시가 있고 각 도시의 0은 빈칸, 1은 집, 2는 치킨집을 의미한다.
각 집과 치킨 집 거리를 치킨 거리라고 하고 도시의 치킨 거리는 치킨 거리의 합을 의미한다.이 도시에 있는 치킨집은 모두 같은 프랜차이즈로 수익을 최대로 증가시키기 위해 m개의 치킨 집만을 설치하고자 한다. 도시 내 치킨 집 중 m개만 고르고 나머진 폐업 시킬 때, 도시의 치킨 거리를 최소화하는 프로그램을 작성하기.
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10*8)
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
house = []
chicken = []
for i in range(n):
for j in range(n):
if graph[i][j] == 1:
house.append((i, j))
elif graph[i][j] == 2:
chicken.append((i, j))
arr = []
maxi = float("infinity")
def backtracking(num, idx):
global maxi
if num > len(chicken):
return
if idx == m:
total = 0
for x, y in house:
dist = float("infinity")
for i in arr:
cx, cy = chicken[i]
dist = min(dist, abs(x-cx)+abs(y-cy))
total += dist
maxi = min(total, maxi)
return
arr.append(num)
backtracking(num+1, idx+1)
arr.pop()
backtracking(num+1, idx)
return maxi
print(backtracking(0, 0))< 풀이 과정 >
재귀함수로 치킨 집을 하나씩 제거하면서 확인하는 방법 적용해 구현한 문제.
우선 재귀 제한과 한줄씩 입력을 통해 시간 단축을 진행해준다.
n, m과 n줄의 도시 구성을 그래프로 입력받는다. 이후 house와 chicken 리스트를 만들어 추후 치킨거리 계산에 사용해준다.
치킨거리를 구하는 공식은 맨해튼 거리를 구하는 값과 동일하다.백트래킹 함수를 생성해 다음 과정을 거친다.
- 함수 생성에 앞서 arr 배열과 거리 간 최소 값 비교를 위해 float("infinity")를 maxi로 저장을 해둔다.
- num > len(chicken)으로 치킨 리스트에 담긴 치킨 집 개수보다 넘어가면 나오는 에러를 방지
- idx == m으로 골라야 할 치킨집 수와 값이 동일하면 치킨집, 집의 좌표를 뽑아 계산 진행
- 도시의 치킨거리를 total변수로 두고 house의 좌표와 치킨집의 좌표를 각각(x,y), (cx,cy)로 두고 dist를 계산해준다. 도시의 치킨거리는 치킨거리의 합이므로 total += dist 처리.
- 이후 arr.append, backtracking(num+1, idx+1)로 현재 치킨집 선택한 경우 시뮬레이션 진행 후 다음 치킨집 선택 위해 백트래킹 진행
- arr.pop, backtracking(num+1, idx)로 현재 치킨집 선택하지 않은 경우 시뮬레이션 진행
-> 결과적으로 주어진 치킨집 수들로 가능한 치킨집 조합을 구성해 모두 탐색하며 그 과정에서 maxi로 최솟값들을 비교하며 백트래킹 진행.
✅ BOJ - 큐/스택
🎈 17413 단어 뒤집기
문자열 S가 주어질 때 다음 규칙을 지키며 단어를 뒤집으려 한다.
- <, > 가 번갈아가며 등장하며 태그라 부르고 태그내 단어는 뒤집지 않는다.
- S는 알파벳 소문자, 숫자, 공백, 특수 문자로 이루어져 있다.
- 연속하는 두 단어는 공백으로 구분하며 공백을 기준으로 단어를 뒤집어준다.
ex) < ab cd >ef gh< ij kl > -> < ab cd >fe hg< ij kl >
import sys
input = sys.stdin.readline
# 입력 단어, 정답 제출할 answer, 단어 저장할 stack, 태그 내 단어 여부 flag 생성
words = input().rstrip()
answer = ''
stack = []
flag = False
# words 내 모든 문자 탐색
for i in words:
#문자가 <인 경우 태그 시작하는 것 표시해주고 기존까지 stack에 저장된 문자 뒤집고 < 추가
if i == '<':
flag = True
while stack:
answer += stack.pop()
answer += i
#문자가 >인 경우 태그 끝난 것 표시하고 > 문자 그대로 추가
elif i == '>':
flag = False
answer += i
# 태그 내 존재하는 단어들 그대로 추가
elif flag:
answer += i
# 공백인 경우 그동안 스택에 저장된 문자 뒤집어 추가하고 공백도 넣어주기
elif i == ' ':
while stack:
answer += stack.pop()
answer += ' '
# 아무것도 아닌 경우 스택에 문자 저장
else:
stack.append(i)
# <>로 끝난 이후 남게되는 맨 마지막 문자는 False인데도 추가가 안되므로 뒤집어 추가
while stack:
answer += stack.pop()
print(answer)< 풀이 과정 >
은근 구현할게 까다로웠던 문제.
크게 보면 주어진 모든 문자들을 탐색하되 <로 시작하는지, >로 시작하는지 여부와 태그 내 단어들인지 체크해주고 공백도 예외 처리를 해줘야 하는 문제.
결과적으로 문자가 태그로 끝나지 않는다면 flag가 False이지만 else로 처리하기에 stack에만 마지막 문자가 남게 된다. 따라서 마지막 문자에 한해 stack에 값이 저장되있으면 뒤집어 줄 필요가 있음.
🎈 17299 오등큰수
크기가 n인 수열 A가 주어지고 수열 A 내 원소의 등장 횟수를 F(Ai)라고 할 때 오등큰수는 수열 내 원소보다 오른쪽에 있으면서 F(Ai)보다 큰 수 중 가 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우 오등큰수는 -1이다.
import sys
input = sys.stdin.readline
from collections import Counter
n = int(input())
array = list(map(int, input().split()))
counters = Counter(array)
stack = []
answer = [-1] * n
for i in range(len(array)):
while stack and counters[array[stack[-1]]] < counters[array[i]]:
answer[stack.pop()] = array[i]
stack.append(i)
print(" ".join(map(str, answer)))< 풀이 과정 >
앞서 풀었던 오큰수 17298 문제와 유사한 문제로 배열 내 대소관계가 아닌 갯수의 대소관계를 활용한 문제.
Counter 라이브러리를 활용해 array 배열 내 모든 원소들의 개수를 dictionary 형태로 구축한다.
- 이후 빈 리스트로 stack과 n길이만큼의 -1로 채워진 answer 리스트를 준비한다.
- for문을 돌며 array 내 원소들을 탐색하며 stack 리스트에는 인덱스들이 저장된다.
- 이때 stack이 비어있지 않고, 오른쪽에 있는 원소들이 개수가 더 많은 경우에만 answer 리스트 내 값을 개선해준다.
