[백준] 2749번 - 피보나치 수 3 (한줄평) 메모리 초과를 해결하지 못해 다른 사람의 풀이를 참고한 문제! 아예 생각조차 하지 못한 방식으로 해결이 가능하다... 답을 안봤으면 절대 못풀었을 문제^^; 유사 문제: 2747, 2748 https://hseungyeon.tistory.com/294 [다이나믹 프로그래밍] 2747번 - 피보나치 수, 2748번 - 피보나치 수 2 [백준] 2747번 - 피보나치 수, 2748번 - 피보나치 수 2 (한줄평) 다이나믹 프로그래밍으로 해결할 수 있었던 문제! 2가지 문제는 n번째 피보나치수를 구하는 문제로 두 문제의 차이는 n의 범위다 hseungyeon.tistory.com 이 문제는 n이 1,000,000,000,000,000,000이하의 자연수 일 때..
[백준] 9184번 - 신나는 함수 실행 (한줄평) 재귀함수 그대로 구현하면 되지만 오류를 스스로 해결하지 못했던 문제..! 꼭 복습이 필요하다~ 풀이 시간: 60분 이내 1) 문제 해결 아이디어 이 문제는 a, b, c가 주어졌을 때 w(a, b, c)를 구하는 문제다. 이 문제는 아래의 재귀함수 그대로 구현을 하면 되지만 이렇게만 구현하게 되면 동일한 작업을 계속 반복하게 되어 그 값을 구하는데 매우 오랜 시간이 걸리게 되는 문제가 발생한다. 그래서 다이나믹 프로그래밍으로 해결해야하는데 다이나믹 프로그래밍의 핵심은 반복되는 계산을 피하기 위해서 dp테이블에 계산한 값을 저장해두고 나중에 그 값이 필요하다면 바로 그 값을 가져다 쓰는 것이다. if a 20, then w(a, b, c) returns:..
[백준] 2573번 - 빙산 풀이 시간: 90분 이내 1) 문제 해결 아이디어 일반적인 BFS문제와는 약간 다른 부분이 있었기 때문에 초반에 BFS로 푸는 것이 과연 효율적인가? 맞나? 싶었던 문제였다. 결국 혼자서 푸는데 성공하긴 했지만 추후 복습이 필요한 문제! 보통의 문제들은 입력받은 정보(graph), 방문여부체크(visited) 2개면 풀이가 가능하지만 이 문제의 경우에는 빙산 녹이기를 한 결과(result)가 추가적으로 필요하다. Q. 빙산 녹이기를 한 결과(result)를 사용해야하는 이유는? 빙산 녹이기를 한 칸의 결과값은 (기존값 - 상하좌우의 바다(0) 개수) 이다. 여기서 중요한 점은 빙산 한 칸을 녹이기를 한 결과를 바로 graph에 반영해버리면 다음 빙산인 칸이 그 칸과 인접한 칸..
[백준] 16930번 - 달리기 풀이 시간: 3시간 이내 아이디어를 떠올리고 코드를 짜는데는 30분 밖에 안걸렸지만 시간 초과를 고치는데 시간이 좀 걸린 문제다. 지금까지 내가 겪었던 시간 초과 문제들에서 보통은 몇가지 방법들을 쓰면 해결이 되었는데 이 문제는 설계를 꼼꼼하게 하지 못해 일어난 시간초과 문제로 해결하기가 힘들었다. 꼭 복습이 필요한 문제!! 매 초마다 상하좌우 중 1가지 방향으로 이동할 수 있고 최소 1개~최대 K개의 빈칸을 이동할 수 있다. 시작점에서 도착점까지 이동하는 최소 시간을 구하는 문제로 BFS로 풀 수 있는 문제이다. 일반적인 BFS 문제는 상하좌우로 한 칸씩만 이동할 수 있으나 이 문제는 상하좌우로 (1~K)칸의 연속된 빈칸을 이동할 수 있다는 것이 중요 포인트다. (풀이1..
