코딩 테스트 대비 백준 정리

지금 까지 푼 문제중에서 꽤 어렵거나 배울만한 점이 있었던 것들을 정리해보자.

 

1. 1016번 : 제곱 ㄴㄴ 수

• 1 ≤ min ≤ 1,000,000,000,000 (long long)
• min ≤ max ≤ min + 1,000,000 (10^6, 8MB)

제곱 ㄴㄴ 수 : 1 외의 정수 제곱수로 나누어 떨어지지 않는 수

예시 : 1~10 = 1,2,3,5,6,7,10은 제곱수? ㅇㅇ / 4,9는 제곱수? ㄴㄴ

 

1부터 sqrt(max)까지 모두 하나하나씩 한다? -> min의 범위가 너무 큼

나누어진다? -> 소수가 아니다. 즉, 제곱수로 나누어 떨어진다 -> 소수의 제곱으로 나누어 떨어진다.

예시) 18 -> 3^2 * 2

 

그렇다면 1,000,000,000,000까지의 모든 소수를 확인할 수 있을까?

제곱수이므로 sqrt(1,000,000,000,000) = 10^6까지만 해도 됀다, 메모리, 시간 문제 X

 

이렇게 판별된 소수를 바탕으로, 제곱수를 만들고, MIN, MAX안의 범위에서 만들어진 제곱수를 곱셈해가면서 하나씩 제거해가면 될 것같다. DP를 사용하면 될 것 같지만, 범위 자체는 10^12이므로, MIN과 MAX의 차이는 10^6이므로 인덱싱을 y = x - min과 같이 하면 될것 같다.

 

실제 구현한 코드를 보니 굳이 소수를 사용할 필요는 없었다. 어차피 10^6개니까.

 

과정에서 배울만 한 것은 소수 판별 과정에서 사용한 에라토테네스의 체(메모리에서 원하는 수의 배수를 모두 소거해가며 소수를 판별하는 방식, sqrt까지만 확인하면 됌)정도가 있겠다.

 

 

2. 1058번 : 친구

내가 이 문제를 푼 방식은 1-친구와 2-친구를 나누어서 구하는 방식이였다. 2친구는 간단하게 직접 연결된 모든 노드들과 그 노드들에 방문하지 않은 노드들을 구하면 됐다. 이렇게 구한 2-친구와 1-친구를 합하면 문제를 쉽게 해결할 수 있다.

그런데 굳이 이 문제를 적은 이유는 플로이드-와샬 알고리즘을 적용할 수 있기 때문이다. 연결된 모든 노드에 대해 다른 모든 노드로의 최소 길이를 알 수 있는 알고리즘인데, 이것이 2보다 작거나 같은 수를 모두 더하는 것이다. 방식으로는 모든 경로 [i][j]에 대해서 노드 k를 반드시 지나는 경로를 하나씩 갱신해나가면 된다.

 다익스트라와 다르게 모든 노드에 대해 최소 길이를 알 수 있으므로 장점이나, O(N^3)이라는 단점이 있다. (다익스트라는 O(E logV))

 

 

3. 1202번 : 보석 도둑

보석과 가방을 무게에 대해 정렬한다. 각 가방에 대해서 보석의 무게가 가방의 무게보다 작은 보석을 하나씩 빼면서 우선순위 큐에 집어넣는다. 그리고 보석의 무게가 가방의 무게보다 크다면, 가장 가치가 높은 보석을 가방에 넣으면 된다.

맨 처음에는 보석의 가치에 대해서 정렬하고 가장 가방의 무게와 가까운 것을 가방을 선택하게하려고 했는데, 시간이 초과가 되었다. 아무래도 n * log N 즉,  3*10^5*10^3 = 3*10^8정도라서 그런 것 같다.

그렇기 때문에 lower_bound를 통해 탐색을 하기 보다는 priority_queue를 사용하여 하나씩만 참조하는 방식이 더 좋다.

즉, priority_queue자료구조의 특성을 활용하면 문제를 더 쉽게 풀 수 있다는 것!

 

4. 1507번 : 궁금한 민호

 

모든 노드로의 길이 최소인지 아닌지는 다시한번 만들어 보면 될 것 같다. 모든 노드로 부터 모든 노드로의 최단길이이니 플로이드 워셜을 사용해야 할것 같다. 현재 노드 k에 대해서 모든 노드로 부터의 모든 노드로의 거리 [i][j] > [i][k] + [k][j] 이면 [i][j] = [i][k] + [k][j]로 배정하는것이니, [i][j] == [i][k] + [k][j] 를 만족한다면 그 경로는 단일 경로가 아닌, 단일경로들로 이어진 최단경로들일것이다.

