문제 출처 : 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..
문제 출처 : https://www.acmicpc.net/problem/2564분류 : 구현 백준 2564 경비원최소 거리 구하기구현 포인트1) 특정 점을 기준으로 위치를 다시 표현동, 서, 남, 북에 따라 점의 위치를 따로 다루기에는 코드가 길어지고 복잡해 지므로조금만 더 생각해 보면 왼쪽 상단을 0으로 두고, 시계방향으로 각 점들의 위치를 나타내면 간단해 진다. 코드는 아래 같다.123456789101112131415161718192021#include #include int main() { int w, h, n, sum=0; scanf("%d %d %d", &w, &h, &n); int d, o, *a = new int[n+1]; for (int i = 0; i
[1068] 트리
문제 출처 : https://www.acmicpc.net/problem/1068분류 : 트리 백준 1068 트리트리의 노드를 삭제시 남은 리프 노드의 갯수를 구하라구현 포인트1) 트리를 간단하게 구현(배열로) 2) Bottom-up으로 리프의 갯수를 파악한다. 우선 첫번째로 풀었던 방식은 각 노드마다 각 노드가 root인 sub-tree의 리프노드 갯수를 가지고 있게 한뒤노드가 삭제되면 전체 리프노드 갯수에서 삭제된 리프노드의 갯수를 삭제하도록 했다. 이렇게 생각하면 고려해야 하는 부분이 더 생긴다. 위와 같이 4번노드를 삭제 할 때 자식 노드가 1개로 이어진 경우 위와 같은 논리는 문제가 생긴다.이런 경우를 고려하여 답을 찾도록 추가적으로 구현을 해주어야 했다. 1234567891011121314151..