Save my data

자주 등장했던 문제유형이다. 리스트 슬라이싱 후에 해당되는 부분만 매번 원본에서 바꿔주면 된다. import sys N, M = map(int, sys.stdin.readline().split()) basket = [0] + [i for i in range(1, N + 1)] for _ in range(M): i, j, k = map(int, sys.stdin.readline().split()) mid_to_rear = basket[k:j + 1] front_to_mid = basket[i:k] basket[i:j + 1] = mid_to_rear + front_to_mid print(*basket[1:]) 간단했던 구현문제

DP 문제이다. DP 문제는 반복의 맨 처음 단계에서 어떤 패턴을 찾으면 그 다음은 빠르게 풀린다. 그리고 항상 그걸 못 찾아서 문제다... 다만 확실히 DP 문제를 풀면 풀수록 뇌가 DP 화 되는 느낌이 있다. 나 같은 범재도 이런식으로 반복하면 그래도 요령이 생기는구나 싶어서 보람은 있었다. ※ 결국 노력과 반복이 답이다... 문제 풀이 아이디어 공유 : 줄 == 가로방향, 칸 == 세로방향 먼저 각 줄의 i 번째까지 누적합을 저장해 줄 dp 리스트를 만든다. 0 으로 마진을 두는게 편해서 인덱스 번호는 항상 1 부터 시작하게 만드는 편이다. 다른 사람들은 그렇게 안 한 사람도 있었다. 누적합의 패턴이 어떤지는 모르지만 여타 DP 문제가 그래왔듯 이번에도 비슷하겠거니 싶어서 일단 그렇게 만들었다. 2..

원본 리스트에서 j - i 회 만큼 pop 을 해준 것을 i 번째 원소 앞에 insert 해주었다. import sys N, M = map(int, sys.stdin.readline().split()) basket = [0] + [i for i in range(1, N + 1)] for _ in range(M): i, j = map(int, sys.stdin.readline().split()) cnt = j - i for k in range(1, cnt + 1): basket.insert(i, basket.pop(i + k)) print(*basket[1:]) 근데 이건 너무 꼬아서 생각한 풀이고, 사실 더 쉬운 방법은 그냥 reverse 함수같은걸로 뒤집은 다음 그 부분만 바꿔 주면 되는 문제였다. 아..

기본적인 LCS 알고리즘 문제이다. LCS 알고리즘에 대해서는 어떤 분이 굉장히 자세히 써 놓으셨는데, 새로 배우는 입장에서 굉장히 이해가 쉽도록 그림자료까지 첨부가 되어 있어서 이해하기가 좋았다. [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다. velog.io 나도 이번에 LCS 라는 알고리즘을 처음 보았는데 위 자료를 참고하여 풀었다. import sys S1 = sys.stdin.readline().strip() S2 = s..

다이나믹 프로그래밍 알고리즘을 활용하는 문제이다. DP 문제는 기초가 되는 점화식을 정확하게 세우면 문제가 쉽게 풀리는데, 계속 머릿속으로만 코드를 구성하려고 애쓰다보니 문제가 잘 안풀렸다. 대략적인 흐름을 dp[4] 정도까지만 노트에 써보면서 흐름을 파악하니 어느 정도 윤곽이 나오는 것을 보고, 잘 안풀리는 문제가 있으면 머리로 애쓸것이 아니라 노트에 써가면서 눈으로 흐름을 파악해야 된다는 것을 깨달았다. (나는 폰 노이만이 아니요) DP 문제에 대해 스스로 부족함을 많이 느끼고 있기 때문에 나 자신을 설명시킬 겸 최대한 상세하게 뜯어가면서 설명했다. 이번 문제에 대한 점화식의 유도 과정을 아래에 써보았다. 내가 현재 카드 한 개를 가지고 있다고 생각하는 것에서 출발해보자. 왜냐하면 한 개를 살 때의 ..

import sys N, K = map(int, sys.stdin.readline().split()) dp = [[0] * (K + 1) for _ in range(N + 1)] for i in range(1, N + 1): w, v = map(int, sys.stdin.readline().split()) for j in range(1, K + 1): if j >= w: # 1 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v) # 2 else: # 3 dp[i][j] = dp[i - 1][j] # 4 print(dp[N][K]) 코드를 보면서 적어놓는게 나중에 더 이해가 쉬울 것 같아서 코드블럭을 앞으로 빼 두었다. 만약 현재 내가 들 수 있는 무게가 j 일 때 ..

기초적인 이분 탐색 문제였다. 이분 탐색은 리스트가 정렬되어 있을 때 사용할 수 있는 탐색의 한 종류이다. import sys sys.stdin = open("10815.txt", 'r') N = int(sys.stdin.readline()) n = [*map(int, sys.stdin.readline().split())] M = int(sys.stdin.readline()) m = [*map(int, sys.stdin.readline().split())] n.sort() for i in m: start = 0 end = N - 1 mid = (start + end) // 2 while start n[mid]: start = mid + 1 mid = (start + end) // 2 else: print..

ㅓ간단한 DP 문제였다. 예전에 이것과 비슷한 문제 (피보나치수열로 진행되는 문제) 를 풀어 본 경험이 있었는데, 그것과 매우 비슷하다는 것을 금방 깨달았다. N = int(input()) dp = [0] * (N + 1) dp[1] = 1 if N > 1: dp[2] = 2 for i in range(3, N + 1): dp[i] = (dp[i - 1] + dp[i - 2]) % 15746 print(dp[N]) 다만 15746 으로 나누는 부분에서 메모리 초과 한 번, 인덱스 범위 정해 줄 때 오류 한 번 해서 총 두 번 오답이 나왔는데 인덱스 부분은 오류를 금방 찾았지만 15746 으로 나누는 부분을 늦게 떠올렸다. 신기하면서 이해가 잘 되지 않았던 점은 15746 으로 나눈 나머지를 dp 에 적용..