viamemine

문제: https://www.acmicpc.net/problem/1463  풀이  dp는 점화식을 찾는 것이 문제 풀이의 핵심입니다. -1, /2, /3의 방법으로 점화식을 찾으려고 노력했는데요. 예를 들어, 그림과 같이 6을 구하는 횟수를 구할 때,1만큼 작은 5보다는 1회 증가하고 (+1하면 되니까)2로 나눈 3보다도 1회 (*3 하면 되니까),3으로 나눈 2보다도 1회(*2 하면 되니까) 증가합니다. 이렇게 점화식을 찾았으며, 코드로 구현하면 다음과 같습니다.   x = int(input())dp = [0] * (x+1) # 계산된 결과를 저장하기 위한 DP 테이블 초기화for i in range(2, x+1): # 보텀업 dp[i] = dp[i-1] + 1 # 현재의 수에서 1을 빼는 경우 ..

문제: https://www.acmicpc.net/problem/17626  풀이 이번 문제는 제곱수의 합을 구하는 문제입니다.dp로 해결했는데, 점화식을 찾는 것이 쉽지 않았습니다.   이해를 위해 그림을 첨부했습니다. i를 가지고 j를 만든다고 할 때, 그림처럼 항의 개수를 가지게 됩니다. 이는 제곱수일 때 +1만큼 커지게 됩니다. (그림을 보고 이해하시면 되겠습니다 !) 브루트포스로도 문제를 해결할 수 있습니다.주석과 함께 코드를 첨부해두겠습니다.   - DP 문제 풀이N = int(input())dp = [n for n in range(N+1)]for i in range(2, int(N**0.5)+1): for j in range(i*i, N+1): dp[j] = min(dp[j..

문제: https://www.acmicpc.net/problem/5618 풀이이번 문제는 공약수를 구하는 문제입니다. 난이도는 브론즈라 어렵지 않았는데, 포스팅까지 하는 이유는 '시간 초과' 때문입니다. 저도 쉽게 코드를 작성했는데 바로 시간 초과가 나더라구요 ㅠ. ㅠ  문제점이 무엇인지 파악해보도록 합시다 !  공약수는 숫자 n개가 공통적으로 나눠지는 수를 의미하기 때문에저는 직관적으로 1부터 작은 수 까지의 범위를 돌고 나눠지는 수를 구하는 방식으로 풀었습니다.  해당 문제는 숫자 두 개 혹은 세 개의 공약수를 찾는 문제였기 때문입니다. 문제의 제한 시간은 1초 였는데요.작은 수가 최대 10의 8제곱(1억) 까지 갈 수 있기 때문에 1초에 2000만번의 연산을 하는 파이썬으로는 시간 초과가 나는 것입..

문제: https://www.acmicpc.net/problem/1913  해당 문제를 풀이할 때 아래 링크의 유투브 강의를 참고했습니다.큰 도움이 되므로 시청을 왕 - 추천합니다 !  https://www.youtube.com/watch?v=rw2gQg9x_EA  문제 풀이 방법은 두 가지 방식이 있습니다.1. 1부터 채우기2. 49(n*n)부터 채우기 저는 2번 방법으로 문제를 해결했습니다.  풀이풀이 방법을 안다면 코드 구현은 그렇게 어렵지 않습니다.     하지만 자꾸만 시작 지점(arr[0][0])에서 오류가 났는데요. 이는 while문 안의 ni  = i + di[dr], nj = j + dj[dr]에서arr[0][0]을 채우기도 전에 좌표를 dr만큼 이동시키기 때문입니다.  따라서 저는 ar..

문제: https://www.acmicpc.net/problem/1244 풀이 이번 문제는 남자인 경우는 쉽게 풀렸지만,여자인 경우에서 자꾸 에러가 났습니다.  이는 남자일 때는 해당 숫자의 배수를 뒤집으면 되는 문제이지만 (for문의 step을 num만큼)여자일 때는 대칭인 경우와 비대칭인 경우를 고려해주어야 하기 때문입니다. 일단 문제는 인덱스가 1부터 시작하는데, 배열은 인덱스가 0부터 시작하기 때문에 가장 앞에 [-1]을 추가해서 인덱스를 맞춰주었습니다. 핵심은 여자인 경우의 대칭과 비대칭일 때의 코드를 작성하는 것입니다. 나는 처음에 cnt를 +1해주는 방식으로i = i+2*cnt일 때와 i != i+2*cnt (일치/불일치)로 코드를 짰습니다. 그러나 index error 발생으로 코드를 리팩..