본문 바로가기

분류 전체보기130

[C++] 백준 1939번: 중량제한 (다익스트라) https://www.acmicpc.net/problem/1939문제 이해하기 문제의 요구사항은 다음과 같습니다.섬과 각 섬을 잇는 다리의 중량 제한이 주어질 때, 한 섬에서 다른 섬으로 한 번에 물품을 옮길 수 있는 최대 중량을 구하여라.시간복잡도 어림하기브루트 포스 알고리즘(플로이드 워셜 알고리즘) 문제를 해결하기 위해 가능한 모든 경로를 탐색해볼 수 있습니다. 해당 알고리즘으로는 플로이드 워셜 알고리즘이 있습니다. 하지만, 플로이드 워셜 알고리즘은 O(n^3)의 시간복잡도를 가집니다. 문제에서 n의 최댓값은 10,000 이므로 제한 시간 내에 문제를 해결하기 어렵습니다.DP 알고리즘(다익스트라 알고리즘) 한 노드에서 다른 노드까지의 가중치를 구하는 문제이므로 다익스트라 알고리즘을 떠올릴 수 있습니다.. 2024. 9. 3.
[C++] 백준 2812번: 크게 만들기(그리디) https://www.acmicpc.net/problem/2812문제 이해하기 문제의 요구사항은 다음과 같습니다.주어진 숫자에서 숫자 K개를 지웠을 때, 만들 수 있는 가장 큰 수를 구하여라.시간복잡도 어림하기브루트 포스 알고리즘 제외할 모든 수를 골라 수를 제거하여 만드는 방법을 생각해볼 수 있습니다. 제거할 수를 선택하는 경우의 수는 조합이므로 nCk로 계산됩니다. 하지만, 문제의 n과 k의 최댓값은 500,000 이므로 그 경우의 수가 너무 큽니다. 따라서 브루트 포스 알고리즘으로 문제를 해결할 수 없습니다.DP 알고리즘 DP 알고리즘을 사용하기 위해서는 이전 상태를 활용할 수 있어야 합니다. 만약 지금까지 idx에 문자를 덧붙이는 방식으로 진행한다면, 매 idx 마다 문자를 붙일지 붙이지 않을지 .. 2024. 8. 28.
[C++] 백준 2143번: 두 배열의 합 (누적합) https://www.acmicpc.net/problem/2143문제 이해하기 문제의 요구사항은 다음과 같습니다.어떤 배열에서 i부터 j까지의 합을 부 배열의 합이라고 할 때, 배열 A의 부 배열의 합과 배열 B의 부 배열의 합이 T가 되는 모든 쌍의 수를 구하여라.시간복잡도 어림하기브루트 포스 알고리즘 부 배열의 합은 i부터 j까지의 합을 의미하므로 이를 구하기 위해 누적합을 사용할 수 있습니다. 누적합을 사용하여 어떤 배열에 대해 가능한 모든 부 배열의 합을 구한다면 O(N^2)의 시간복잡도가 필요합니다. 첫 번째 루프로 시작 위치를 고정하고, 두 번째 루프로 끝 지점을 1씩 증가시키며 모든 구간 합을 구하는 방식입니다. 문제에서 N의 최댓값은 1000이므로 1000^2 = 1000000(백만)입니다.. 2024. 8. 27.
[C++] 백준 2473번 : 세 용액 (이분 탐색, 두 포인터) https://www.acmicpc.net/problem/2473문제 이해하기 문제의 요구사항은 다음과 같습니다.세 용액의 특성값의 합이 0에 가장 가까운 세 용액을 구하여라.시간복잡도 어림하기브루트포스 알고리즘 단순히 모든 경우의 수를 살펴본다면 O(N^3)의 시간복잡도가 걸립니다. 문제에서 N의 최댓값이 5000이므로 5000^3 = 125,000,000,000(1250억) 번 반복됩니다. 이는 제한시간 내에 해결하기 불가능한 수치이므로 브루트포스 알고리즘을 사용할 수 없습니다.DP 알고리즘 DP 알고리즘을 사용하기 위해 이전에 계산된 상태를 이용할 수 있어야 합니다. 이번 문제는 이전 계산 상태를 사용하여 현재 상태를 계산하기 애매한 유형이므로 DP 알고리즘을 사용하지 않습니다.이분탐색, 두 포인터.. 2024. 8. 23.
[C++] 백준 17142번: 연구소 3 (구현) https://www.acmicpc.net/problem/17142문제 이해하기 문제의 요구사항은 다음과 같습니다.M개의 바이러스를 활성화하여 모든 칸에 바이러스를 퍼뜨릴 수 있는 최소 시간을 구하여라.시간복잡도 어림하기 미리 시간복잡도를 어림하는 것이 큰 의미가 없는 구현 문제이므로 생략하도록 하겠습니다.알고리즘 설계하기  코드의 전체 흐름부터 설계해봅시다.1. 활성화할 바이러스 M개를 선택한다.2. 바이러스를 퍼뜨린다.3. 모든 빈 칸에 바이러스가 퍼졌는지 확인한다. 먼저 여러 바이러스 중 활성화할 바이러스 M개를 선택해야 합니다. 이는 조합으로 해결할 수 있습니다. 이때, 조합으로 뽑는 바이러스 수는 정확히 알 수 없으므로 반복문 대신 재귀 호출로 구현해야 합니다. 저는 모든 바이러스 위치를 저장한.. 2024. 8. 22.
[C++] 백준 17135번: 캐슬 디펜스 (구현) https://www.acmicpc.net/problem/17135문제 이해하기 문제의 요구사항은 다음과 같습니다.지도의 가장 아래 외곽에 성이 있고, 성에 궁수를 3명 배치할 때, 제거할 수 있는 적의 최대 수를 구하여라.추가적인 조건은 다음과 같습니다.1. 궁수는 사거리 안에 있고, 가장 가까운 적을 공격한다. 해당 적이 여럿인 경우 가장 왼쪽의 적을 처리한다.2. 여러 궁수가 하나의 적을 처치할 수도 있다.3. 모든 궁수의 공격이 끝나면, 적은 한 칸 아래로 이동한다. 이때, 성이 있는 칸으로 이동한 경우 적은 사라진다.시간복잡도 어림하기 미리 시간복잡도를 어림하는 것이 큰 의미가 없는 구현 문제이므로 생략하도록 하겠습니다.알고리즘 설계하기 코드의 흐름부터 구성해봅시다.1. 궁수 배치2. 모든 적이.. 2024. 8. 21.

티스토리툴바