본문 바로가기

개발/알고리즘

 (64)
[BOJ] 나이트의 이동_7562 이 문제는 bfs를 이용하여 최단거리를 구하는 문제이다. 궁금증. 이 코드에 최단거리가 어떻게 고려되었는가? 1. 시작점으로부터 모든 방향으로 움직인다. 2. 이미 방문한 상태라면, 방문하지 않는다. 3. 이동한 칸에는 이동하기 전의 count+1을 한다. 왜 DFS는 안되는가?
[BOJ] 제곱수의 합_1699 이 문제의 포인트는 다음과 같은 생각이다. 주어진 값 n의 가장 작은 수를 구하는 방법은, j를 1~n까지의 반복문 안에서 min을 활용해 j*j가 n보다 크지 않을 때까지 뺸 값에 +1 한 값이다. 즉, 다음과 같은 코드를 구성하게 된다. 근데,, 이걸 어떻게 생각해내지,,, 무튼 수를 더해 검사해나가며, dp[i]라는 한 자리에 그 값을 교체해주는 형식이된다.
[BOJ] 스티커_9465 이 문제는 그림과 같은 규칙을 찾아내, 점화식을 구한 후 푸는 DP문제이다. 해당 동그라미 표시의 값은 대각선의 값을 더하거나, 그 왼쪽의 값을 더하는 방법이 있다. 그 중 최대인 값을 구한다면, 그것이 최대로 가질 수 있는 값이 된다. 처음 실수가 나왔던 코드이다. 이 코드는 윗 칸부터 순차적으로 내려오게 했는데, 그렇게 되면 안되고 윗칸과 아래칸이 동시에 이루어져야 한다. 그래서 이러한 식이 나오게 된다.
[BOJ] 01타일_1904 이 문제의 유형은 타일과 같은 여러 문제들에서 비슷하게 응용된다. 이 문제의 핵심은 다음과 같다. 그림을 예로 보았을 때, dp[4]를 구하는 방법을 생각해보겠다. dp[2]는 타일이 두개일 때, 구할 수 있는 모든 경우의 수이다. 만약 여기에 00타일 두개가 들어가고, dp[3]에는 1타일 한개가 들어간다면 4개짜리의 모든 경우의 수가 나온다. 하지만 난 여기서 뭔가 거슬리는 생각들이 있었다. dp[2]에 00을 추가할 때, 순서를 바꿔준다면 다른 경우가 되지 않을까?? 그리고 두개를 추가한다고 했을 때, 00말고 11을 넣는다면,,? 물론 잘못된 생각이지만, 한번은 짚고 넘어가자. 저 생각은 왜 잘못된 것일까? 이 잘못된 생각의 흐름은 어디서 부터 시작된걸까? 일단 dp[2]의 11에 00을 앞뒤로 ..
[BOJ] 퇴사_14501 이 문제를 푸는데 정말 오래걸렸고, 끝내 풀지 못했다. 해당 문제는 https://suri78.tistory.com/178것을 보고 받아적고, 이해하기 위해 블로그 글로 남긴다. 우선 for i in range(n):을 통해 0~n-1까지 반복문을 실행한다. if i + data[i][0] > n: ->만약 해당 날짜가 n보다 작으면 실행한다. 우선 이부분도 쉽게 생각하지 못했다.. i는 해당 일수이고, data[i][0]을 통해 해당 날짜에서 그 날짜처리를 할 수 있는지 판별을 저 한 구문으로 하였다. 또한 charge[i] = 0,, 이 부분도 전혀 생각하지 못했다. 이 생각을 하기 어려웠던 이유는 당장 필요한 부분이기 보다 뒤에 상황까지 고려해준 부분이기 때문이다. 이 설명은 뒤에서 한번 더 하겠다..
[python] 문자열 다루기 보호되어 있는 글입니다.
[BOJ] 연속합_1912 이 문제는 쉽게 해결될 줄 알았는데 풀이를 보고도 어렵다고 느꼈다. 결론부터 보자면, dp.append(max(dp[i-1] + data[i], data[i])) 이 부분은 다시 봐도 정확히 이해가 되지 않는다. 저 한줄의 코드가 각 항 마다, 이전까지 더한 값이 더 크냐 or 현재 값이 더 크냐를 의미한다. 하지만 저것이 어떻게 모든 경우의 수를 고려해준 것일까?? dp[i] = max(dp[i-1]+data[i], data[i])에서 dp[i-1]은 이전까지 구한 값 중 최대의 값을 만들어낸 값이다. 그 전까지 더했을 때, 더 이득이 되는 것만 값을 더했기 때문이다. 그러한 값과 현재의 값을 더했을때와 더하지 않았을 떄의 값을 비교해서 최대값을 구하는 것이다.
[BOJ] 포도주 시식_2156 dp문제는 수능 수학에서 수열 문제와 비슷한 것 같다. 수능 수열 문제처럼 a1, a2..a4정도 까지 구해본 다음, 그 속에서 규칙을 찾아내 문제를 해결하는 것이다. 물론 그 규칙이 생기는 논리적인 이유를 통해 유추할 수 있지만, 처음 접근 방식을 수능 수열처럼 해보자. 그리고 배열에 값을 초기화할 때, 무조건 쓰던 방식만 생각하지 말고 그때그때 필요한 방식을 적용하자.

티스토리툴바