매일 꾸준히

https://www.acmicpc.net/problem/1448 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net 해결방안 : 빨대를 내림차순으로 정렬한다. 그 후 for문을 돌리면서 max값을 배열[0] ~ 배열[n-1]순으로 설정하고 세 빨대의 길이가 삼각형이 성립하면 바로 루프를 탈출한다 (내림차순 정렬이기 때문에 삼각형이 성립하는 경우가 최대값이 된다) 삼각형이 만들어 질 수 없으면 -1을 출력해준다. #include int compare(const void *a,const vo..

분할정복이란? 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산한다. 첫번째 그림은 항상 문제를 한 조각과 나머지로 쪼갠다. (재귀호출) 두번째 그림은 항상 문제를 절반씩 나눈다. (분할정복) 분할정복을 사용하는 알고리즘의 구성 요소 1)문제를 더 작은 문제로 분할하는 과정(Divide) 2)문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(Merge) 3)더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(Base case) 분할정복의 장점??? 문제를 나눔으로써 어려운 문제를 해결 할 수 있다.병렬적으로 문제를 해결하는 데 장점이 있다. 분할정복의 단점??? 일반적으로 재귀 함수를 ..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 입력의 최대 크기가 100000(10만)이고 종만북에서 본 것을 써보자면(주먹구구의 법칙) 서론) '입력의 최대 크기'를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해 ,1초당 반복문 수행 횟수가 1억을 넘어가면 시간 초과가 날 수 있다.! N->입력의 최대 크기가 10만이니깐 O(N^2) ->시간초과가 날 수 있다. O(N) -> 시간초과가 안 날 것이다.. DP로 풀면 O(N)의 시간복잡도로 풀 ..