백준17 [C++,DP] 백준 1463번 1로 만들기 문제풀이, DP와 분할정복의 특징 문제링크 백준 1463번 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 다시 복습하는 DP문제이다. 다시 DP 개념부터 집고 넘어가야겠다. DP(Dynanic Programing)란? 주어진 문제를 여러 개의 부분 문제들로 나누어 푼 다음, 그 결과들로 큰 문제를 푸는 방법을 말하며 여기서 DP의 Dynanic은 개발자가 아무 의미없이 붙인 거라고 한다... 큰 문제를 해결하기 쉽게 여러 개의 쉬운 부분 문제들을 풀어 해결하는 방법 정도로만 이해하면 될 것 같다. 분할정복이랑 비슷한 개념이기는 하나 분할정복은 문제를 분할했을 때 겹치는 문제가 발생하지 않지만, DP는 겹치는 문제가 발생하기 때문에 메모이제이션.. 2019. 2. 26. [C++] 백준 2309번 일곱난장이 문제풀이 문제 링크 백준 2309번 일곱난장이 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net DP관련 문제인 줄 알았더니 알고보니 짐승공격 문제였다. ㅎㅎㅎ 항상 9개가 입력되고 7개의 답안이 출력된다는 점에 착안해서 9개 중에 골라낼 가짓수 2개를 모두 하나하나 대입하여 제외하고 나머지 7개의 합이 100이 되는지 판단하는 문제이다. vector와 sort함수를 이용하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 .. 2019. 2. 14. [C++] 백준 1181번 단어정렬 문제풀이 문제 링크 백준 1181번 단어정렬 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 간단한 심화 정렬 문제이다. string으로 단어를 받고 sort 함수를 이용해 정렬을 하는데 compare 함수를 따로 길이순으로 반환을 한 후에 길이가 같다면 알바벳순으로 오름자순 정렬을 하는 형식이다. string size 함수를 이용해 길이를 파악하고 길이가 같다면 단순 비교를 통해 함수를 만들었다. 정렬을 공부하는 사람이라면 도움이 많이 될 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 .. 2019. 1. 24. [C++] 입출력 속도 가속시키기 백준 2741번 N찍기 풀이 std::ios_base::sync_with_stdio(0) 알고리즘을 공부하다 사람들이 std::ios_base::sync_with_stdio(0);를 간간히 사용하는 것을 보았다. 왜 그런지 궁금하여 찾아보니 C++에서 흔하게 사용되는 입력 방법은 cin인데 이 cin이 다른 입력방법 (scanf, get)에 비해 상대적으로 느리다는 것이다. 알고스팟에 올라온 자료를 첨부한다. 출처 : https://algospot.com/forum/read/2496/ 위의 자료에 따르면 std::cin은 scanf보다 거의 3배가까이 느린것으로 나온다. 이유는 cpp의 iostream의 buffer와 c의 stdio buffer와 동기화 시켜주므로 2개의 버퍼사용으로 속도가 저하된다는 것이다. 하지만 std::ios_base::sync_with_stdio(false);를 사.. 2018. 8. 6. [C++] 백준 1002번 터렛 문제풀이 문제 링크 백준 1002번 터렛 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include using namespace std; int main() { long long T=0,C=0,sr=0,br=0; double A=0; long long x1=0,x2=0,y1=0,y2=0,r1=0,r2=0; cin>>T; while(T!=0){ cin>>x1>>y1>>r1>>x2>>y2>>r2; A=sqrt(abs(x1.. 2018. 8. 6. 이전 1 2 다음