이렇게 하나 씩 소거하다보면 단일 경로만을 판별할 수 있을것이고 다 더하면 될것이다. 만약 [i][j] < [i][k] + [k][j]라면 이미 잘못된 최단경로이기 때문에 찾을수 없음 즉,  -1 을 출력하면 된다.

 

 

 

5. 1644번 : 소수의 연속합

에라토스의체와 DP밖에 없을 것 같다. 1 ≤ N ≤ 4,000,000이므로, 대충 16MB정도일 것이다.  범위에 대해서 소수를 판별한다. 그리고 prefix-sum을 통해 합을 저장하고, i~j부터, 부족하면 j를 하나 높이고, 너무 많으면 i을 하나 높이는 형태로 진행하다가 같으면 결과를 ++하면서 판별하면 될 것 같다.  

뭐 아니면 소수 배열에서의 인덱스인 i를 0부터 n까지 부터 시작해서 만약 입력과 같다면 ++하면서 판별하는 방식도 있을 것 같다. 

 

 

6. 1520번 : 내리막 길

DFS + DP이다. DP[i][j]를 [i][j]에서 부터 목적지까지 다다를 수 있는 경로의 수라고 하자. 만약 현재 [i][j]로 도착했는데, 메모리에 저장된 값이 있다면, 이미 그 경로를 지나온 적이 있다는 것이므로 [i][j]에 다다르기 까지의 메모리의 값에 [i][j]의 값을 더하면 된다. 이후 출발점인 [0][0]의 값을 확인하면 된다.

 

 

7. 1655번 : 가운데를 말해요

이 문제 또한 자료구조의 특징을 활용한 문제이다. 값을 계속 넣을때마다 중앙의 값을 출력해야하는데, list의 insert와 lower_bound를 이용해서 구현할 수 있겠지만, 자료구조를 이용하면 더 쉽다.

모든 데이터를 3가지로 나눈다. 하나는 중앙, 하나는 중앙값보다 작고, 높은 값을 우선으로 하는 priorty_queue, 하나는 중앙값보다 크고, 낮은 값을 우선으로 하는 priorty_queue로 3개로 나누면 된다.

이 두 자료구조의 size를 바탕으로 하나 넣을 때 마다 중앙값을 바꾸고, 양 자료구조에 밀린 값을 insert한다.

 

 

8. 1700번 : 멀티탭 스케줄링

k구 멀티탭에서 기구 n개를 순서대로 꽃을 때 현재 i번째 기구를 꽃고 있고 모든 멀티탭이 사용중이라고 할 때, i+1 기구가 멀티탭에 없는 기구라고 한다면 앞으로 나올 기구들을 봐야한다. 문제는 어디까지 봐야하는가? 인데 값의 제한을 보았을 때(n, k가 100 이하의 자연수) 100*100 해봐야 큰 수가 아니기 때문에 끝까지 봐도 상관없을 것 같다.

뒤에 봐야할 것은 이미 멀티탭에 꽃혀있는 기구를 체크하고 k-1개가 다 확인된다면 마지막에 남은 것을 빼는 것이다. 만약 끝까지 간다면 나오지 않은 모든 기구중 아무거나 빼서 새로 꽃으면 된다. 이걸 체크하는 과정에서는 set이 필요할 것이다. k개의 실제set과 같은 tmp_set을 복사하고 그 set에 대해서 이미 있는것을 마주치면 erase하고 마지막에 빠지는 기구를 삭제하고 다음 기구를 실제 set에 추가하면 된다.  

 

 

9. 1715번 : 카드 정렬하기

또 자료구조 특성 문제이다. 최소인 2개를 계속 합치는게 가장 좋은 방식이다.  그렇다면 계속해서 가장 작은 값을 선택해야할텐데 이에 맞는 특성을 갖는 자료구조인 priority_queue를 이용하면 된다. 2개 뽑고, output에 그 합을 더하고, priority_queue에 합을 insert하면 된다. 이 자료구조의 size가 1일때 다 합쳐졌다고 가정하고 끝내면 된다.

 

 

10. 1726번 : 로봇

뭐 여느 문제와 같이 DP와 BFS를 활용한 최소 거리를 찾는 문제이다. 다만, 전진과 방향 전환의 행동이 나뉜 문제인데, 흐름으로 보면 현재 점에서 직진하고 2개의 방향으로 도는 것 총 3가지의 행동을 한다.(만약 방문되지 않았다면) 그렇게 해서 원하는 점에서 원하는 방향이 된다면 중지한다.

 

 

 

11. 1753번 : 최단경로

조건 : 1≤V≤20,000, 1≤E≤300,000

다익스트라의 복잡도 -> E log V = 3*10^5 * 10^2 이니까 괜찮을것같다. V = 20,000 = 2 * 10^4인데, n x n의 배열에 넣기에는 너무 많다.

