codeollie

문제 해석 주어진 식에 괄호를 만들어서 최솟값을 구하는 문제이다. 떠올린 아이디어는 +를 사이에 둔 숫자들을 괄호로 묶는 것이였다. 문제 풀이 sick = input().split("-") num = [] for s in sick: cnt = 0 add = s.split("+") for a in add: cnt += int(a) num.append(cnt) n = num[0] for i in range(1, len(num)): n -= num[i] print(n) 그런데 그 괄호가 쳐지는 것을 어떻게 구현할지 생각하는 것이 쉽지 않았다. 방법은 "-"로 나눠주면 55-50+40 이라면 55, (50+40)으로 나누어지고 그 다음엔 쪼개진 식의 괄호안의 덧셈을 계산해준다. 그리고 각각 더해져서 나온 숫자들..

문제 해석 바로 전에 풀었던 문제와 똑같은 BFS를 돌릴 때 depth를 포함해 튜플 형태로 덱에 append시킨 후 탐색을 진행하는 문제였다. 문제 풀이 import sys from collections import deque N, K = map(int, sys.stdin.readline().split()) deq = deque() cnt = 0 deq.append((N, cnt)) while deq: N, cnt = deq.popleft() if N != K: deq.append((N - 1, cnt + 1)) deq.append((N + 1, cnt + 1)) deq.append((N * 2, cnt + 1)) else: result = cnt break print(result) 우선 테스트 케이스..

문제 해석 우선 태그를 BFS로 검색해서 찾은 문제이지만 BFS로 풀었을때 cnt를 어떻게 셀지를 고민하다가 B를 A로 만드는 규칙이 눈에 보여서 그리디 알고리즘으로 풀었는데 그리디 알고리즘으로도 풀 수 있는 문제였다. 문제 풀이 그리디 import sys A, B = map(int, sys.stdin.readline().split()) def solution(A, B): cnt = 1 while B != A: if B % 10 == 1: B = int(B / 10) else: B = int(B / 2) cnt += 1 if A == B: return cnt else: return -1 print(solution(A, B)) 처음 풀었던 풀이인데 47%에서 틀린 풀이이다. 우선 틀린 이유는 위에 나온 조..

문제 해석 간선과 정점으로 입력을 받지만 인접한 노드의 탐색의 이루어지는 구역의 수를 구하는 기존 문제와 풀이 방식은 똑같다. 문제 풀이 import sys from collections import deque N, M = map(int, sys.stdin.readline().split()) graph = [[] for _ in range(N + 1)] visited = [False for _ in range(N + 1)] for _ in range(M): v1, v2 = map(int, sys.stdin.readline().split()) graph[v1].append(v2) graph[v2].append(v1) result = 0 def BFS(x): deq = deque() deq.append(x)..

문제 해석 합이 입력받은 S인 부분수열을 구하는 문제이다. 처음에 경우의 수를 뽑는 조건을 합이 S인 완성된 순열로 했다. 하지만 합이 0인 경우가 6개의 순열이 된다면 답은 6이 나온다. 부분수열이라는 부분을 간과하고 문제에 알고리즘을 적용한게 실수였던 것 같다. 문제에 대해서 더 자세히 알아보고 풀어보았다. 문제 풀이 import sys N, S = map(int, sys.stdin.readline().split()) arr = list(map(int, sys.stdin.readline().split())) stk = [] result = 0 def DFS(idx, sum): global result if idx >= N: return sum += arr[idx] if sum == S: result ..

문제 해석 대각선을 포함해서 인접한 노드를 찾는 탐색문제였다. 대각선까지 탐색하는 문제는 처음이였지만 어차피 대각선 인덱스만 추가로 탐색을 해주면 되는 것이기 때문에 풀이 자체는 어렵지 않았다. 문제 풀이 import sys from collections import deque def BFS(x, y): dx = [-1, -1, -1, 0, 0, 1, 1, 1] dy = [-1, 0, 1, -1, 1, -1, 0, 1] deq = deque() deq.append((x, y)) graph[x][y] = 0 while deq: x, y = deq.popleft() for i in range(8): nx = x + dx[i] ny = y + dy[i] if nx = H or ny < 0 ..

문제 해석 두 사람의 촌수를 구한다는 의미는 입력받은 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 탐색 시작 노드와 탐색 종료 노드를 뜻하는 것이라고 볼 수 있다. 문제 풀이 import sys from collections import deque N = int(sys.stdin.readline().rstrip()) x, y = map(int, sys.stdin.readline().split()) M = int(sys.stdin.readline().rstrip()) graph = [[] for _ in range(N + 1)] visited = [0 for _ in range(N + 1)] for _ in range(M): v1, v2 = map(int, sys.stdin.readline().spl..

문제 해석 이문제도 이전에 풀어본 문제와 마찬가지로 탐색을 진행한 구역의 수를 구하는 문제이다. 하지만 다른점이 있다면 1인 좌표를 입력받고 보드판을 직접 만들어야 하는 것이였다. 문제 풀이 def BFS(x, y): deq = deque() deq.append((x, y)) graph[x][y] = 0 dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] while deq: x, y = deq.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if nx = N or ny = M: continue if graph[nx][ny] == 1: graph[nx][ny] = 0 deq.append((nx,..

문제 해석 이전에 풀어본 예제와 같은 기본적인 BFS를 이용한 최단경로 문제이다. 문제 풀이 import sys from collections import deque def BFS(x, y): deq = deque() deq.append((x, y)) while deq: x, y = deq.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if nx = N or ny = M: continue else: if graph[nx][ny] == 1: graph[nx][ny] = graph[x][y] + 1 deq.append((nx, ny)) return graph[N - 1][M - 1] N, M = map(int,..

문제 해석 BFS나 DFS를 이용해서 1인 구역의 갯수와 해당 구역의 1의 수를 구하는 문제이다. 이 문제는 저번에 DFS/BFS를 정리하면서 풀었던 예제 아이스크림 얼려 먹기 문제와 미로 탈출 문제를 합친 것 같았다. 그래서 처음엔 그 두 문제의 풀이법을 그대로 섞어서 사용하면 답이 나올 것으로 생각했다. 문제 풀이 두 풀이법의 혼용이라 함은 for i in range(N): for j in range(N): if graph[i][j] == 1: apart.append(BFS(i, j)) 함수의 호출부분이 모든 그래프의 노드를 훑으면서 탐색을 시작할 수 있는 노드를 찾는 방식으로 탐색이 이루어진 구역의 수를 찾는 아이스크림 얼려 먹기 문제의 방식과 if graph[nx][ny] == 0: continu..