공부 기록

✏️ 문제   문제 파악입력으로 주어진 값을 잘 구분해야 한다.X → 벽이므로 아예 방문을 자체를 안해도 됨I → 도연이의 위치로, 즉 탐색의 초기 위치 값P → 사람이 있는 위치로 이 위치에 해당될 때만 카운트  또한 이 문제의 경우 가로, 세로로 이동해서 방문할 수 있으니 방향 배열을 다음과 같이 구성했다.d = [(-1, 0), (1, 0), (0, -1), (0, 1)]   알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinen, m = map(int, input().split())graph = [[0] * m for _ in range(n)]visited = [[0..

✏️ 문제   문제 파악처음에는 위의 사진과 같이 해당 범위 내에 있는 값 중 제일 큰 값과 그 값의 인덱스 값을 받아와 제일 큰 값이 있는 인덱스로 점프하는 방향으로 코드를 짰다. 점프한 인덱스의 visited 배열에 1을 넣어 최종적으로 sum(visited)을 출력하는 코드를 짰는데 자꾸 값이 몇 개는 맞으면 몇 개는 1씩 차이가 났었다.  반례 모음 72 3 1 2 6 4 7# 3101 2 0 1 3 2 1 5 4 2# 520 0# -132 5 0# 11021 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ..

✏️ 문제 문제 파악입력으로 주어진 배열을 두 가지로 병사를 나눴다. 1 → 'W'가 입력으로 들어온 위치, 즉 우리팀 병사2 → 'B'가 입력으로 들어온 위치, 즉 상대팀 병사병사를 구분하여 병사의 수를 세야하므로 카운트할 때 다음 위치에 있는 병사가 현재 병사와 같은 팀이라는 조건이 붙어야 한다. 또한 이 문제의 경우 가로, 세로로 이동해서 방문할 수 있으니 방향 배열을 다음과 같이 구성했다.d = [(-1, 0), (1, 0), (0, -1), (0, 1)]   알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinem, n = map(int, input().split())..

✏️ 문제 문제 파악visited 2차원 배열의 값을 세 가지로 나눠서 구분했다.0 → 그림이 있으나 방문하지 않은 위치1 → 그림이 있고 방문한 위치-1 → 그림이 없어 방문할 필요 없는 위치또한 이 문제의 경우 가로, 세로로 이동해서 방문할 수 있으니 방향 배열을 다음과 같이 구성했다.d = [(-1, 0), (1, 0), (0, -1), (0, 1)] 마지막 쯤에 ValueError 뜨는 경우 그림이 하나도 없는 경우에 0이 출력되는 지 확인해보길..! 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드n, m = map(int, input().split())graph = [[0] * m for _ in range(n)]visited = [[0] * m for _ in range(..

✏️ 문제 문제 파악짧은 거리를 출력해야 하므로 BFS를 사용해서 풀었다. visited 배열을 도달할 수 있는 거리를 저장하는 배열로 설정해서 출발지점이 거리가 0이므로 이걸 기준으로 나머지 거리를 구했다. 이때 입력으로 주어진 0은 갈 수 없는 땅이므로 초기에는 갈 수 없는 땅임을 구분하기 위해 visited 배열에서 -1로 주었다.그리고 원래 갈 수 있지만 도달할 수 없는 땅은 BFS가 실행된 후에도 visited 배열의 값이 0(방문 X)이고 입력으로 주어진 값은 1인 땅이므로 이를 -1로 출력하도록 조건문을 처리했다. 다음과 같다.if 갈 수 없는 땅이면: visited[갈 수 없는 땅] = -1def bfs: ... if 이동한 땅이 방문하지 않았다면: visited[이동한..

✏️ 문제 문제 파악시간 제한이 5초로 시간 초과가 뜨지 않도록 하는 게 이 문제의 핵심이다.. 메모리도.. (둘 다 초과 떠본 사람이) 아마 이 두 개의 제한이 정답 비율을 낮게 만든 요인일 듯..  인접리스트랑 BFS를 활용해서 풀었는데 각 컴퓨터의 해킹할 수 있는 컴퓨터의 개수를 저장해야 하므로 컴퓨터 하나하나를 BFS를 돌아야 한다. 그래서 각각의 컴퓨터가 BFS 돌 때 방문 처리를 해줘야 하므로 방문 배열을 BFS 함수 내에서 초기화해야 한다. python으로 풀고 싶어서 오래 붙잡아봤지만 결국 못풀었다 ㅠ pypy3로 제출하니까 되긴 됐는데 다른 분들의 많은 코드를 봤지만 대부분 pypy3로 푸는 듯.. python으로 푼 사람이 있을까.. !! 궁금하다 그 코드! 알고리즘그래프 이론그래프 탐..

✏️ 문제 문제 파악입력값은 점을 기준으로 주니까 배열로 구현하려 할 때 조금 헷갈렸다. 그래서 아래와 같이 그림 그리니 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값은 그대로, 오른쪽 위 꼭짓점의 x, y좌표값은 -1씩하면 됐었다. 직사각형이 있는 영역은 방문하면 안되는 영역이므로 -1로 표시했다. 아 그리고 이 문제는 DFS로 풀었을 때 재귀를 사용하면 RecursionError가 발생하므로 나는 재귀 대신 스택을 사용해서 풀었다. 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드import sysinput = sys.stdin.readlinem, n, k = map(int, input().split())graph = [[0] * n for __ in range(m)]visited = ..

✏️ 문제 문제 파악최소 이동 거리를 구하므로 BFS를 사용해야 한다.또한 나이트는 8가지 방법으로 움직일 수 있으므로 다음과 같이 방향 배열을 구성했다.d = [(-2, -1), (2, -1), (-2, 1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)] x, y 좌표를 deque에 넣을 땐 "q = deque([(x, y)])" 라는 걸 알고 있자! 알고리즘그래프 이론그래프 탐색너비 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinefor _ in range(int(input())): l = int(input()) visited = [[0] * l for __ in range(l)..

✏️ 문제 문제 파악연산의 최솟값을 구해야 하므로 BFS를 사용해서 풀어야한다.이 문제에서 배열로 풀게 되면 A와 B의 범위가 매우 커서 배열 초기화시 메모리 초과가 뜨게 된다.그래서 배열 대신 딕셔너리 { } 를 사용하면 필요한 노드에 대해서만 메모리를 할당하여 메모리 사용량을 줄일 수 있다! 알고리즘그래프 이론그래프 탐색너비 우선 탐색그리디 알고리즘  코드from collections import dequea, b = map(int, input().split())graph = {}def bfs(v): q = deque([v]) graph[v] = 0 while q: node = q.popleft() if node == b: retur..

✏️ 문제 문제 파악같은 알고리즘의 문제 중 11725번 트리의 부모 출력 문제가 생각난 .. 매우 비슷함인접리스트를 활용하면 쉽게 풀 수 있다! 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinen = int(input())a, b = map(int, input().split())graph = [[] for _ in range(n+1)]visited = [0] * (n+1) for _ in range(int(input())): x, y = map(int, input().split()) graph[x].append(y) graph[y].append(x)def bfs(v)..