알고리즘/문제풀이 - 백준

백준 12865 평범한 배낭

문제 : https://www.acmicpc.net/problem/12865 서론 어디서 본것같은 문제였는데 풀어보니 처음본다. 공부해놓고 잊은건 실망스러우니 어디서 본것같은건 반드시 착각이다. 풀이 유명한 문제라고 해서 크게 고민 안하고 배낭문제를 검색했다. 참고한 사이트는 https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C https://huiyu.tistory.com/entry/DP-01-Knapsack%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C 배낭문제를 모르고, 위의 참고한 사이트를 읽어보지 않으면 아래의 내용은 이해할 수 없다. dp의 행은 아이템, 열은 무게다. 무게 3짜리를 기준으로 dp[0][0]..

2019. 8. 19. 15:52
알고리즘/문제풀이 - 백준

백준 11049 행렬 곱셈 순서

문제 : https://www.acmicpc.net/problem/11049 서론 DP와 분할정복 아이디어를 이미 갖고 있었음에도 구현을 못한 문제 행렬을 어떻게 곱해서 재귀함수의 리턴으로 넘겨줘야할지를 해결하지 못했다. 다른분의 풀이를 참고하여 구현한 지금에서도 왠지모를 석연찮음이 남아있다. 아이디어 11066번 문제와 유사하다. 전체적인 풀이 아이디어는 이 문제와 같다. https://hydroponicglass.tistory.com/4 위 문제와 다른점은 행렬을 계산하는 것. (AB)(CD)에서 ABCD는 AB와 CD의 곱이다. 따라서 왼쪽분할인 AB의 결과값과 오른쪽분할인 CD의 결과값에 AB와 CD를 곱한 결과값을 더해줘야한다. 즉 재귀함수의 리턴값은 왼쪽+오른쪽+(왼쪽*오른쪽) 리턴값의 왼쪽*..

2019. 8. 18. 18:56
알고리즘/문제풀이 - 백준

백준 2869 달팽이는 올라가고 싶다

문제 : https://www.acmicpc.net/problem/2869 서론 문제 이름이 꼭 해결해주고싶게 지어졌다. 아이디어 문제를 식으로 구현해보면 지나간 날 = n (A-B)n +B >=V 하루에 이동할 수 있는 총 거리(A-B)에 지나간 날짜를 곱해주는데 마지막날은 정상에 올라가면 내려가지 않으므로 마지막날 내려간 B를 상쇄시키기 위해 B를 더해준다. 위 식을 변형하면 n>=(V-B)/(A-B) 식을 코드로 작성하면 끝 구현 (V-B)/(A-B)가 n보다 작을 경우 +1 //c++ #include int main() { long long a, b, v; std::cin >> a >> b >> v; long long result = (v - b) / (a - b); if ((a - b)*resu..

2019. 8. 18. 11:56
알고리즘/문제풀이 - 백준

백준 1712 손익분기점

문제 : https://www.acmicpc.net/problem/1712 서론 조건을 만족하는지 반복문을 돌려 확인하면 시간초과에 걸린다. 아이디어 시간초과를 고려하지 않고 조건을 만족하는지 알아보기 위해 반복문을 만든다. // i = 판매량 for(i){ if(a+b*i> b >> c; if (c > b) std::cout

2019. 8. 18. 11:02
알고리즘/문제풀이 - 백준

백준 10773 제로

문제 : https://www.acmicpc.net/problem/10773 서론 스택문제. STL을 사용하지 않고 간단한 스택을 만들어봤다. 다음문제는 연결리스트로 구현해볼 계획이다. 구현 //c++ #include using namespace std; int stack[100001]; int top = -1; void push(int input) { top++; stack[top] = input; } void pop() { top--; } int main() { int k; int result = 0; cin >> k; for (int i = 0; i > tmp; if (tmp == 0) pop(); else push(tmp); } for (int i =..

2019. 7. 16. 14:16
알고리즘/문제풀이 - 백준

백준 1541 잃어버린 괄호

문제 : https://www.acmicpc.net/problem/1541 서론 쉬운문제였는데 혼자 풀어내지 못했다. 풀이를 볼 때 조금 더 생각하지 않았음에 오는 아쉬운 문제가 있고 보길 잘했다는 생각이 드는 문제가 있다. 풀이를 빠르게 볼지 말지를 선택하는것은 어려운 일이다. 아이디어 그리디 알고리즘 문제라서 규칙성이 있을거라는 생각은 했지만 찾지 못했다. 모든 경우의 수를 일단 계산해볼까 생각했으나 이것도 쉬운일은 아니었다. 간단하게 '-'가 나올때까지 입력값을 tokenization 해주면 된다. 입력값이 55-50+40 이면 괄호를 50-(50+40) 해주면 되고 100-20-10이면 100-(20)-(10) 100-30+20-40+10이면 100-(30+20)-(40+10)이다. 직관적으로 음..

2019. 7. 15. 20:18