본문 바로가기

백준58

[Java] [백준 1300][이분 탐색, Parametric Search] K번째 수 문제 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. 입력 첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다. 출력 B[k]를 출력한다. BOJ 1300: K번째 수 🌈 풀이 후기 처음에 단순하게 배열에 넣어서 검사하려다가 범위가 너무 커서 메모리 오류가 났습니다. 범위를 잘 파악하고 문제를 시작해야 시간낭비를 줄일 수 있을것 같습니다. 곰곰히 생각해보니 이전에 풀다가 실패했던 유형과 비슷했.. 2021. 3. 1.
[Java] [백준 2075][우선순위큐] N번째 큰 수 문제 N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자. 12 7 9 15 5 13 8 11 19 6 21 10 26 31 16 48 14 28 35 25 52 20 32 41 49 이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다. 입력 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. 출력 첫째 줄에 N번째 큰 수를 출력한다. 🌈 풀이 후기 우선순위큐를 이용하면 정말 쉽게 풀 수 있습니다. 우선순위 큐를 그.. 2021. 2. 27.
[Java] [백준 11659][누적합] 구간합 4 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 🌈 풀이 후기 전형적인 누적합 문제입니다.누적합 개념을 익히기에 좋은 문제인것 같습니다. https://www.youtube.com/watch?v=rI8NRQsAS_s&ab_channel=동빈나 제가 좋아하는 동빈나에서 자세히 알려주고 있습니다 ㅎㅎ 심심하면 봐보세요! 👩‍🏫 문제 풀이 알고리즘 - 누적합 누적.. 2021. 2. 27.
[Java] [백준 2003][투 포인터] 수들의합 2 문제 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. 🌈 풀이 후기 전형적인 투 포인터 문제입니다. 투 포인터 개념을 익히기에 좋은 문제인것 같습니다. https://www.youtube.com/watch?v=rI8NRQsAS_s&ab_channel=동빈나 제가 좋아하는 동빈나에서 자세히 알려.. 2021. 2. 27.

티스토리툴바