공부 기록

✏️ 문제 문제 파악조건이 3가지가 있는데 축약해보면 n번 집은 n-1의 집과 색만 같지 않으면 된다. n-1의 집과 n+1의 집의 색은 같아도 상관없다.이전 집의 색만 겹치지 않는 걸 조건으로 문제를 풀이하면 다음과 같다.ary 배열은 하나의 집에 대한 색 비용을 각각 담은 배열이고 dp 배열은 하나의 집에 대한 최소 색 비용의 총 합을 담은 배열이다. 다음 집의 색은 현재 선택할 색의 비용과 다음 선택할 색의 비용의 합이 최소로 되는 것으로 선택해야 한다.이게 무슨 말이냐면 dp 배열의 2행 색을 선택할 때 최소 비용을 고르려고 한다면 1번째 집이 R을 선택했을 시 경우의 수는 2가지R-G : 26 + 60 = 86 R-B : 26 + 57 = 83G와 B 중에 최소인 B를 선택할 것이므로 R-B값을..

✏️ 문제 문제 파악직접 넣어보면 다음과 같이 나온다. ndp(n)개수1dp(1)12dp(2)23dp(3)44dp(4)75dp(5)13 위의 표를 보면dp(n)일 때, 개수 =  dp(n-1) + dp(n-2) + dp(n-3)라는 규칙이 있다는 것을 알 수 있다.이 점화식을 활용하여 코드를 짜면 쉽게 풀 수 있다!  알고리즘다이나믹 프로그래밍   코드t = int(input())dp = [0, 1, 2, 4]for i in range(4, 12): dp.append(dp[i-1] + dp[i-2] + dp[i-3]) for i in range(t): n = int(input()) print(dp[n])

✏️ 문제 문제 파악피보나치 수열은 f(n) = f(n-1) + f(n-2) 이다.이는 즉 f(n)의 f(0) 호출 횟수과 f(1) 호출 횟수는 f(n-1)의 f(0) 호출 횟수과 f(1) 호출 횟수 + f(n-2)의 f(0) 호출 횟수과 f(1) 호출 횟수 라는 것을 의미한다.  직접 값을 찾아보면 다음과 같이 나온다. nf(n)f(0) 호출 횟수f(1) 호출 횟수2f(2)113f(3)124f(4)235f(5)356f(6)58 위의 표를 보면f(n)일 때, f(0) 호출 횟수 =  f(n-1)의 f(0) 호출 횟수 + f(n-2)의 f(0) 호출 횟수 f(n)일 때, f(1) 호출 횟수 =  f(n-1)의 f(1) 호출 횟수 + f(n-2)의 f(1) 호출 횟수이전에 설명한 것과 같이 값이 잘나온다.이..

