viamemine

문제: https://www.acmicpc.net/problem/6550 풀이오늘 문제는 문자열을 다루는 문제입니다.부분 문자열이 포함되어있는지 확인하는 문제입니다. t와 s가 같을 때 idx를 하나씩 올려주면서, s 문자열이 t안에 완벽하게 있는지 확인합니다. while True: try: # 실행할 코드 s, t = map(str, input().split()) idx = 0 flag = 0 for i in range(len(t)): # subsequence if t[i] == s[idx]: # sequence idx += 1 if idx == len(s): ..

문제: https://www.acmicpc.net/problem/1912  풀이이번 문제는 연속 합의 최댓값을 구하는 문제입니다. 선택을 하냐, 하지 않느냐에 따라 dp[i]가 채워집니다. 어려운 문제는 아니였기 때문에 점화식을 구해서 풀 수 있었습니다.이전 값(dp[i-1])에 이번 값(arr[i])를 더한 값을 0과 비교해서, 최댓값을 dp[i]에 채우도록 풀었습니다.   n = int(input())arr = [0] + list(map(int, input().split()))dp = [0] * (n+1)if max(arr[1:])

문제: https://www.acmicpc.net/problem/2579 풀이오늘 문제는 경우의 수를 나누어 풀어야 하는 문제로, 점화식을 찾는데 어려움이 있었습니다.i를 점수 계산으로, j를 0/1/2번 연속 밟을 때로 간주하여 문제를 해결했습니다. 따라서, dp[i][j]는 i번 계단을 j번 연속 밟았을 때의 최대점수를 의미합니다. 그림을 보면서 설명드리겠습니다. dp[0]일 때, j = 0, 1, 2는 초기값 0입니다.  dp[1]일 때, j = 0은 계단을 밟지 않은 경우로 초기값 0입니다. dp[1]일 때, j = 1은 계단을 1번 밟은 경우로 10 입니다.dp[1]일 때, j = 2는 계단을 연속 2번 밟은 경우이지만 첫번째 계단이기 때문에 2번 밟을 수 없고, 10 입니다.  dp[2]일 때..

문제: https://www.acmicpc.net/problem/11726 풀이  계속해서 dp문제를 풀고 있습니다. 앞서 다른 게시글에서도 말씀드렸듯이, dp는 점화식을 구하는게 문제 해결의 핵심입니다 ! 아래의 그림처럼 n이 1일 때부터차근차근 경우의 수를 생각해보시면 점화식을 구할 수 있습니다. 아, 저는 dp를 (n+1)만큼만 구해서 답을 출력하려고 했으나 index error가 나오더라구요. n이 1이거나 2일 때, error가 발생하기 때문입니다. 따라서 dp는 문제와 같이 1000까지 구해야 오류 없이 정답을 도출할 수 있습니다.    n = int(input())dp = [0 for _ in range(10000)] # (n+1)만큼 하면 index errordp[1] = 1dp[2] = ..

문제: https://www.acmicpc.net/problem/9095 풀이 이번 문제도 DP 문제입니다.DP의 핵심은 점화식을 찾는 것인데, 쉽사리 점화식이 잘 보이지 않았던 문제입니다. 하지만 여러 문제를 풀어보고 나니, '1, 2, 3' 이게 하나의 힌트가 될 수 있음을 알게되었습니다.  오늘도 문제 풀이의 과정은 이해가 쉽도록 그림을 첨부하겠습니다 !   위의 그림처럼 n이 1일 때, 2일 때, 3일 때이렇게 순차적으로 정답을 생각해보면 좋습니다. n이 4일 때는 (n이 3인 경우 + 1), (n이 2인 경우 + 2), (n이 1인 경우 + 3) 임을 알게되었습니다.이렇게 점화식을 찾았으면, 코드를 작성하는 건 어렵지 않습니다 ^.^ !  코딩 고수가 되고싶네요 ...자 이제 코드를 보겠습니다 ..

문제: 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/1699 풀이 이전에 작성한 문제와 동일한 유형의 문제입니다.  문제 풀이는 이 게시글을 확인해주시기 바랍니다.https://esjeong153.tistory.com/96 [python] 17636. Four Squares문제: https://www.acmicpc.net/problem/17626  풀이 이번 문제는 제곱수의 합을 구하는 문제입니다.dp로 해결했는데, 점화식을 찾는 것이 쉽지 않았습니다.   이해를 위해 그림을 첨부했습니다. i를 가esjeong153.tistory.com 해당 게시글에 풀이과정이 설명되어 있기 때문에,풀이과정의 설명 없이 바로 코드를 공유하도록 하겠습니다.   n = int(input())dp = [i for..

문제: 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..

오늘은 git과 github에 대해 공부해보려고 합니다. Git과 Github의 차이점  - github: 소스코드를 올리는 어떤 공간 - git: 소스코드를 내 컴퓨터에서 인터넷으로 올려주는 역할  github는 개발 협업 tool로, 효율적인 코드 형상 관리를 하기 위함이라고 생각하면 됩니다  git 영역1) Working Directory (local): 개인 코드 작성 2) Staging 영역: git add를 통해 수정된 코드를 올리는 영역 3) Repository: git commit을 통해 최종 수정본을 제출 Git 작업 플로우 1) 저장소(Repository) 생성 원하는 폴더 들어간 후$ git init 또는 기존 github에 있는 저장소를 내 로컬로 복제할 수도 있다.$ git clo..

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