본문 바로가기

전체 글

 (131)
[BOJ] 거스름돈_5585 이 문제는 아주 쉬운 문제이다. 하지만 내 코드가 비효율적이여서 효율적인 코드를 기억하고자 남긴다. 조건도 3개나 된다. 이 코드를 간단히 줄이면 이 코드가 된다. 원리를 설명하자면, 배열의 원소를 큰 것부터 순서대로 가져온다. 그 값으로 코인을 나눈 몫을 count에 더해준다. -> 이래야 해당 코인이 사용될 수 있는 총 갯수가 나오니까. 그리고 a%=i는 i로 나눈 나머지 값이 저장된다. -> 이 뜻은 i로 최대한 뺸 후 값을 저장한다는 의미가 된다. 이렇게 해서 아주 간단하게 구할 수 있다.
[BOJ] 나이트의 이동_7562 이 문제는 bfs를 이용하여 최단거리를 구하는 문제이다. 궁금증. 이 코드에 최단거리가 어떻게 고려되었는가? 1. 시작점으로부터 모든 방향으로 움직인다. 2. 이미 방문한 상태라면, 방문하지 않는다. 3. 이동한 칸에는 이동하기 전의 count+1을 한다. 왜 DFS는 안되는가?
[BOJ] 가장 큰 증가 부분 수열 이 문제는 이전에 풀었던 문제가 생각나서 바로 풀었다. 여기서 더 배울점은 바로 copy대신 다른 방법을 쓰는 것이다. data2 = [x for x in data1]으로 하면 copy와 같은 효과를 내지만 더 간결하다.
[BOJ] 제곱수의 합_1699 이 문제의 포인트는 다음과 같은 생각이다. 주어진 값 n의 가장 작은 수를 구하는 방법은, j를 1~n까지의 반복문 안에서 min을 활용해 j*j가 n보다 크지 않을 때까지 뺸 값에 +1 한 값이다. 즉, 다음과 같은 코드를 구성하게 된다. 근데,, 이걸 어떻게 생각해내지,,, 무튼 수를 더해 검사해나가며, dp[i]라는 한 자리에 그 값을 교체해주는 형식이된다.
[BOJ] 스티커_9465 이 문제는 그림과 같은 규칙을 찾아내, 점화식을 구한 후 푸는 DP문제이다. 해당 동그라미 표시의 값은 대각선의 값을 더하거나, 그 왼쪽의 값을 더하는 방법이 있다. 그 중 최대인 값을 구한다면, 그것이 최대로 가질 수 있는 값이 된다. 처음 실수가 나왔던 코드이다. 이 코드는 윗 칸부터 순차적으로 내려오게 했는데, 그렇게 되면 안되고 윗칸과 아래칸이 동시에 이루어져야 한다. 그래서 이러한 식이 나오게 된다.
[BOJ] 가장 긴 증가하는 부분 수열_11053 어떻게 풀었는가? 해당 문제의 포인트는 해당 지점을 j가 0~i까지 검사하는 것이다. 해당 코드와 같이 if data[j] < data[i]: 배열의 해당 값이 지금 검사하고 있는 값보다 작다면, 원래 가지고 있던 dp의 값과 더 작은 배열의 dp에+1한 값 중 더 큰 값을 대입한다. 왜 저렇게 풀어야 하는가? 문제의 접근방식은 dp[]를 만들고 해당 index값까지 배열이 있다고 가정했을 때, 해당 index까지의 가장 긴 수열 부분을 구하여 dp[index]값에 대입하는 방식이였다. 문제를 보았을 떄 dp로 풀어야 겠다는 감이 왔고, dp로 풀기 위해 작은 단위로 쪼개서 생각하였다. 왜 저 코드가 가능하지? 해당 index값까지 오면서 차례대로 값을 비교한 후, 현재의 값 보다 작다면 그 값은 증가 ..
[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,, 이 부분도 전혀 생각하지 못했다. 이 생각을 하기 어려웠던 이유는 당장 필요한 부분이기 보다 뒤에 상황까지 고려해준 부분이기 때문이다. 이 설명은 뒤에서 한번 더 하겠다..

티스토리툴바