본문 바로가기

이진탐색

[백준 18870] 좌표 압축 (JAVA)

CodingTEST 2023. 12. 9. [백준 18870] 좌표 압축 (JAVA) 백준 18870번 문제 - 좌표 압축 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 문제 분석 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. 가장 작은 수를 0으로 해서 정렬에 따라 숫자가 1씩 증가한다. 중복 수는 동일한 수를 준다. ex) 2 4 -10 4 -9 → -10 -9 2 4 4 ..

[백준 1654] 랜선 자르기 (JAVA)

CodingTEST 2023. 11. 24. [백준 1654] 랜선 자르기 (JAVA) 백준 1654번 문제 - 랜선 자르기 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 분석 K개의 서로 다른 길이의 랜선을 가지고 N개의 동일한 길이의 랜선을 제작하고자 한다. 이때 가장 N개의 랜선을 만들 수 있는 가장 긴 길이를 출력해라. 해결 키 포인트 K개의 랜선 길이 합을 구하고, 합을 N으로 나눴을 때 값을 알아낸다 : 할 수 있는 최대 랜선 길이 (max) 방법 1 : 1부터 max까지 11개를 만들 수 있는 최대 길이 구하기 실패 ! 시간 초과 방법 2 : 이진..

[백준 1300] K번째 수 (JAVA)

CodingTEST 2023. 8. 12. [백준 1300] K번째 수 (JAVA) 백준 1300번 문제 - K번째 수 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제 분석 N*N 배열을 1차원 배열로 정렬해서, k번째 수를 출력해라 해결 키 포인트 이진탐색으로 해결한다는 마인드를 가져야 함 (본인도 이를 못해서 힌트를 찾음) NxN배열에서 k보다 큰 수를 배열을 만들어서 정렬한 뒤 찾으려면 메모리 초과로 불가능 n보다 큰 값은 i번째의 행의 i / n 개의 수가 존재한다. 3X3배열에서 4보다 큰 값 1번째 행 4 / 1 3 2번째 행 4 / 2 2 3번..

이전 1 다음

티스토리툴바