본문 바로가기

전체 글411

[알고리즘] 이분 탐색 (Binary Search) 목차 이분 탐색이란? 이분 탐색 혹은 이진 탐색 (Binary Search)는 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 이 알고리즘은 자료가 순서에 따라 정렬된 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다. 따라서, 탐색할 때마다 검사 범위가 절반으로 줄어든다. 이분 탐색 의 진행 단계 이분 탐색에서는 내가 찾고자 하는 값이 정렬된 배열의 중간 값보다 크면 중간값을 포함한 하위 값들은 탐색 대상에서 제외하고, 반대로 찾고자 하는 값이 배열의 중간 값보다 작으면 중간 값을 .. 2023. 8. 7.
[백준] 10813번 : 공 바꾸기 – JAVA [자바] https://www.acmicpc.net/problem/10813 10813번: 공 바꾸기 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 바구니에는 공이 1개씩 들어있고, 처음에는 바구니에 적혀있는 번호와 같은 번호가 적힌 공이 www.acmicpc.net 문제 문제 풀이 백준 10813번 공 바꾸기는 브론즈 2 난이도의 구현 및 시뮬레이션 문제이다. 이 문제에서는 N개의 바구니가 주어지고 각각 바구니들은 1부터 N까지 적혀있다. 그리고 바구니에는 공이 1개씩 들어있고, 처음에는 바구니에 적혀있는 번호와 같은 번호가 적힌 공이 들어있다. 이때 M개 줄에 걸쳐서 자연수 i와 j가 주어진따. 이때, i번째 바구니에 들어있는 공을 j번째 바구니에 들어있는 .. 2023. 8. 7.
[백준] 10810번 : 공 넣기 – JAVA [자바] https://www.acmicpc.net/problem/10810 10810번: 공 넣기 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 또, 1번부터 N번까지 번호가 적혀있는 공을 매우 많이 가지고 있다. 가장 처음 바구니에는 공이 www.acmicpc.net 문제 문제 풀이 백준 10810번 공 넣기는 브론즈 3 난이도의 구현 및 시뮬레이션 문제이다. 이 문제에서는 1번부터 N번까지 번호가 적혀 있는 바구니가 주어지고 각각 바구니에는 공을 1개씩만 넣을 수 있다. 그리고, M개 줄에 걸쳐 정수 i j k가 주어진다. 이때, k가 적혀 있는 공을 i번 바구니부터 j번 바구니까지 넣으면 된다. 이때, 공을 다 넣었으면 각각 바구니에 몇 번이 쓰여있는 공.. 2023. 8. 7.
[백준] 2566번 : 최댓값 – JAVA [자바] https://www.acmicpc.net/problem/2566 2566번: 최댓값 첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 위치한 행 번호와 열 번호를 빈칸을 사이에 두고 차례로 출력한다. 최댓값이 두 개 이상인 경우 그 중 한 곳의 위치를 출력한다. www.acmicpc.net 문제 문제 풀이 백준 2566번 최댓값은 브론즈 3 난이도의 구현 문제이다. 이 문제에서는 9 X 9 격자판에 81개의 자연수 또는 0이 주어진다. 이때, 이들 중 최댓값을 찾고 그 최댓값이 몇 행 몇 열에 위치해 있는지도 구하면 된다. 이 문제는 배열을 이용하지 않아도 충분히 풀 수 있다. 이 문제는 StringTokenizer만 이용해서도 충분히 풀 수 있다. StringTokenizer는 문자열을 분리하는 클래.. 2023. 8. 7.
[백준] 25314번 : 코딩은 체육과목 입니다 – JAVA [자바] https://www.acmicpc.net/problem/25314 25314번: 코딩은 체육과목 입니다 오늘은 혜아의 면접 날이다. 면접 준비를 열심히 해서 앞선 질문들을 잘 대답한 혜아는 이제 마지막으로 칠판에 직접 코딩하는 문제를 받았다. 혜아가 받은 문제는 두 수를 더하는 문제였다. C++ www.acmicpc.net 문제 문제 풀이 백준 25314번 코딩은 체육과목 입니다는 브론즈 5 난이도의 문제이다. 이 문제에서 4의 배수인 정수 N이 주어진다. 이때 혜아가 N바이트 정수까지 저장할 수 있다고 생각하는 정수 자료형의 이름을 출력하면 된다. 문제에서 주어진 바로는 혜아는 기본인 4 바이트는 long int라고 생각하고 여기서 4 바이트씩 추가될수록 앞에 long이 붙는다고 생각한다. 따라서, .. 2023. 8. 4.
[백준] 1747번 : 소수&팰린드롬 – JAVA [자바] https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고,www.acmicpc.net 문제  문제 풀이백준 1747번 소수&팰린드롬은 실버 1 난이도의 수학 및 에라토스테네스의 체 문제이다. 이 문제에서는 정수 N이 주어진다. 그리고 N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서 가장 작은 수를 출력하면 된다. 이 문제에서 중요한 포인트는 바로 소수 찾기와 팰린드롬인지 확인하는 것이다. 이 문제에서는 한 숫자가 소수인지 아닌지를 구하는 게 .. 2023. 8. 3.
[백준] 23972번 : 악마의 제안 – JAVA [자바] https://www.acmicpc.net/problem/23972 23972번: 악마의 제안 첫째 줄에 악마가 제안한 정수 K와 N이 공백을 사이에 두고 주어진다. (1 ≤ K, N ≤ 200,000,000) www.acmicpc.net 문제 문제 풀이 백준 23972번 악마의 제안은 브론즈 3 난이도의 수학 문제이다. 이 문제에서는 처음에 X원을 가지고 있다. 그리고 악마한테 K원을 지불하면 남은 금액 (X - K)원을 N배로 만들어준다고 한다. 이때, 처음에 얼마를 가지고 있어야 K원을 지불했을 때 손해를 보지 않는지 구하면 된다. 그리고 무조건 손해를 본다면 -1을 출력하면 된다. 즉, 다음과 같은 식을 이용해서 풀면 된다. 추가로, 무조건 손해를 보는 조건은 N이 1일 때다. 이때, 악마한테 K.. 2023. 8. 3.
[백준] 1920번 : 수 찾기 – JAVA [자바] https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 문제 풀이 백준 1920번 수 찾기는 실버 4 난이도의 정렬 및 이분 탐색 문제이다. 이 문제에서는 N개의 정수들이 주어지고 그다음에 M개의 정수들이 주어진다. 이 M개의 정수들 중에서 전에 주어진 수면 1을 출력하고 이전에 주어진 수가 아니면 0을 출력하면 된다. 이 문제는 HashSet을 이용해서 풀 수도 있겠지만 이 풀이에서는 정렬과 이분.. 2023. 8. 3.
반응형

티스토리툴바