공부 기록

✏️ 문제  문제 파악한 방향으로 갈 수 있는 만큼 끝까지 갔다가 더 갈 곳이 없다면 이전 위치로 돌아가면서 한수의 집을 도착하는 모든 경로를 찾는 백트래킹을 사용하는 문제이다.백트래킹 문제는 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]):   알고리즘그래프 이론그..

✏️ 문제 문제 파악다른 문제들과 달리 이 문제에서는 문자로 값을 주어 해당 문자에 해당하는 유니코드 정수를 반환하는 ord() 메소드를 사용해야 한다.또한 a와 b의 값만 분리하기 위해 입력을 받을 때 split() 옵션을 잘 활용해야 한다.  소문자 a 를 아스키코드 값으로 하면 97이므로 a를 0으로 기준을 잡으려면 -97 하면 된다.u, v = map(str, input().split(' is '))u = ord(u) - 97v = ord(v) - 97graph[u].append(v) 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색최단 경로플로이드-워셜  코드from collections import dequen = int(input())graph = [[] * 28 for _ in r..

✏️ 문제 문제 파악예제의 값은 잘 나왔지만 제출했을 때 시간 초과가 계속 떠서 시간을 많이 잡아먹었었는데 찾아보니 다들 똑같은 이유로 python3 대신 pypy3 로 제출하고 있었다.. python3 로 맞힌 사람은 딱 한 사람뿐... (멋있다..) pypy3 로 제출했더니 틀렸다고 나왔는데 3, 4, 5를 만났을 때 return 하도록 하는 if 조건문의 위치를 잘못두고 있었다...! 알고리즘그래프 이론그래프 탐색너비 우선 탐색  코드import sysfrom collections import dequeinput = sys.stdin.readlineq = deque()n, m = map(int, input().split())graph = [list(map(int, list(str(input().rs..

✏️ 문제 문제 파악최소 연산 횟수를 구하므로 BFS를 사용해서 풀어야 한다. 문제에서 연산 종류가 2가지 있다.a + 1a * 2이를 바탕으로 다음과 같이 코드를 짜면 next_v에 v + 1, v * 2 가 차례대로 들어가게 된다.for next_v in (v+1, 2*v): 제출했는데 IndexError가 계속 떠서 애초에 if 조건문에 next_v   알고리즘그래프 이론그래프 탐색너비 우선 탐색다이나믹 프로그래밍  코드from collections import dequeimport sysinput = sys.stdin.readlinea, k = map(int, input().split())graph = [0] * (k + 1)def bfs(v): q = deque([v]) graph[v] ..

✏️ 문제 문제 파악최소 치환 횟수를 구하므로 BFS를 사용해서 풀어야 한다.인접리스트를 활용해서 풀어야 하는 문제라 다음과 같이 입력을 처리하였다.for _ in range(m): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u) 그 후엔 graph를 돌며 visited 배열에 치환 횟수를 저장하며 풀었다. 예제들은 잘 출력되는데 자꾸 틀렸다고 나오길래 찾아보니 a와 b가 같은 문자라면 치환 횟수가 0이므로 0을 출력해야 한다는 것을 빼먹고 있었다.. 예제는 잘 풀리는데 퍼센트 높을 때 틀리는 사람은 a와 b가 같은 문자였을 때를 처리했는 지 확인해 보는 것을 추천! 알고리즘그래프 이론그래프 탐색너비 우선 탐색  코드..

✏️ 문제 문제 파악16173번 점프왕 쩰리 (Small) 와 비슷한 문제이다. 하지만 메모리가 매우 작습니다...... (메모리 초과 3번이나 떴다ㅠ) 메모리 초과를 해결한 방법은 다음과 같다.visited 배열을 없애고 graph 배열로만 방문했는 지 구분했다.이미 방문했던 위치는 또 돌 필요가 없으므로 바로 continue를 통해 메모리를 절약하도록 했다.if graph[x][y] == 0: # 이미 방문했던 위치 continue덱에 값을 새로 넣은 후에 방문 표시를 하는 보통의 경우와 달리 덱의 값을 꺼내는 즉시 바로 방문 표시를 하였다.x, y = q.popleft()graph[x][y] = 0 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections im..

✏️ 문제 문제 파악graph 2차원 배열에 1을 양, 2를 늑대로 표시했다.1 → 양2 → 늑대그리고 visited 2차원 배열의 값을 세 가지로 나눠서 대입하고 이를 이용해 조건문을 구분하였다.0 → 방문 안한 필드1 → 방문한 필드-1 → 울타리 부분으로 방문하면 안되는 필드또한 이 문제의 경우 가로, 세로로 연결되어 있는 필드는 같은 영역이므로 방향 배열을 다음과 같이 구성했다.d = [(1, 0), (0, 1), (-1, 0), (0, -1)] BFS를 돈 후에 배열을 return 했는데 인덱스 0에는 양의 수, 인덱스 1에는 늑대의 수로 하였다.그리고 return 된 값에서 if 문을 돌아양의 수가 많으면 늑대를 우리에서 쫓아내므로 늑대의 수가 0이라 인덱스 1을 0으로 바꾸고 출력할 nu..