알고리즘/백준118 백준 2295 세 수의 합 (JAVA 자바 풀이) 백준 2295 세 수의 합 (JAVA 자바 풀이) 문제의 요구사항을 그대로 구현하여 모든 경우의 수를 탐색하는 방식은 다음과 같을 것이다. for (int i =0; i 시간 복잡도 O(n^2 * nlogn) 💡 코드 구현 import java.io.. 2023. 7. 4. 백준 14425 문자열 집합 (이분 탐색을 이용한 JAVA 자바 풀이) 백준 14425 문자열 집합 (이분 탐색을 이용한 JAVA 자바 풀이) https://www.acmicpc.net/problem/14425 이분 탐색을 이용한 풀이이다. N개의 문자열로 이루어진 집합 S에서 M개의 문자열 중 집합 S에 속하는 문자열의 개수를 구해야 한다. 자바의 컬렉션 Set의 contains 메서드를 이용하면 간단하게 풀 수 있지만 바이너리 서치를 직접 구현해 풀어보기 좋은 문제여서 바이너리 서치를 이용해 풀어보았다. 먼저 문자열을 sort 해준다. String[] strings = new String[N]; while(N-->0){ strings[N] = bufferedReader.readLine(); } Arrays.sort(strings); -> 시간 복잡도 O(nlogn) 문자.. 2023. 7. 3. 백준 17232 생명 게임 (JAVA 자바 풀이) | 누적합 배열 백준 17232 생명 게임 (JAVA 자바 풀이) 초기 제출 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] args) throws IOException { StringTokenizer stringTokenizer = new StringTok.. 2023. 7. 3. 백준 19951 태상이의 훈련소 생활 (JAVA 자바 풀이) 백준 19951 태상이의 훈련소 생활 (JAVA 자바 풀이) https://www.acmicpc.net/problem/19951 문제에서 설명하듯이 주어지는 조교의 쿼리를 모두 다 받아놓고 한번에 연산을 해주어야 한다. 문제에서 N, M의 조건이 최대 10만이기 때문에 반복문 두번이면 O(n^2)으로 1초를 넘어서게 될 것이 분명하다. 누적합을 이용해 풀이해야 한다. 문제는 누적합을 어떻게 설계할 것이냐이다. 만약 누적합이라고 하여, 또 M번의 쿼리를 그대로 모든 배열에 넣는 방식을 사용하면 N이 10만 건으로 주어질 경우 배열의 10만 개의 칸을 순회해야 한다. 즉, 앞에서 모든 계산을 받자마자 그대로 하는 것과 다를 바가 없어진다. 따라서 이 부분의 시간 복잡도를 O(M)으로 유지할 수 있어야 한다... 2023. 7. 2. 백준 10811 바구니 뒤집기 (JAVA 자바 풀이) 백준 10811 바구니 뒤집기 (JAVA 자바 풀이) 1차원 배열을 연습하는 문제로서 지난 문제 10813 공바꾸기를 좀 더 응용한 문제이다. swap과 reverse를 수행해주면 된다. reverse는 새로운 배열을 만들어서 전체를 새롭게 할당하는 방법도 있지만 처음과 끝을 하나씩 바꿔주는 방식으로 수행할 수도 있다. 이때 while문과 for문 방식 두가지 모두 사용할 수 있다. 둘다 반복 횟수는 길이 + 1를 2로 나눈 몫으로 구한다. while문을 사용하면 별도의 카운트 변수를 두어 처음과 끝에서부터 증감을 표현해준다. for문을 사용하면 i 변수를 사용할 수 있다. 💡 코드 구현 import java.io.BufferedReader; import java.io.IOException; import.. 2023. 7. 2. 이전 1 2 3 4 5 6 7 ··· 24 다음
