profile
"신은 주사위 놀이를 하지 않는다."
post-thumbnail

[백준] 16236 - 아기 상어 (Python)

문제 링크 알고리즘 >* 그래프 탐색 너비 우선 탐색 아기 상어는 개인적으로 굉장히 재밌게 풀었다. 최근에 많이 풀었던 너비 우선 탐색 (BFS) 알고리즘을 다시 한 번 복습할 수 있는 기회였다. 처음에는 문제가 길고 규칙이 많아서 복잡하다고 느꼈었는데 하나하나 구현해가면서 해결할 수 있었다. 또 무작정 코드를 치는 것보다 먼저 어떻게 구현할지 정리하는게 훨씬 효율적이라는 것을 다시 한번 느낄 수 있었다. Tip > 다음 물고기까지의 최단거리를 구할 때의 시간복잡도를 최소로 하는 것이 중요 한 번의 Step에 무조건 1의 시간이 소요된다. 즉 가중치가 모두 1로 같은 그래프이므로 BFS를 사용하는 것이 효율적이다. ( BFS를 사용하면 방문하지 않은 곳만 방문할 수 있다 ) 풀이 코드가 많으므로 나눠서 정리했다. 전역 변수 세팅

2023년 3월 31일
·
0개의 댓글
·
post-thumbnail

[백준] 13549 - 숨바꼭질 3 (Python)

문제 링크 알고리즘 >* 그래프 탐색 BFS Tip > BFS, 큐를 활용한 풀이 파이썬의 내장 자료구조인 deque를 활용해서 순간이동 시 관리할 리스트의 크기를 시작과 목표지점의 차이의 2배로 설정 (곱하기 2 연산 때문) 풀이 관리할 리스트 (dp)를 생성 ( dp[n] 은 시작 지점에서 n까지의 최단 거리를 뜻함 ) 방문하지 않은 곳은 -1로 설정 시작 지점 dp[start] 을 0으로 설정 목표 지점 dp[finish] 초기값을 abs(start - finish) -> start와 finish의 차이로 설정 큐에서 하나씩 빼고 탐색을 실시한다. 큐에서 뺀 숫자 n의 다음 스텝이 finish보다 클 경우 아래로 한칸 내려오는 알고리즘을 수행하고 n의 다음 스텝이 finich보다 작을 경우 한칸 올라가는 알

2023년 3월 27일
·
0개의 댓글
·
post-thumbnail

[백준] 1697 - 숨바꼭질 (Python)

문제 링크 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 알고리즘 >* 그래프 이론 그래프 탐색 너비 우선 탐색(bfs) 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는

2022년 3월 27일
·
0개의 댓글
·