공부 기록

✏️ 문제  문제 파악인접리스트를 활용해 예제 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..

✏️ 문제 문제 파악현재 위치 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..

✏️ 문제 문제 파악최댓값을 출력하므로 BFS를 활용하여 풀었다. 아기 상어의 위치에서 공간 내 거리가 각각 얼마나 걸리는 지 safety 배열에 담았다.그리고 A 아기 상어에서 멀어도 B 아기 상어에서의 거리가 더 가까우면 그 거리를 대입해야 하므로 min을 사용하여 safety 배열에 담았다.  safety 이차원 배열에서 max 값을 구해야 하므로 max(safety) 쓰면 값이 안나온다! 주의하자! 알고리즘그래프 이론그래프 탐색너비 우선 탐색브루트포스 알고리즘  코드from collections import dequeimport sysinput = sys.stdin.readlinen, m = map(int, input().split())graph = [[0] * (m) for _ in range(..