이분 탐색16 [백준]3151: 합이 0 - JAVA https://www.acmicpc.net/problem/3151 풀이N개의 숫자들 중 3개를 선택하여 그들의 합을 0으로 만드는 경우의 수를 찾는 문제이다. 배열에 숫자들을 저장하여 정렬한다. 첫 번째 숫자를 선택하고, 그 다음 숫자를 left, 배열의 끝 숫자를 right로 놓고 left와 right를 조정하여 합이 0이 되는 수를 찾는다. 선택한 숫자를 node라고 할 때, `node + arr[left] + arr[right]` 가 0이 되는 경우를 찾아 정답을 증가시킨다. `arr[left]` 와 `arr[right]`가 같은 경우에는 left부터 right까지의 수가 n개라고 할 때 nC2의 조합을 구하는 것과 같다. 처음 선택한 수를 0부터 시작하여 증가시키면서 값이 0보다 커질 때까지 실행.. 2024. 9. 3. [백준] 20917: 사회적 거리 두기 https://www.acmicpc.net/problem/20917 풀이솔브드에 랜덤 마라톤 기능이 생겼다. 일주일마다 8문제를 랜덤으로 골라주는데, 풀 문제를 따로 고르지 않아 편한 점이 있다. 이 문제도 랜덤 마라톤에 있는 문제였다. 좌석들의 위치가 주어지고, 좌석을 s개 선택할 때 거리의 최댓값을 구해야한다. 좌석들의 위치를 입력받아 정렬했다. 서로 떨어진 거리를 기준으로 이분탐색을 하는데, 이때 일정 거리(mid)를 기준으로 좌석의 위치 배열을 앞에서부터 탐색하면서 배치할 수 있는 좌석의 개수를 헤아린다. 좌석의 개수가 원하는 개수보다 적다면 `high`를 `mid -1`로 배치하고, 원하는 개수 이상이라면 `mid`값을 `result`에 넣고, `low`를 `mid +1`로 늘려 더 큰 거리에서.. 2024. 7. 18. [백준] 28449: 누가 이길까 - JAVA https://www.acmicpc.net/problem/28449 풀이HI 팀과 ARC 팀의 모든 사람들끼리 한번씩 대결하여 N X M회의 대결이 성사된다. HI팀이 이기는 횟수, ARC팀이 이기는 횟수, 무승부하는 횟수를 구해야 한다. 각 팀의 점수를 입력받아 각각 정렬했다. HI팀을 순회하면서 HI팀원의 점수를 타겟으로 하여 ARC팀에서 해당 점수와 같은 점수가 있는지 찾았다. 이때, 이분탐색을 이용하여 같은 점수가 시작되는 지점(drawStart), 같은 점수가 끝나는 지점(drawEnd)를 각각 찾았다. drawStart보다 작은 값들은 HI팀이 이기게 되고, drawEnd보다 큰 값들은 ARC팀이 이기게 된다. 메모리: 41148KB시간: 700ms언어: Java 11import java.i.. 2024. 6. 18. [백준] 1477: 휴게소 세우기 - JAVA https://www.acmicpc.net/problem/1477 풀이이분탐색으로 풀어야겠다는 생각이 바로 들지 않았다. 우선순위큐를 이용해 풀어보려고했는데 잘 되지 않아서 구글링의 도움을 받았다. 이분탐색을 하는데 휴게소들 사이의 거리를 기준으로 탐색한다. 이분탐색을 어떤걸 기준으로 하는지 찾는 것이 어려웠다. 휴게소 간 거리이기때문에 left를 1로, right를 l-1로 놓고 진행했다. mid만큼의 거리를 두고 이미 있는 휴게소들 사이에 mid만큼 거리로 몇 개나 더 세울 수 있는지 체크한다. 이렇게 헤아린 개수를 통해 구간을 좁혀나간다. 메모리: 14268KB시간: 128ms언어: Java 11import java.io.*;import java.util.*;public class Main { .. 2024. 5. 19. [백준] 8983: 사냥꾼 - JAVA https://www.acmicpc.net/problem/8983 풀이x축에 사냥꾼들의 위치가 주어지고, 동물의 좌표가 x, y 좌표로 주어진다. 사냥꾼의 총의 사정거리가 주어지고, 동물을 몇 마리 잡을 수 있는지 구하는 문제이다. 동물을 기준으로 자신을 잡을 수 있는 사냥꾼이 있는지 판별했다. 동물의 위치로부터 사정거리 내에 있는 x축 위 점의 최소, 최대를 구한다. 이를 left, right로 하고 이분탐색을 통해 사냥꾼의 위치가 이 범위 안에 있는지 확인한다. 메모리: 55416KB시간: 700ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Animal { int x; .. 2024. 5. 19. [프로그래머스] 징검다리 건너기 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]위과 같은 배열으로 징검다리들의 숫자가 입력으로 들어온다. 디딤돌을 밟을때마다 숫자가 1씩 줄어들고, 0인 돌이 있다면 안뛰고 건너뛸 수 있다. 하지만, 입력으로 k가 주어지는데 한번에 k개의 돌만 건너뛸 수 있다. 예를 들어, `[5, 3, 2, 1, 4]` 이러한 배치를 하고있다면 3명이 돌을 건너간 후의 상태는 `[2, 0, 0, 0, 1.. 2024. 5. 19. [백준] 2792: 보석 상자 - JAVA https://www.acmicpc.net/problem/2792 풀이M가지 보석을 N명의 학생들에게 나눠주어야한다. 보석을 받지 못하는 학생이 있어도 된다. 따라서 질투심을 몇 개로 할지를 변수로 두고 이분 탐색을 했다. 질투심을 mid로 했을 때 보석을 받는 학생의 수가 N보다 작으면 정답이 될 수 있다. N보다 크면 left를 mid + 1로, 그렇지 않으면 right를 mid - 1로 좁혀가면서 탐색한다. 메모리: 34892KB시간: 356ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { Buffer.. 2024. 5. 18. [백준] 15810: 풍선 공장 - JAVA https://www.acmicpc.net/problem/15810 풀이만들어야 할 풍선의 개수와 한 사람이 풍선 하나를 만드는데 얼마나 걸리는지가 주어진다. 만들어야 할 풍선의 개수가 1,000,000개까지 주어지므로 연산과정에서 타입으로 long을 선택했다. 걸리는 시간을 기준으로 이분탐색을 진행했다. `left`는 1로, `righ`t는 (`소요 시간 배열의 최댓값 \* 풍선 목표량`) 으로 했다. `(left + right) / 2` 의 시간동안 각각 몇개씩 풍선을 만들 수 있는지 계산하여 더해줬고, 목표량보다 적으면 `left`를 `mid + 1`로, 크거나 같으면 `right`를 `mid - 1`로 해줬다. 계산값이 목표량보다 크거나 같을 경우 답을 갱신해줬다. 메모리: 93420KB시간: .. 2024. 5. 17. [알고리즘] 이분 탐색 - JAVA 이분 탐색이분탐색은 탐색할 대상이 정렬된 상태에서 사용한다. 데이터의 특정 값을 찾기 위해 대상을 둘로 나눠 절반씩 줄여나가는 원리이다. 대상을 반씩 줄이기 때문에 시간복잡도는 O(logN)이다. 주어진 데이터에서 중복되지 않은 값이 주어질 때, 데이터 내에 특정 값이 존재하는지 여부를 확인하는 방법으로 많이 사용한다. 동작 방식은 다음과 같다. 1. 배열의 중간 값을 가져온다. 2. 중간 값과 검색 값을 비교한다. - 중간 값이 검색 값과 같다면 종료한다. (mid = key) - 중간 값보다 검색 값이 크다면 중간 값 기준 오른쪽 구간을 탐색한다.(right = mid-1) - 중간 값보다 검색 값이 작다면 중간 값 기준 왼쪽 구간을 탐색한다.(left = mid+1) 3. 값을 찾거.. 2024. 5. 17. [백준] 19637: IF문 좀 대신 써줘 - JAVA https://www.acmicpc.net/problem/19637 풀이N개의 문자열과 숫자가 주어진다. 해당 숫자 이하의 점수라면 해당 문자열이 칭호가 되는 것이다. 문자열과 점수를 배열에 저장해두고 M개의 점수가 나올 때마다 해당 배열을 이용해서 맞는 칭호를 출력해야 한다. 칭호의 개수 최대값이 10의 5제곱이기 때문에 앞에서부터 확인하면 시간초과가 발생한다. 따라서, 이분탐색을 통해 해당 구간에 점수가 포함되는지 확인해주었다. 메모리: 54040KB시간: 520ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Node { String name; int score; .. 2024. 5. 17. 이전 1 2 다음