[백준 파이썬] 16236 아기 상어

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제  공간과 아기상어, 먹이가 주어질 때 아기상어가 물고기를 잡아먹을 수 있는 최단시간을 구하는 문제이다. 풀이 먼저 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러간다. 라는 조건이 있다. 따라서 BFS를 사용하는데 이는 BFS가 최단경로를 가지기 때문이다. 이를 해결하기 위해 다음과 같은 순서를 사용하였다. 1. BFS를 사용하여 현재 위치에서 각 위치..

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

[백준 파이썬] 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