Save my data

깊이 우선 탐색과 너비 우선 탐색 기초문제이다. 깊이 우선 탐색 - Depth First Search 트리나 그래프에서 임의의 분기를 마주칠 때 마다 어떤 노드에 어떤 형태의 분기가 있다는 것을 기억만 해 놓고 계속 내려간다. 그러다가 막다른 곳(자식 노드가 없는 노드 == 리프 노드) 을 마주하게 되면 전에 기록해놓았던 분기로 되돌아가서 그 분기부터 다시 파고들어가는 것을 그 그래프의 모든 노드를 방문할 때 까지 계속 반복한다. 말 그대로 깊이를 우선해서 탐색하는 방법이다. 너비 우선 탐색 - Breadth First Search 트리나 그래프에서 임의의 분기를 마주치면 분기 하위의 자식 노드들을 너비 방향으로 방문해간다. 어떤 분기에서 그 분기의 뿌리가 되는 부모 노드의 형제 노드들을 우선적으로 방문..

배낭 문제와 비슷한 원리로 풀리는 문제인데, 처음에 아이디어를 잘못 가져다가 고민을 하는 바람에 시간이 엄청 걸렸다. 한 번에 안 풀려서 방치하고 있다가 푸는데 거의 이틀이 걸렸다... 핵심 아이디어 : 내가 현재 몇 종류의 동전을 가지고 있다면, 그 때 그 동전들을 가지고 목표값을 만들 수 있는 모든 경우의 수를 저장하는 것 처음에 나는 dp에 경우의 수를 저장하지 않고 각 동전이 입력될 때 그것을 가지고 만들 수 있는 누적합 비슷하게 저장하려고 시도했었다. 그러기 위해서 dp 를 2차원 배열로 만들고 온갖 헛수고를 했는데, 다시 생각해보면 문제풀이를 시작한 극초반에 다양한 아이디어가 스쳐가던 중 배낭 알고리즘 활용하는 방법이 뇌리에 스쳤었는데 그것을 구체화하지 못했던 것이 아쉽게 느껴진다. 난 항상 ..

자주 등장했던 문제유형이다. 리스트 슬라이싱 후에 해당되는 부분만 매번 원본에서 바꿔주면 된다. 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 일 때 ..