모든 노드에 대해서 vector에 간선을 넣고, 시작 점부터 하나씩 빼가면서 모든 노드를 정복, 배열을 채우고 그걸 또 참조하여 또 다른 노드를 참조한다. priority_queue에 노드와 현재까지의 거리 정보를 저장하고 하나씩 빼고 간선을 참조하며 새로운 노드를 배열에 갱신해 나아가면 된다.

 

 

12. 1781번 : 컵라면

보석도둑과 같이 데드라인에 대해 오름차순으로 정렬한다. 정렬된 문제에 대해 현재 데드라인보다 작은 모든 문제를 priority_queue에 넣는다. 만약에 현재 데드라인보다 문제의 데드라인이 더 커진다면 priority_queue에서 가장 큰 값을 꺼내고, 다음 데드라인으로 넘어간다. 이렇게 계속 하다보면 최댓값을 얻을 수 있을것이다.

 

 

13. 1826번 : 연료 채우기

우선 위치에 대해서 정렬한다. 그리고 현재위치로 부터 움직일 수 있는 점은 [현재 위치 ~ 현재 연료로 최대로 갈 수 있는 위치]니까 어차피 한번 멈출 때 다음에 최대의 위치로 갈 수 있는 주유소를 찾는다. 이걸 그리디하게 하면 될 것 같다. 

첨엔 이렇게 생각했는데 보니까 이건 안된다. 왜냐하면 [현재 위치 ~ 현재 연료로 최대로 갈 수 있는 위치]에 주유소가 없다면 문제가 된다. 당연히 이전에 지나온 주유소 중 하나를 아무거나 골라도 되지만, 현재를 기준으로 한다면 그것은 불가능하다.

따라서 지금까지 지나온 모든 주유소를 priority_queue에 넣고, 최대 거리를 갱신해나간다. 만약 이 pq가 empty라면 끝까지 못가는 것이고, 된다면 pop함수가 호출된 수를 리턴하면 된다.

 

14. 1915번 : 가장 큰 정사각형

DP를 활용하는 꽤 재밌었던 문제로 기억한다. [i][j]를 점 (i,j)를 맨 오른쪽 맨 아래로 하는 정사각형의 최대 크기라고 정의하면, [i][j]에 대해서 [i-1][j]과 [i][j-1]과 [i-1][j-1]를 보고 최솟값 + 1을 하면 최대 정사각형의 크기를 구할 수 있다.

그림을 그려보면 명확하게 알 수 있다. 3x3의 맨 밑, 맨 오른쪽을 보면 그 위, 옆, 대각선을 끝으로 하는 정사각형은 2x2가 최대이므로 이의 최솟값인 2+1 = 3이 되는 것이다.

 

 

15. 1939번 : 중량제한

N, M(1≤M≤100,000) / A, B(1≤A, B≤N) /  C(1≤C≤1,000,000,000)제한이 꽤 빡세다.

파라메트릭 서치로 특정 weight에 대해서 BFS를 해당 노드에서 부터 다른 노드로 갈 수 있는지 없는지를 판별하면 최대 weight가 나올것이다. 한번에 search에 O(N)이므로 10^5정도, 파라메트릭 서치에는 log(C) = 10^4정도일것이다.

더 이상 탐색하지 못한다면 BFS가 바로 종료되므로 이보다는 조금 더 낮을것으로 예상되지만 확실하진 않고, 백준에서 정답으로써 체택되었지만 더 확실하게 해보자면, 간선 크기를 오름차순으로 정렬하고 한개씩 선택하면서 그래프를 만드는게 가장 좋은것 같다.

간선의 크기에 대해 오름차순으로 정렬하고 disjoint set을 이용해서 [start]와 [dest]의 root가 같을때 그래프를 만들면서최소 간선의 길이를 출력하면 된다.

 

 

16. 2098번 : 외판원 순회 (TSP)

외판원 순회 문제는 O(N!)의 복잡도를 가지므로 N = 16이라고만 하더라도 10^13이다.

그렇기 때문에 단순히 brute force하게 가면 안되고, DP를 이용해야한다.

비트 필드를 활용하여 하나의 정수로 방문노드를 모두 표현하고, 그에 대해 배열을 생성한다. 그렇게 되면 총 저장될 메모리는 다음과 같을것이다. dp[now_pos][visited]. 이 의미는 now_pos에서 visited상태일 때 순회의 최솟값을 저장할 것이다.

이렇게 되면 결국엔 16 *65536의 경우의 수만 존재할 것이므로 그렇게 충분히 풀만한 연산수가 나오게 된다.

 

너무 많다..... 이정도 까지만 하자