공부 기록

✏️ 문제 문제 파악배추들이 모여있는 곳을 모두 접근해야 하므로 깊이 우선 탐색을 사용해서 풀었다.그리고 배추들이 모여있는 곳 당 한 마리씩 필요하므로 깊이 우선 탐색을 돌 때마다 개수를 +1 해주면 된다. 여기서 나는 visited 2차원 배열에 조건을 주었는데0 → 방문 안해도 되는 거1 → 방문한 거-1 → 방문해야 되는데 아직 방문 안한 거이렇게 세 가지로 나눠서 조건문을 구분하였다. 아! 그리고 이 문제는 DFS로 풀 때 재귀를 사용해서 풀면 RecursionError 에러가 발생한다. 이는 Python이 정한 최대 재귀 깊이보다 내 코드의 재귀의 깊이가 더 깊어서 발생하는데 이를 해결하는 방법은 2가지가 있다.재귀 함수를 사용하지 않고 스택으로 DFS 구현sys.setrecursionlimit..

✏️ 문제 문제 파악처음 바이러스에 걸린 컴퓨터와 인접된 모든 컴퓨터를 돌아야 하므로 BFS가 아닌 DFS를 사용해서 풀어야 한다. # 1graph = [[0] * (c+1)] * (c+1) graph[1][2] = 1print(graph)# [[0, 0, 1, 0],# [0, 0, 1, 0],# [0, 0, 1, 0],# [0, 0, 1, 0]]# 2graph = [[0] * (c+1) for _ in range(c+1)]graph[1][2] = 1print(graph)# [[0, 0, 0, 0],# [0, 0, 1, 0],# [0, 0, 0, 0],# [0, 0, 0, 0]] 처음 graph 2차원 배열을 초기화할 때 # 1 과 같이했는데 원하는 값이 계속 안나왔다.  찾아보니 # 1 과 ..

✏️ 문제 문제 파악최소의 칸 수를 출력하기 원하므로 전체 경로를 탐색하는 DFS가 아닌 BFS를 사용해야 한다. 또한 상하좌우로 움직일 수 있으므로 상하좌우 하나하나 움직이며 움직인 좌표가 이동할 수 있는 칸인 지, 이미 방문했던 칸은 아닌 지 확인하는 것이 포인트이다. 처음에는 단순히 지나간 칸마다 cnt += 1을 해서 cnt 값을 출력하는 방식으로 문제를 풀었다. 그런데 생각해보니 지나간 칸이더라도 그 이후에 갈 수 있는 경로가 없다면 그 칸을 문제에서 요구하는 최소 칸 수에 포함시키면 안 된다. 그래서 이전의 방문한 칸에 이때까지 지나왔던 칸의 수를 1씩 더하니 답이 나왔다. 알고리즘그래프 이론그래프 탐색너비 우선 탐색  코드import sysinput = sys.stdin.readlinefr..

✏️ 문제 문제 파악  알고리즘매개 변수 탐색이분 탐색  코드import sysinput = sys.stdin.readlinen, m = map(int, input().split())colors = [int(input()) for _ in range(m)]start, end = 1, max(colors)result = endwhile start n: start = mid + 1 else: end = mid - 1 result = min(result, mid)print(result)

✏️ 문제 문제 파악풍선의 개수는 해당 시간에서 각 시간을 나눈 몫의 합이라는 걸 알면 쉽게 풀 수 있다!최대 시간을 end로 주는 걸 생각 못하고 end 없이 코드를 어떻게 짜야하지 .. 하고 있었던 .. 알고리즘매개 변수 탐색이분 탐색  코드import sysinput = sys.stdin.readlinen, m = map(int, input().split())a = sorted(list(map(int, input().split())))start, end = 1, max(a) * mwhile start = m: end = mid - 1 else: start = mid + 1print(start)

✏️ 문제 문제 파악(큰 인덱스 - 작은 인덱스)를 출력해서 문제를 풀었는데선분의 시작점이나 끝점이 점의 좌표와 같을 때 예상 값보다 1개씩 작게 나오는 문제가 있었다..그래서 시작점이나 끝점 중 하나를 원래 인덱스 값보다 -1 해서 계산하면 출력이 잘 나오긴 한다...근데 뭔가 야매로 푼 거 같아서 찝찝 ㅠ 했는데 다른 정답코드를 찾아보니 이런 식으로 나눠서 푸는 게 맞는 것 같다! 휴 알고리즘정렬이분 탐색  코드import sysinput = sys.stdin.readlinen, m = map(int, input().split())point = sorted(list(map(int, input().split())))def bs(ary, l, switch): start, end = 0, n-1 i ..

✏️ 문제문제 파악이분 탐색으로 안풀면 시간 초과가 뜬다. 알고리즘정렬이분 탐색  코드이분 탐색 안쓰고 풀 때 시간 초과 코드import sysinput = sys.stdin.readlinen = int(input())files = sorted(list(map(int, input().split())))cnt = 0for i in range(n-1): for j in range(i+1, n): if files[i] = 0.9 * files[j]: cnt += 1 print(cnt)이분 탐색 사용import sysinput = sys.stdin.readlinen = int(input())files = sorted(list(map(int, input().split())))cnt = 0..

✏️ 문제문제 파악  알고리즘자료 구조해시를 사용한 집합과 맵두 포인터이분 탐색  코드이분 탐색으로 풀려니까 자꾸 시간초과가 떠서 결국 pypy3로 제출 ㅠimport sysinput = sys.stdin.readlinewhile True: n, m = map(int, input().split()) if n == 0 and m == 0: break n_number = [int(input()) for _ in range(n)] m_number = [int(input()) for _ in range(m)] cd = 0 for i in range(m): start, end = 0, n-1 while start m_number[i]: end = mid - 1 ..

✏️ 문제문제 파악  알고리즘이분 탐색매개 변수 탐색  코드import sysinput = sys.stdin.readlinen, k = map(int, input().split())kettles = [int(input()) for _ in range(n)]start, end = 0, max(kettles)while start

✏️ 문제문제 파악  알고리즘이분 탐색  코드n, l, w, h = map(int, input().split())start, end = 0, max(l, w, h)for i in range(100): mid = (start + end) / 2 if (l // mid) * (w // mid) * (h // mid) >= n: start = mid else: end = midprint(start)