viamemine

문제: https://www.acmicpc.net/problem/2839 풀이 요즘 코딩테스트 준비로 인해, 여러 문제를 풀고 있는데요. 예전에 풀어봤던 DP 문제를 다시 풀어보게 되었습니다.그 때와는 또 다른 방식의 풀이를 생각해서기록해보려고 작성하게 되었습니다. 1년 전 쯤에 풀었던 코드는 부끄러울 정도로 지저분합니다 ...  그때 작성한 코드를 보니, 지금은 조금 성장한 모습이라 다행이라고 생각이 됩니다.  제가 푼 방법을 방법을 말씀드려보자면 !N을 5로 나눈 몫을, 큰 순서대로 구하고 (for문을 돌려서)사용한 봉지의 개수가 가장 작은 것부터 나오도록 계산했습니다.  5kg의 봉지를 많이 사용할수록 3kg의 봉지는 덜 사용하기 때문에5kg의 몫을 구할 수 있을 때 break를 걸었고,break ..

문제: https://www.acmicpc.net/problem/10870  풀이  이번 문제는 피보나치를 구하는 문제입니다. 피보나치는 f(n) = f(n-1) + f(n-2)의 점화식으로 구할 수 있는 쉬운 문제입니다. 문제는 크게 두 가지의 방법으로 해결할 수 있습니다.1. 재귀 2. for loop 저는 재귀 중 memoization 방법으로 ! 한 번 계산한 fibo(n)는 arr에 저장하고, 다시 계산하지 않는 방법으로 풀었습니다.  세 가지 방법은 아래의 코드처럼 풀이할 수 있습니다.   - 기본 코드 (재귀)def fibo(n): if n    - 기본 코드 (for loop)n = int(input())fibonacci = [0, 1]for i in range(2, n+1): ..

문제: 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 발생으로 코드를 리팩..

문제: https://www.acmicpc.net/problem/2960 풀이  이번 문제는 어렵지 않았지만 코드가 조금 지저분하게 작성됐습니다. 시간 제한은 1초로, 이중 for문으로 충분한 시간이라 이중 for문으로 구현했습니다. 그러나, cnt를 셀 때마다 k랑 맞는지 확인하고 break를 걸어주어야 하는 부분 때문에 코드가 지저분해졌고 'if ~' 부분을 반복해서 작성했습니다.  따라서 방향성을 바꿔서 깔끔한 코드로 수정했습니다. 또한 이중for문을 완전히 탈출할 때 if문을 두 번 쓰지 않고, 하단의 코드처럼 else: continue break로 작성해도 됨을 배웠습니다.  - 지저분한 코드n, k = map(int, input().split())num_list = [i for i in ran..

문제:  https://www.acmicpc.net/problem/17478 나는 재귀함수 구현을 헷갈려하는 편인데, 이 문제를 통해 제대로 알길 원한다. 재귀보다 후에 작성한 코드는 재귀가 종료된 후 실행함을 고려하면서 코드를 작성했다.  .join(문자열)은 문자열 사이에 특정 문자를 삽입할 수 있는 함수이다. 이때, 문자열 맨 앞에도 특정 문자를 삽입해야 하기 때문에 문자열에 ""를 추가했다.  def recursive(cnt, n): if cnt == n: string = "____" * cnt text1= [ "", "\"재귀함수가 뭔가요?\"\n", "\"재귀함수는 자기 자신을 호출하는 함수라네\"\n",..

문제 잘못된 풀이 n = int(input()) dp = [0] * n dp[0] = 1 dp[1] = 2 for i in range(2, n): dp[i] = dp[i-1] + dp[i-2] print(dp[n-1] % 10007) 해당 문제는 다이나믹 프로그래밍으로 해결할 수 있다. 2*1일 때, 1 / 2*2일 때, 2 / 2*3일 때, 3 / 2*4일 때, 5 / 2*5일 때, 8 으로, dp[i] = dp[i-1] + dp[i-2]를 만족한다. 하지만 해당 풀이는 dp의 사이즈를 n으로 지정하면서 런타임 오류(IndexError)가 발생하였다. 올바른 풀이 n = int(input()) dp = [0] * 1000 dp[0] = 1 dp[1] = 2 for i in range(2, n): dp[..

문제 잘못된 풀이 T = int(input()) for i in range(0, T): n = int(input()) dp = [0] * n dp[0] = 1 dp[1] = 2 dp[2] = 4 for j in range(3, n): dp[j] = dp[j-1] + dp[j-2] + dp[j-3] print(dp[n-1]) 해당 문제는 n=1일 때, 1 / n=2일 때, 2 / n=3일 때, 4 / n=4일 때, 7 / n=5일 때, 13 / n=6일 때, 24이다. dp를 n만큼 초기화하여 문제 풀이를 시도했다. 런타임 에러(IndexError)로 문제풀이에 실패했다. 올바른 풀이 T = int(input()) def dfs(n): if n == 1: return 1 elif n == 2: return..

문제 올바른 풀이 n = int(input()) # 1 ~ 90 dp = [0] * (n+1) dp[0] = 0 dp[1] = 1 for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[n]) 해당 문제는 다이나익 프로그래밍에 대한 매우 간단한 문제라, 쉽게 풀 수 있다.