전체 글 200

[Python] 15723번 n단 논법

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

PS/백준 2024.08.30

[Python] 17129번 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

✏️ 문제 문제 파악예제의 값은 잘 나왔지만 제출했을 때 시간 초과가 계속 떠서 시간을 많이 잡아먹었었는데 찾아보니 다들 똑같은 이유로 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..

PS/백준 2024.08.30

[Python] 25418번 정수 a를 k로 만들기

✏️ 문제 문제 파악최소 연산 횟수를 구하므로 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] ..

PS/백준 2024.08.29

[Python] 14496번 그대, 그머가 되어

✏️ 문제 문제 파악최소 치환 횟수를 구하므로 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가 같은 문자였을 때를 처리했는 지 확인해 보는 것을 추천! 알고리즘그래프 이론그래프 탐색너비 우선 탐색  코드..

PS/백준 2024.08.29

[Python] 16174번 점프왕 쩰리 (Large)

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

PS/백준 2024.08.29

[Python] 3184번 양

✏️ 문제 문제 파악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..

PS/백준 2024.08.28

[Python] 17086번 아기 상어 2

✏️ 문제 문제 파악최댓값을 출력하므로 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(..

PS/백준 2024.08.28

[Python] 16948번 데스 나이트

✏️ 문제 문제 파악7562번 나이트의 이동 의 업그레이드 버전인 듯? 똑같이 풀면 쉽게 답이 나온다! 알고리즘그래프 이론그래프 탐색너비 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinen = int(input())graph = [[0] * (n) for _ in range(n)]visited = [[0] * (n) for _ in range(n)] d = [(-2, -1), (-2, 1), (0, -2), (0, 2), (2, -1), (2, 1)]start_x, start_y, end_x, end_y = map(int, input().split())def bfs(x, y): q = deque([(x, y)]) vi..

PS/백준 2024.08.28

[Python] 24445번 알고리즘 수업 - 너비 우선 탐색 2

✏️ 문제 문제 파악예전 트리 부모 찾기  문제랑 비슷한 맥락이다.인접리스트를 사용해서 풀었고 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..

PS/백준 2024.08.27

[Python] 11123번 양 한마리... 양 두마리...

✏️ 문제 문제 파악상하좌우 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 = [(..

PS/백준 2024.08.27