꺼진불도다시보자

문제 https://www.algospot.com/judge/problem/read/TRIANGLEPATH algospot.com :: TRIANGLEPATH 삼각형 위의 최대 경로 문제 정보 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 www.algospot.com 접근방법 메모이제이션을 활용한다. 중복 계산을 없앨 수 있다. 완전 탐색이라면 최악의 경우 2^100 을 훨씬 넘어가지만, 메모이제이션을 활용하면, 저장된 값을 재사용가능하기 때문에, 100 * 100 = 10000 의 계산 내에서 해결 가능하다. 코드 #include #include #include..

문제 접근방법 코드 완전탐색 코드 : bool match(const string& w, const string& s) { //w[pos]와 s[pos]를 맞춰나간다. int pos = 0; while(pos < s.size() && pos < w.size() && (w[pos] == '?' || w[pos] == s[pos])) ++pos; //더이상 대응할 수 없으면, 왜 while문이 끝났는지 확인한다. //2.패턴 끝에 도달해서 끝난 경우, 문자열도 끝났어야 대응됨 if (pos == w.size()) return pos == s.size(); //4.*를 만나서 끝난 경우: *에 몇 글자를 대응해야 할지 재귀 호출하면서 확인한다. if (w[pos] == '*') for (int skip = 0;..

문제 접근방법 분할정복. 3개로 분할하는데, 하나는 왼쪽, 하나는 중간, 하나는 오른쪽. 주목해봐야할 부분은 중간에 걸친 사각형의 최댓값을 계산하는 부분이다. for loop이 돌 때마다 더 높은 막대를 선택하고, ret와 비교해서 더 큰 값을 고른다. 코드 #include #include #include #include using namespace std; #define FOR(i, n) for (int i=0;i> C; while(C--) { cin >> n; h = vector(n); FOR(i, n) cin >> h[i]; cout

문제 접근방법 iterator를 쓰기 때문에, 함수가 하나 끝나고 나서도 자연스럽게 it변수를 그대로 받아 쓸 수 있다. it은 마지막으로 끝난 함수에서 검사한 위치 다음을 가리킨다. 코드 , #include #include #include using namespace std; #define FOR(i, n) for (int i=0;i> C; while(C--) { string quadtree; cin >> quadtree; string::iterator it = quadtree.begin(); string answer = reverse(it); cout

문제 접근방법 완전탐색 하는 경우, 4^10의 시간이 걸린다. 2^20이므로 1000000정도다. 코드 #include #include #include using namespace std; #define FOR(i, n) for (int i=0;i> C; while(C--) { clocks = vector(16, 0); FOR(i, CLOCKS) { cin >> clocks[i]; } int answer = solve(clocks, 0); cout

문제 접근방법 재귀함수를 이용한 완점탐색이다. 순서를 강제하여 중복으로 세는 문제를 해결한다. 코드 #include #include #define FOR(i,n) for (int i=0;i> C; while (C--) { int cnt = 0; int answer = 0; cin >> h >> w; board = vector(h, vector(w, 0)); FOR(i,h) FOR(j,w) { char temp; cin >> temp; if (temp == '#') board[i][j] = 1; else { board[i][j] = 0; cnt++; } } if (cnt == 0) answer = 1; else if (cnt % 3 == 0) answer = cover(board); cout 1) ok =..

해결과정 완전탐색할 때 가장 주의해야할 점은 중복으로 세는 문제이다. 아래 예시는 중복으로 세고 있는 경우이다. int n; bool areFriends[10][10]; //taken[i] = i번째 학생이 짝을 이미 찾았으면 true, 아니면 false int coutPairings(bool taken[10]) { //기저사례 : 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다. bool finished = true; for (int i=0;i