본문 바로가기

BOJ10

[C++] 2003번 수들의 합 2 [ 문제 ] 2003번 문제보기 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. [ 제출코드 ] [ 풀이 ] 처음부터 더해서 sum이 M을 초과하면 sum=0으로 하고 i+1부터 다시 더한다. [ 이야기 ] '알고리즘 분류'를 보지 않고 풀었다. 2021. 4. 27.
[C++] 1920번 수 찾기 [ 문제 ] 1920번 문제보기 [ 제출코드 ] [ 풀이 ] A = 4 1 5 2 3 B = 1 3 7 9 5 1. A배열을 오름차순으로 정렬. A = 1 2 3 4 5 2. left = 0번 인덱스, right = (n-1)번 인덱스, mid = ((left+right)/2)번 인덱스 1 2 3 4 5 left mid right if (A[mid] B[i]) right = mid-1; else 1출력; [ 참고 ] 이분탐색 2021. 4. 22.
[C++] 2309번 일곱 난쟁이 [ 문제 ] 2309번 문제 보기 [ 제출코드 ] [ 풀이 ] 1. 모든 난쟁이의 키를 더해준다. 2. sumDiffer = (모든 난쟁이의 키) - 100 3. 배열을 오름차순으로 정렬한다. 4. 두 개씩 더해서 sumDiffer인 두 명을 선택한 뒤, 두 명의 키를 -1로 설정한다. 5. 0이상인 난쟁이의 키만 찾아서 출력한다. for i=0 to 8 for j=1 to 9 if (arr[i] + arr[j] == sumDiffer) { arr[i] = -1; arr[j] = -1; break; } [ 이야기 ] 내가 처음에 생각한 풀이는 다음과 같았다. 1. 배열을 오름차순으로 정렬한다. 2. 7개의 키를 더한다. 2-1. 키의 합이 100이 아니라면 가장 마지막을 pop하고 그다음 인덱스를 pus.. 2021. 4. 21.
[C++] 1026번 보물 [문제] 1026번 문제보기 [제출코드] #include #include #include int main(){ int N; std::cin>> N; std::vector A; std::vector B; for(int i=0; i> x; A.push_back(x); } for(int i=0; i> x; B.push_back(x); } std::vector tempA(N, 0), tempB(N, 0); std::copy(A.begin(), A.end(), tempA.begin()); std::copy(B.begin(), B.end(), tempB.begin()); std::sort(tempB.begin(), tempB.end()); std::sort(tempA.begin(), tempA.end()); std.. 2021. 3. 15.
[C++] 1463번 1로 만들기 [문제] 1463번 문제보기 [제출코드] [풀이] 1 2 -> 1 3 -> 1 4 -> 3 -> 1 5 -> 4 -> 3 -> 1 6 -> 2 -> 1 ... 노란색으로 칠해진 부분은 이미 앞에서 연산된 부분이다. 했던 계산을 또 하는 것은 비효율적이므로, 연산을 사용하는 최솟값을 배열에 저장한다. [이야기] 항상 vector만 사용했기에 이번에는 동적배열을 사용해보고 싶었다. [참고] 함수로_배열_전달 2021. 2. 24.
[C++] 10870번 피보나치 수 5 [문제] 10870번 문제보기 [제출코드] [이야기] 이 문제는 다이나믹 프로그래밍을 안다면 너무 쉽게 풀 수 있는 문제다. 2021. 2. 24.
[C++] 1003번 피보나치 함수 [문제] 1003번 문제보기 [제출코드] [풀이] f(0) = 0 f(1) = 1 f(2) = f(1) + f(0) = 1 + 0 f(3) = f(2) + f(1) = { f(1) + f(0) } + f(1) = 1 + 0 + 1 ... 재귀로 풀면 위처럼 이미 계산한걸 또다시 계산해야하므로 비효율적이다. 하지만 DP로 풀게 되면, f(0)과 f(1)의 결과만 배열에 저장해놓고 2이상의 n은 앞의 2개의 결과를 더해주기만 하면 되므로 훨씬 시간이 단축된다. [이야기] 알고리즘을 배우기 전 DP를 몰라서 시간초과로 틀렸던 문제다. 그때는 다이나믹을 생각하지 않고 재귀로 해서 틀렸었다. 2021. 2. 22.

티스토리툴바