viamemine

문제: https://www.acmicpc.net/problem/1158 풀이  리스트 회전을 구현하는 법을 알면 어려운 문제는 아니였습니다.# *** 으로 표시한 부분을 주의하여 구현하면 되는 문제입니다. # pop 해야 할 원소를 list의 가장 마지막으로 옮기고 pop = O(1)N, K = map(int, input().split())arr = [i for i in range(1, N+1)]idx = 0 # 제거될 사람의 인덱스 번호ans = []for i in range(N): idx = (idx + K-1) % len(arr) # *** ans.append(arr.pop(idx))ans[0] = ""print(*ans, sep= ', ')

문제: https://www.acmicpc.net/problem/1918  풀이 오늘은 stack, queue, deque의 문제 유형인 후위 표기식을 풀어보겠습니다. 연산자 우선순위1. () 2. * /3. + - stack을 이용하여 연산자의 우선순위를 고려하여 문제를 해결해보도록 하겠습니다.  리스트에 식전체를 넣어 for문을 통해 한 문자씩 확인합니다.1. ()를 확인2. * / 인지를 확인하고, 먼저 들어온 같은 우선순위에 있는 * /는 모두 출력 문자열에 추가3. 현재 연산자를 stack에 추가4. + - 인지를 확인하고, + - 보다 낮은 우선순위의 연산자가 없기 때문에 자신보다 우선순위가 높은 연산자들을 모두 출력 문자열에 추가5. )를 발견하면 ( 와 ) 사이에 있는 모든 연산자들을 출력..

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