빠르고 꾸준하게

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 1405(파이썬) - 미친 로봇

https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 최근 푼 문제들 유형이 그래프가 많다 보니 이 문제도 보자마자 그래프로 풀어야겠다 싶었습니다. 하지만 문제에서는 좌표가 주어지지 않았는데요, 주어지지 않으면 만들어서 풀면 됩니다! 시작점을 중심으로 동, 서, 남, 북으로 움직여서 주어진 횟수를 모두 사용해서 도달한 곳이 자신이 한 번도 방문하지 않은 좌표일 때, 확률을 더해서 구해주면 됩니다. 처음에는 '로봇의 이동 경로가 단순할 확률을 출력..

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 2589(파이썬) - 보물섬

https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 이 문제를 처음읽고 든 생각은 bfs인데 어떻게 지점간의 거리를 구하고 그 거리가 최대일 때를 구해야할까? 였습니다. 조건이 보통은 1000, 1000을 주는데 50,50 으로 준 걸 보니 완전탐색을 이용해서 각 좌표마다 bfs를 실행해주면 되겠다 라는 생각을 했고, 문제를 풀었습니다. 이 문제에서 핵심은 cnt 를 다음 bfs 좌표로 넘어갈 때, +1 씩 해줘서 현재 지점에서 bfs를 마쳤을 때 가..

자료구조 & 알고리즘/백준(Baekjoon)

[백준]4811(파이썬) - 알약

https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 이 문제는 꽤나 까다로웠던 문제입니다. 이 문제를 빠른 시간 내에 풀 수 있다면 DP관련 문제들은 웬만한 건 해결할 수 있겠다는 생각이 들었죠.먼저 DP로 푸는 문제인 거 같다! 라는 생각을 했고 DP문제를 푸는 과정을 정리해봤습니다. DP는 이전 결과가 다음결과에 영향을 미쳐야 합니다. DP를 풀 때 변수를 어떻게 정할지가 중요합니다. 이전 결괏값을 가져다 쓰기 위해서는 초기화가 중요합니다. 위 세 가지 조건을..

자료구조 & 알고리즘/백준(Baekjoon)

[백준]5014(파이썬) - 스타트링크

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 이 문제는 보자마자 BFS로 풀어야겠다는 생각이 들었습니다. 또 생각이 들었던 점은 뱀과 주사위 게임과 거의 유사한 유형이라는 점입니다. 이 문제의 핵심은 BFS 떠올렸어? 그리고 UP, DOWN을 어떻게 표현할래?라고 생각합니다. 이 부분만 인지를 했으면 문제 푸는 데는 어렵지 않았습니다. 한 가지, result를 -1로 초기화하지 않고 0으로 초기화한 뒤, result [s-1] = 0을 제외시키면 31 ..