✅ BOJ 문제 풀이
🎈 1051 숫자 정사각형
1칸마다 숫자가 적혀있는 NXM크기의 정사각형이 존재한다. 이때 각 코너에 적힌 숫자가 동일한 정사각형의 최대 크기를 출력하는 문제
n, m = map(int, input().split())
rectangular = []
for _ in range(n):
rectangular.append(list(input()))
v = min(n, m)
answer = 0
for i in range(n):
for j in range(m):
for k in range(v):
if i+k < n and j+k < m:
if rectangular[i][j] == rectangular[i+k][j] == rectangular[i][j+k] == rectangular[i+k][j+k]:
answer = max(answer, (k+1)**2)
print(answer)< 풀이 과정 >
문제 그대로 이해하고, 단순 구현으로 처리한 문제 N,M이 50이하인 자연수 이므로 3중 for문을 돌려도 문제 없다고 판단했다.
- 입력값
n과 m을 입력받아 rectangular 2차원리스트를 문자열로 입력받는다.
그 이후 n,m중 최솟값을 v로 저장하고 직사각형 내 범위 설정을 위해 i+k, j+k가 각각 n,m을 넘지 않는 선에서 각 코너 값이 일치하면 answer에 저장하여 정사각형 크기 중 max값을 뽑아주면 되는 문제.
k가 0이면 1을 출력해야하고, k가 1이라면 2x2 사이즈이므로 (k+1)**2으로 리턴한다.
🎈 2503 숫자 야구
두 player가 있고 한 명이 다른 한명에게 n번 질문을 통해 숫자를 물어보고 몇 스트라이크 몇 볼인지 알려주면서 최종적으로 숫자를 맞추는 player가 유추할 숫자 조합의 개수를 구하는 문제.
from itertools import permutations
n = int(input())
number = list(permutations(['1','2','3','4','5','6','7','8','9'], 3))
for _ in range(n):
n, s, b = map(int, input().split())
n = list(str(n))
k = 0
for i in range(len(number)):
strike, ball = 0, 0
i -= k
for j in range(3):
if number[i][j] == n[j]:
strike += 1
elif n[j] in number[i]:
ball += 1
if s != strike or b != ball:
number.remove(number[i])
k += 1
print(len(number))< 풀이 과정 >
입력받은 숫자들을 조합하여 경우의 수를 구하는 것보다 9개 중 3개를 골라 숫자 조합을 생성하고 전체 조합 중 strike, ball이 일치하지 않으면 삭제하는 방식으로 진행하여 경우의 수를 맞추는 것이 더 낫다고 판단되어 전체탐색 방식으로 진행하였다.
- 입력값
숫자 n을 입력받고, number로 순열조합을 이용해 전체 가능한 경우의 수를 리스트로 뽑아 준 후, n 줄마다 숫자, 스트라이크, 볼을 입력받는다. - 그 이후 n을 문자열의 리스트로 변환하여 각 자리 수마다 체크하여 스트라이크, 볼 수를 체크하여 그 수가 일치하지 않다면 전체 경우의 수에서 그 숫자 조합을 빼가면서 최종적으로 남아있는 경우의 수를 리턴한다.
🎈 10973 이전 순열
[1,n]으로 이루어진 순열이 있고, 입력값으로 순열 경우의 수 중 하나의 조합이 입력된다.
이때 입력받은 순열의 이전 순열을 구하는 문제. 이전 순열이란 사전순으로 나열하였을때 입력값 이전의 값을 의미한다.
import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
for i in range(n-1, 0, -1):
if num[i-1] > num[i]:
for j in range(n-1, 0, -1):
if num[i-1] > num[j]:
num[i-1], num[j] = num[j], num[i-1]
num = num[:i] + sorted(num[i:], reverse = True)
print(*num)
exit()
print(-1)< 풀이 과정 >
itertools 라이브러리 내 permutations을 이용하여 전체 탐색하여 결과를 제출해보았지만 메모리 초과가 나와 조건을 걸어 입력 받은 수보다 하나 더 작은 값을 출력하는 방향으로 바꾸었다.
- 숫자 n과 순열을 입력받은 후 for문으로 역순을 탐색해 숫자 배열이 전체적으로 오름차순인 경우, -1을 출력하도록 하고 내림차순이 있는 경우에 한해 앞 뒤 숫자 배열 순서를 바꾸어 값을현재보다 한 단계 더 낮게 만들어주고 exit()로 for문을 종료시켜 메모리 초과를 벗어나도록 구현하였다.
🎈 1913 달팽이
자연수 N과 찾고자 하는 변수 값이 주어졌을 때 왼쪽 위부터 시작해 시계 반대방향으로 숫자가 입력된 NXN 그래프를 만들어 그래프와 찾고자 하는 변수값의 위치를 리턴하는 문제
import sys
input = sys.stdin.readline
# input
n = int(input())
k = int(input())
graph = [[0 for _ in range(n)] for _ in range(n)]
# direction 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 초기값 location, value
x, y = n//2, n//2
graph[x][y] = 1
# 다음 값, graph크기
number = 2
graph_size = 3
while x!=0 or y!=0:
while number <= graph_size**2:
if x == n//2 and y == n//2:
up, down, left, right = graph_size, graph_size-1, graph_size-1, graph_size-2
x += dx[0]
y += dy[0]
up -= 1
elif right > 0:
x += dx[3]
y += dy[3]
right -= 1
elif down > 0:
x += dx[1]
y += dy[1]
down -= 1
elif left > 0:
x += dx[2]
y += dy[2]
left -= 1
elif up > 0:
x += dx[0]
y += dy[0]
graph[x][y] = number
number += 1
graph_size += 2
n -= 2
for i in range(len(graph)):
for j in range(len(graph)):
if graph[i][j] == k:
find_x, find_y = i, j
print(graph[i][j], end = ' ')
print()
print(find_x+1, find_y+1)< 풀이 과정 >
음,, 구현하는데 시간을 꽤 투자한 문제.
1부터 시작해 이동하는 패턴을 발견해 구현할 수 있었다. 위, 우측, 아래, 좌측, 다시 위로 이동하는 패턴
- 입력값
그래프 크기를 나타내는 n과 찾고자 하는 변수 k를 입력받고, 그래프를 만들어준다.- 구현 방식
그래프를 보면 대각선은 n^2 값임을 알 수 있다.
이를 이용하여 보면, 그래프 크기가 3일 때 상3, 하2, 좌2, 우1로 1부터 이동함을 알 수 있고
그래프 크기가 5인 경우 9부터 시작해 상5 하4 좌4 우3로 이동하는 패턴을 알 수 있다.
이를 이용하여 while문으로 범위를 지정해주고, 방향마다 몇번 씩 이동하는지 값을 지정해 준 후 0보다 크면 이동시켜 1씩 더해주는 방식으로 구현하였다.- 출력값
최종적으로 값이 입력된 그래프와 찾고자하는 수가 위치한 좌표를 출력한다.
🎈 1697 숨바꼭질
1차원 리스트에서 A에서 B로 이동하는 방법 중 가장 빠른 방법을 골라 시간을 출력하는 문제
방법은 아래 두가지다.
- 1초에 (현 위치 X 2)로 순간이동
- 1초에 현 위치 + 1 혹은 - 1씩 이동
from collections import deque
n, k = map(int, input().split())
li = [0] * 100001
def bfs(x):
queue = deque([x])
while queue:
x = queue.popleft()
if x == k:
return li[x]
for i in (x-1, x+1, 2*x):
if 0 <= i <= 100000 and not li[i]:
queue.append(i)
li[i] = li[x] + 1
print(bfs(n))< 풀이 과정 >
BFS를 이용하여 구현하였다. 우선 1차원의 0으로 된 리스트를 생성해주고, bfs함수를 만들어 deque에 현위치를 저장하고 x-1, x+1, 2*x를 이용하여 다음 노드 입력값 + 1씩 해주어 걸리는 시간을 결과로 출력하였다.
🎈 11724 연결 요소의 개수 BFS
정점 개수와 간선 개수와 정보를 입력받아 연결되어 있는 노드의 그룹 개수를 출력하는 문제
- BFS
from collections import deque import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] visited = [0] * (n+1) for _ in range(m): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u) def bfs(start): queue = deque([start]) visited[start] = 1 while queue: node = queue.popleft() for i in graph[node]: if not visited[i]: visited[i] = 1 queue.append(i) answer = 0 for i in range(1, n+1): if not visited[i]: if graph[i]: bfs(i) answer += 1 else: answer += 1 visited[i] = 1 print(answer)< 풀이 과정 >
BFS를 이용해 풀이를 진행하였다.
- 입력값
n, m을 입력받고 graph와 방문한 여부를 따지기 위해 visited를 생성해준 후 양방향으로 이동 가능이므로 for문으로 입력받은 양 간선의 끝점을 그래프에 추가해준다.- bfs 함수
deque를 만들어 초기노드인 start를 집어 넣고 이동하면서 node로 pop해 다음 노드에 도착 시 방문했는지 아닌지 여부를 따진다.- 생성해준 리스트 graph에서 방문하지 않았을 경우, 그래프 값이 있다면 bfs를 통해 탐색하고 결과값 + 1을 해준다. 만일 그래프에 값이 없다면 방문한 곳이므로 visited = 1처리를 해주고 결과값 + 1을 진행한다.
- DFS
import sys sys.setrecursionlimit(50000) input = sys.stdin.readline n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] visited = [0] * (n+1) for _ in range(m): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u) def dfs(node): visited[node] = 1 for next_node in graph[node]: if not visited[next_node]: dfs(next_node) answer = 0 for i in range(1, n+1): if not visited[i]: dfs(i) answer += 1 print(answer)
< 풀이 과정 >
DFS를 이용한 풀이
재귀함수를 이용하여 현재 노드는 방문처리하고, 다음 노드를 입력받을 때 방문하지 않은 곳이면 재귀함수로 탐색
sys.setrecursionlimit(): 파이썬 인터프리터 스택의 재귀 길이를 늘려주어 런타임에 문제가 없도록 함.
