공부 기록

✏️ 문제 문제 파악상하좌우로 인접한 흰색 격자들로 전달될 수 있으므로 다음과 같이 방향 배열을 구성했다.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..

✏️ 문제 문제 파악다른 문제들과 달리 이 문제에서는 문자로 값을 주어 해당 문자에 해당하는 유니코드 정수를 반환하는 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..

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

✏️ 문제 문제 파악예전 트리 부모 찾기  문제랑 비슷한 맥락이다.인접리스트를 사용해서 풀었고 BFS를 활용했다.  개수가 아닌 순서이므로 들렸으면 +1 씩 해줘야 한다. 그래서 인접리스트의 한 배열을 방문한 후에 순서를 +1 하도록 코드를 짰다.그리고 문제에서 내림차순으로 방문한다고 했으므로 인접리스트의 한 배열을 방문하기 전에 인접리스트를 내림차순하고 돌아가도록 코드를 구성했다. 알고리즘그래프 이론그래프 탐색너비 우선 탐색정렬  코드from collections import dequeimport sysinput = sys.stdin.readlinen, m, r = map(int, input().split())graph = [[] * (n+1) for _ in range(n+1)]visited = [0..

✏️ 문제 문제 파악상하좌우 4가지가 붙어있으면 하나의 무리가 되므로 다음과 같이 방향 배열을 구성했다.d = [(1, 0), (0, 1), (-1, 0), (0, -1)] 무리의 개수를 구하는 것이므로 BFS가 한 무리를 돌 때마다 +1 하면 무리의 개수가 나온다. 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinefor _ in range(int(input())): h, w = map(int, input().split()) graph = [[0] * w for _ in range(h)] visited = [[0] * w for _ in range(h)] d = [(..

✏️ 문제 문제 파악문제를 읽어봤을 때 방향이 정해졌을 시 그 방향으로 칸에 적혀있는 수만큼 움직일 수 있는 것 같았다. 그래서 다음과 같이 코드를 짰다.다음 x위치 = 현재 x위치 + (움직일 방향 * 현재 밟고 있는 칸에 쓰여 있는 수)다음 y위치 = 현재 y위치 + (움직일 방향 * 현재 밟고 있는 칸에 쓰여 있는 수)  다음 x, y 위치가 -1일 경우 1을 리턴하고 끝까지 만나지 못할 경우 0을 리턴하여 이 리턴값을 기준으로 출력하는 문자열을 달리하였다. 알고리즘구현브루트포스 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinen = int(input())graph =..