[백준 파이썬] 1987 알파벳

1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 문제  현재 까지 이동한 위치와 다른 알파벳이 그려진 좌표로만 이동할 수 있을 때 가장 멀리 이동하는 거리를 구하는 문제이다. 풀이 기본적인 개념은 가장 멀리 떨어진 좌표까지 이동해야 하는 문제이므로 DFS를 사용하였다. 이 때 현재 까지 이동한 알파벳과 다른 알파벳이어야만 이동이 가능하므로 SET자료형을 사용하여 알파벳을 검사해주었다. visited = set(graph[0][0]) 가장 먼저 0, 0일 때의 알파벳을 visited에 추가시켜준다..

• format_list_bulleted 알고리즘
• · 2024. 2. 15.
• textsms

[백준 파이썬] 14938 서강그라운드

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 문제   그래프가 주어지고 수색범위 내부에서 수색했을 때 가장 아이템을 많이 주울 수 있는 경우의 수를 구하는 문제이다. 풀이 그래프간의 최단경로를 구하는 문제이므로 다익스트라 알고리즘을 사용하였다. def dijkstra(start): q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heapq.heappop..

• format_list_bulleted 알고리즘
• · 2024. 2. 12.
• textsms

[백준 파이썬] 17070파이프 옮기기 1

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제  파이프를 옮긴 후 적절하게 회전시켜 마지막 좌표로 이동시키는 경우의 수를 구하는 문제이다. 풀이 파이프를 이동시켜 지정한 위치까지 옮겨야한다. 이 때 파이프는 45도까지 회전시킬 수 있는데 중요한 점은 이동 후 회전시킬 수 있다는 점이다. 따라서 같은자리에서 회전은 불가능하고 현재 파이프가 놓여있는 방향으로 한칸 이동 후 회전시켜야 한다. 파이프가 이동할 수 있는..

• format_list_bulleted 알고리즘
• · 2024. 2. 10.
• textsms

[백준 파이썬] 11054 가장 긴 바이토닉 부분 수열

11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제  주어진 수열의 부분 수열 중 가장 긴 바이토닉 수열의 길이를 구하는 문제이다. 풀이 기본적인 풀이방법은 11053번 "가장 긴 증가하는 부분수열" 문제와 아주 유사하다. 먼저 가장 긴 증가하는 부분수열의 알고리즘인 LIS 알고리즘에 따라 기존 수열의 LIS값을 DP1 배열에 저장한다. for i in range(N): for j in range(i): if S[i] > S[j]: dp1[i] = max(dp1[i], dp1[j] + 1) 이렇게 하면 예제의 수열이 다음과 같..

• format_list_bulleted 알고리즘
• · 2024. 2. 7.
• textsms

[백준 파이썬] 2467 용액

https://www.acmicpc.net/problem/2467 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제  주어진 2차원 배열에서 내리막으로만 갈 수 있는 길의 경우의 수를 계산하는 문제이다. 풀이 용액을 비교해가며 풀어야하는 문제이므로 이분탐색을 이용하였다. 먼저 가장 왼쪽값을 0부터 N-1 까지 순회하며 바꿔주는데 이 과정에서 이분탐색을 적용해줬다. if abs(tmp) < ans: lAns = i rAns = mid ans = abs(tmp) 왼쪽값과 중앙값을 더한 값의 절대값이 현재 정답값..

• format_list_bulleted 알고리즘
• · 2024. 2. 3.
• textsms

[백준 파이썬] 1520 내리막 길

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 문제  주어진 2차원 배열에서 내리막으로만 갈 수 있는 길의 경우의 수를 계산하는 문제이다. 풀이 가장 먼저 떠오른 방법은 DFS를 이용하여 경로를 찾는 것이었다. 하지만 DFS를 단독으로 사용하면 수많은 경로를 모두 탐색해야 하기 때문에 시간초과가 발생한다. 따라서 DP와 DFS를 같이 사용해야한다. graph = [list(map(int, input().split())) for _ in r..

• format_list_bulleted 알고리즘
• · 2024. 2. 1.
• textsms