문제 출처 : https://www.acmicpc.net/problem/1517분류 : 정렬 백준 1517 버블 소트NlogN 안에 swap수를 구하자구현 포인트1) Merge sort를 이용하여 swap을 구한다. (O(NlogN))2) long long으로 답을 기록한다. 일반적인 버블소트나 flagged한 방법을 써도 N이 크므로 시간초과가 난다. 생각보다 방법을 떠올리기 쉽지 않아서 기록을 남기기로 하였다. 핵심은 Merge를 통해 NlogN으로 time을 줄이는데에 있다.절반씩 나누어 정렬을 하는데, 그 안에서 Bubble Sort로 정렬하는 것이 아니라 Merge sort를 하면서비교 인덱스를 이용하여 swap수를 바로 구해준다. (아래 코드의 line 21)이 과정은 O(1) 시간이 걸리고,..
문제 출처 : https://www.acmicpc.net/problem/1086분류 : 수학 백준 1086 피보나치 수의 합큰 범위의 피보나치 수의 합을 구하라구현 포인트1) 피보나치 행렬표현을 이용 (O(logN))2) 피보나치 수의 합을 수식으로 구하기이 문제는 피보나치 수에 대해 공부하면서 2)를 망각하고 있었기에 남기기로 했다.1)과 2)에 대한 내용은 링크에 있다. 코드는 아래와 같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include#include#define mod 1000000000 using namespace std;typedef vector matrix; matrix ope..
문제 출처 : https://www.acmicpc.net/problem/1037분류 : 구현 백준 1037 약수약수를 주면 원래 수 찾기구현 포인트1) 없음이 문제는 실수를 해서 남기기로 했다. 주어진 진짜 약수가 정렬되어서 나오리란 보장이 없는데.. 왜 정렬되서 나올것이라고 생각했는지..멍청했다..;; 코드는 아래와 같다. 1234567891011121314151617#include#include#includeusing namespace std; int main() { int n; scanf("%d", &n); vector divider; while (n--) { int tmp; scanf("%d",&tmp); divider.push_back(tmp); } sort(divider.begin(), div..
문제 출처 : https://www.acmicpc.net/problem/2580, https://www.acmicpc.net/problem/2239분류 : 백트래킹 백준 2239, 2580 스도쿠스도쿠의 답을 찾아라구현 포인트1) 백트래킹(DFS)2) 2239번의 경우 사전식 우선순위를 고려하여 코딩해 주어야 한다. 이 문제에 대해 글을 남기는 이유는 이 문제가 삼성 SDS에 초청되어 campus tour를 갔을 때삼성 SW 역량평가 중에 어려운 문제의 수준과 유사하다고 했기 때문이다.푸는데는 약 30분 정도가 소요되었다.2239를 풀고 2580을 푸는데 문제가 완전 똑같아서 푼 문제 수만 1개 늘려주었다. 개이득! 스도쿠의 빈칸 좌표를 모두 저장한 후(vec), 하나씩 꺼내어 가능한 경우를 오름차순 순..
문제 출처 : https://www.acmicpc.net/problem/1914분류 : 재귀 호출 백준 1914 하노이 탑BigInteger 를 C++에서 구현하기구현 포인트1) 재귀적으로 하노이탑을 구현2) 100개의 원판까지 구현이 가능해야 하므로 숫자가 long long으로 표현되지 않는다.3) 2)의 이유로 string으로 숫자를 구현해야 한다. 이 문제에서 얻어갈 수 있는 것은 2가지 정도이다.1) JAVA에 있는 BigInteger를 C++ string으로 구현해 본다는 것이다.unsigned long long범위(0~2^64-1)까지의 범위를 넘어가므로 따로 숫자를 저장하여 계산을 해주어야 한다. 2) float는 부동소수점 방식에 의해 2^100은 표현가능하지만 2^100-1은 표현할 수 ..
문제 출처 : https://www.acmicpc.net/problem/8983분류 : 이분탐색 백준 8983 사냥꾼O(n*n)을 O(nlogn)으로 줄이기구현 포인트1) 1초안에 돌아가야 하므로 O(nlogn) 만에 해결해야 한다. 2) 이를 위해 이분 탐색을 써야 한다.3) 값의 범위는 int내에서 해결가능 함을 다시 상기시키자. (항상 값의 범위를 체크하여 자료형을 결정하는 것이 중요하다.)이 문제가 정답률이 낮은 이유는 아마 시간초과 때문일 것이다. 사로에 대해 모든 동물들을 비교하게 되면 당연히 O(NM)시간이 걸리고, 이는 1초안에 끝나지 않는다.둘 중 하나를 fix해놓고 나머지 하나를 log시간안에 해결해야 시간초과가 나지 않음을 알 수 있다. 1) 사로를 fixed할 경우이 경우 한 사로에..
문제 출처 : https://www.acmicpc.net/problem/2602분류 : DP 백준 2602 돌다리 건너기모든 경우의수 구하기구현 포인트1) DP로 할 것사실 이 문제는 DP라고 문제를 보자마자 알아채지 못했다. 아직 실력이 부족한 탓인가..문제를 보고 상황 자체가 백트래킹 같아서 DFS로 접근을 하였다. 결과는 물론 시간초과;; 1초내에 몇 억이 될수있는 모든 경우를 DFS로 보기에는 역시.. 주어진 조건에서 DFS로의 해결이 불가능 할꺼라는 것을 미리 잡았어야 했다. 일단 처음에 DFS로 구현했던 코드는 아래 같다. 123456789101112131415161718192021222324252627282930313233#include#includeusing namespace std; ch..