알고리즘145 백준 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. 백준 10813 공 바꾸기 (JAVA 자바 풀이) 백준 10813 공 바꾸기 (JAVA 자바 풀이) 10810 공 넣기 문제와 마찬가지로 그대로 구현해주면 된다. 풀이에 있어서 배열 내부를 먼저 초기화해주고 할 것인지, swap 하는 과정에서 초기화할 것인지를 선택할 수 있다. 후자로 하면 마지막에 초기화하지 않은 0에 대해서도 index를 설정해준 값에 대해서 한번 작업을 해주어야 한다. 먼저 초기화해주는 것이 편하다고 판단해 그렇게 풀이했다. 💡 코드 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.stream.IntStream; publ.. 2023. 7. 2. 백준 10810 공 넣기 (JAVA 자바 풀이) 백준 10810 공 넣기 (JAVA 자바 풀이) 단순 구현 문제로서 구현해주면 된다. 범위가 전체 배열을 순회하도록 주어지면 이중 반복문이 돌면서 최대 O(n^2)까지 시간 복잡도가 높아지지만 주어지는 N,M 데이터의 최대 범위가 100으로 낮기 때문에 괜찮다. 💡 코드 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.stream.IntStream; public class Main { private static final BufferedReader bufferedReader = new Buff.. 2023. 7. 2. 이전 1 2 3 4 5 6 7 8 ··· 29 다음
