[S4] 수 찾기 __💡이분탐색 (Binary Search) __이분탐색을 이용한 배열에서 수 찾기 문제 __https://www.acmicpc.net/problem/1920 문제보기더보기 🙄어떻게 풀까?이분탐색 방식으로 풀이 진행이분탐색을 위해 배열을 정리하고정렬된 배열에서 이분탐색을 통해 값이 있는지 확인하는 과정을 거치면 된다.1. input 값 배열에 담고 정렬해두기이분탐색 진행을 위해서는배열의 정렬은 반드시 선행되어야 함static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Syste..
CS & 알고리즘/백준
__💡브루트포스 (BruteForce)__체스판을 만들기 위한 최솟값 구하기__https://www.acmicpc.net/problem/1018 문제보기더보기문제지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다..
[1157] 단어 공부__💡구현 (Implements)__ 반복을 이용한 구현 (시간복잡도 고려필요)__ https://www.acmicpc.net/problem/1018Question문제알파벳 대소문자로 된 단어가 주어지면,이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오.단, 대문자와 소문자를 구분하지 않는다.입력첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다.주어지는 단어의 길이는 1,000,000을 넘지 않는다.출력첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다.단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다. Tag구현, 문자열Answer1 (./Main.java)Map 객체의 반복문 활용 가능lamda 에서는 외부..
__💡구간합 (PrefixSum)__ 구간 합 응용 구현 문제 __ https://www.acmicpc.net/problem/10986 Question문제수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.입력첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103) 둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)출력첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.Tag수학, 구간합 (누적합)..
__💡구간합 (PrefixSum)__ 누적합을 이용한 구간합 기본 문제__ https://www.acmicpc.net/problem/10986Question문제수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.입력첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.제한$1 ≤ N ≤ 100,000$$1 ≤ M ≤ 100,000$$1 ≤ i ≤ j ≤ N$출력총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.Tag누적 합메모리(kb)시간 (ms)시간복잡도56156656$O(n)..
자바 풀이__💡구간합 (PrefixSum)__ 2차원 배열에서의 구간합 응용__ https://www.acmicpc.net/problem/10986Question문제N×N개의 수가 N×N 크기의 표에 채워져 있다.(x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.아래 표에서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고,(4, 4)부터 (4, 4)까지 합을 구하면 7이다.표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오. 012301234123452345634567입력첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다.(1 ≤ N ≤ 1024, 1 ≤ M ..
