본문 바로가기

백준 문제풀이93

[백준][이분 탐색] 18770 c++ 구현 목차 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 문제 문제 풀이 나는 중복을 제거해준 정렬된 배열을 따로 만들어 이분 탐색을 하는 식으로 코드를 구현했다. 코드 구현 #include #include #include #include using namespace std; vector v; //벡터 페어로 각각 개수 저장 vector sort_v; //정렬된 중복x 배열 int main() {.. 2024. 3. 20.
[백준][그리디] 18310 안테나 c++ 구현 https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 문제 문제 풀이 최적부분 구조는 정렬했을 때 크기가 짝수이면 중간 index-1 크기가 홀수이면 가운데 중간 index이다. 코드 구현 #include #include #include #include using namespace std; vector arr; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, num, i, sum=.. 2024. 3. 19.
[백준][그리디] 11501 주식 c++ 구현 목차 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 문제 문제 풀이 시 주의해야 할점 이중반복문을 돌리게 되면 시간 복잡도가 O(N^2)이 나와 시간초과로 틀리게 된다. 따라서 전처리를 통해 자기보다 큰 것이 없는지 있는지 정해주어 풀면시간복잡도가 O(N)으로 풀리게 도힌다. 문제 풀이 오늘보다 뒷날에 주가가 더 큰 것이 있다. 매수한다. 오늘보다 뒷날에 더 큰 것이 없다. 주식이 있다면 판다. 주식이 없다면 나둔다. 이런식의 최.. 2024. 3. 16.
[백준][이분 탐색] 1484 다이어트 c++구현 목차 https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 문제 문제 풀이 시 주의할 점 현재 몸무게와 그 전 몸무게가 자연수인 것을 주의 해야 한다. 처음에 식을 풀어서 이분 탐색을 했는데 식을 풀지말고 A^2-B^2 형태로 이분탐색을 해야한다. 문제 풀이 내가 탐색하고자 하는 현재몸무게를 A, 그 전 몸무게를 B라고 놓으면 G = A^2-B^2의 형태가 나온다. 그 후 A를 기준으로 B를 이분탐색해주면 된다. 코드구현 #include #include #incl.. 2024. 3. 14.
728x90

티스토리툴바