soicem's note

계단을 오를 때 integer overflow를 방지하기 위하여 나머지를 더하는 문제. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #include using namespace std; int N;int cache[101][10]; int letsBin(int level, int last) { if (level == N) return 1; int & ret = cache[level][last]; if (ret != -1) return ret; ret = 0; if (last == 0) { ret += letsBin(level + 1, last + 1); ret %= 1000000..

최솟값을 찾아라면서 최대값을 찾는 문제. 문제를 풀면서 자료구조의 범위 지정에 신경쓰는 연습을 해야할듯 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include int N, K;int minTimes[1001];int cache[1002];int connect[1001][1001];int target; using namespace std; int getMinCraft(int target) { int &ret = cache[target]; if (ret != -1) return ret; ret = minTimes[target]; for (int i = 1; i > case..

기본 dp 문제 123456789101112131415161718192021222324252627282930313233#include #include #include #define MAX 0x12345678 int cache[1000001]; using namespace std; int makeOne(int N) { if (N == 1) return 0; int & ret = cache[N]; if (ret != -1) return ret; ret = MAX; if (N % 3 == 0) ret = min(ret, makeOne(N / 3) + 1); if (N % 2 == 0) ret = min(ret, makeOne(N / 2) + 1); return ret = min(ret, makeOne(N - ..

계단을 오를 때 어디서부터 오를 것인지, 오를 때 3칸 연속 오르면 안되기에 이를 처리해주는 곳만 있다면 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #define LOWEST -3000000 using namespace std; int N;int steps[301];int cache[302][2]; int getMaxStep(int level, int ctn) { if (level == N) return steps[N]; if (level > N) return LOWEST; int locCtn = ctn; if (locCtn > N; memset(cache..

동적계획법 기본 문제 12345678910111213141516171819202122232425262728293031#include #include #include using namespace std; int triangle[500][500];int cache[501][501];int N;int getMaxPath(int y, int x) { if (y == N) return 0; int & ret = cache[y][x]; if (ret != -1) return ret; return ret = max(getMaxPath(y + 1, x), getMaxPath(y + 1, x + 1)) + triangle[y][x];} int main() { cin >> N; memset(cache, -1, sizeof..

RGB거리, 처음엔 재귀와 메모이제이션으로 풀었다가 시간초과가 나서 현재값이 선택되었을 때 앞에 값 중 최소값과 더해서 나가는 형식으로 수정하니 O(N)으로 들어온다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #include #include #define HMAX 1000#define MAX 0x12345678using namespace std; int RGB[HMAX][HMAX];int cache[HMAX][HMAX + 1];int D[HMAX][HMAX];int N; int minRGB(int start, int prev) { if (N == start) return 0;..

어떤 문제든 하루에 한 문제만 꾸준히 풀기로~ fibonacci basic 문제ref : https://www.acmicpc.net/problem/1003123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include using namespace std; int cache[41];int fibonacci(int n) { int & ret = cache[n]; if (ret != -1) return ret; if (n == 0) { return 0; } else if (n == 1) { return 1; } else { ret = fibonacci(n - 1) + fibonacci(n - 2);..

16.1 Number Swapper 16.2 Word Frequencies : Design a method to find the frequency of occurences of any given word in a book. What if we were running this algorithm multiple times? -kmp 12345678910111213141516171819202122232425262728293031323334def getPi(p): m = len(p) j = 0 pi = [0 for _ in range(m)] for i in range(1, m): while j>0 and p[i] != p[j]: j = pi[j - 1] if(p[i] == p[j]): j += 1 pi[i] =..

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192class graph: def __init__(self): self.vertexList = set() self.edgeList = [] self.weightList = {} # {(start, end), weight} self.adjacencyList = {} def addVertex(self, vertex): self.vertexList.add(vertex) def addEdge(self, st..

1. Arrays and Strings 1. Is Unique : Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures? 12345678910111213141516171819202122232425262728293031323334353637383940# example 1 O(n^2)def isUnique(string): cnt = 0 lenString = len(string) while cnt 5->8->5->10->2->1 [partition=5]Output: 3->1->2->10->5->5->8 1234567891011121314151..