✏️ 문제  문제 파악인접리스트를 활용해 예제 1과 같은 경우 1과 연결된 2, 3를 배열[1]에 대입하고 2와 연결된 1, 3, 4, 5를 배열[2]를 넣으면서 풀면 된다.처음 찾는 1번을 기준으로 각 숫자의 거리를 visited의 배열에 담는다.그 후 배열의 메소드인 index(), max(), count()를 활용해서 결과를 출력한다. 알고리즘그래프 이론그래프 탐색너비 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinen, m = map(int, input().split())graph = [[] * (n+1) for _ in range(n+1)]visited = [0] * (n+1)d = 0for _ in range(..

✏️ 문제 문제 파악상하좌우로 인접한 흰색 격자들로 전달될 수 있으므로 다음과 같이 방향 배열을 구성했다.d = [(1, 0), (0, 1), (-1, 0), (0, -1)] 문제에서 전류가 섬유 물질의 가장 바깥쪽 흰색 격자들에만 공급된다고 했으므로 첫 째줄을 돌면서 첫 째줄의 흰색 격자들과 인접해 있는 격자들만 전류가 흐른 것으로 바뀌도록 코드를 짜면 된다.또한 나는 안쪽까지 침투된 건지 아닌 지에 대한 기준을 잘 이해 못했었는데 찾아보니 다들 맨 아래줄의 흰색 격자가 전류가 흘렀는 지 아닌 지를 구분하여 출력하는 것을 볼 수 있었다. 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequem, n = map(int, input().spli..

✏️ 문제  문제 파악처음에 DFS 함수를 얼마나..? 돌려야할 지 몰라서 해멨다... 그냥 각 위치에서 한번씩만 돌리면 되는 거 였삼.. 씁 그리고 첨에  for (배열명) in (변수)  를 사용해서 중복 방지를 하려고 했는데 set() 이라는 자동으로 중복은 저장이 안되는 아주 좋은 집합 자료형이 있다! (뒤늦게 기억난 건 비밀) 알고리즘그래프 이론그래프 탐색깊이 우선 탐색브루트포스 알고리즘  코드import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**6)graph = [list(map(int, input().split())) for _ in range(5)]d = [(1, 0), (0, 1), (0, -1), (-1, 0)]nums = se..

✏️ 문제  문제 파악한 방향으로 갈 수 있는 만큼 끝까지 갔다가 더 갈 곳이 없다면 이전 위치로 돌아가면서 한수의 집을 도착하는 모든 경로를 찾는 백트래킹을 사용하는 문제이다.백트래킹 문제는 BFS와 DFS 둘 다 사용해서 풀 수 있지만 특징상 DFS로 푸는 것이 편하다.한수는 상하좌우로 이동할 수 있으므로 방향 배열을 다음과 같이 정의했다.d = [(1, 0), (0, 1), (0, -1), (-1, 0)] 그리고 깊이 탐색을 하다가 더 갈 곳이 없다면 이전 위치로 돌아가면서 들렀던 위치에 대한 방문을 안했다고 수정해야 하는데 그 이유는 현재 경로와 다른 경로로도 탐색해야 하기 때문이다.visited[x][y] = 0 ! 문제에서 한수의 위치는 왼쪽 아래, 한수의 집 위치는 오른쪽 아래라고 했으므로 ..

✏️ 문제 문제 파악인접리스트를 사용하여 트리를 구성하면 되는 DFS 문제이다. 각각의 리프 노드에서 루트까지의 모든 이동 횟수를 계산하여 총 이동 횟수가 홀수면 성원이가 승리하고 짝수면 형석이가 승리한다. 이때 리프 노드에서 루트까지의 이동 횟수는 노드의 깊이와 같으므로 이를 저장할 depth 배열이 따로 필요하다.  알고리즘그래프 이론그래프 탐색깊이 우선 탐색트리  코드import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**5)n = int(input())graph = [[] for _ in range(n+1)]visited = [0] * (n+1)depth = [0] * (n+1)ans = 0for _ in range(n-1): u, v = ..

✏️ 문제 문제 파악24444번 알고리즘 수업 - 너비 우선 탐색1 이 문제와 매우 유사너비 우선 탐색으로 푸는 문제를 깊이 우선 탐색으로 똑같이 푸는 느낌이다! 참고로 알고리즘 수업 - 깊이 우선 탐색2 는 그냥 정렬하는 부분을 내림차순 정렬로 수정해주면 똑같이 쉽게 풀어진다~! 알고리즘그래프 이론그래프 탐색깊이 우선 탐색정렬  코드import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**6)n, m, r = map(int, input().split())graph = [[] for _ in range(n+1)]visited = [0] * (n+1)order = 1for _ in range(m): u, v = map(int, input().spl..

✏️ 문제 문제 파악현재 위치 v 에서 앞으로 graph[v] 만큼 떨어진 위치로 점프 가능한 모든 위치를 계산한다.v + graph[v] 에서 시작해서 n 까지 graph[v] 씩 증가하면 가능한 점프 위치를 next_v 에 대입하도록 코드를 짜면 다음과 같다.for next_v in range(v + graph[v], n, graph[v]): 그리고 현재 위치 v 에서 뒤쪽으로 graph[v] 만큼 떨어진 위치로 점프 가능한 모든 위치를 계산한다. v - graph[v] 에서 시작해 0 까지 graph[v] 씩 감소하며 가능한 점프 위치를 next_v 에 대입하도록 코드를 짜면 다음과 같다.for next_v in range(v - graph[v], 0, -graph[v]):   알고리즘그래프 이론그..