Baekjoon
-
이번 문제는 N의 범위가 1000까지이므로 버블정렬을 사용해도 된다. 시간 복잡도가 O(n2)이어도 1,000,000이기에 상관이 없다. 버블정렬은 인접한 값을 비교한 후 정렬을 하는 방식으로 교환이 매우 자주 일어난다. 따라서 N의 범위가 크면 사용하기 어려운 알고리즘이다. 아래 코드를 보자. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); ..
[백준] 정렬 - 2750_수 정렬하기 Java[자바]이번 문제는 N의 범위가 1000까지이므로 버블정렬을 사용해도 된다. 시간 복잡도가 O(n2)이어도 1,000,000이기에 상관이 없다. 버블정렬은 인접한 값을 비교한 후 정렬을 하는 방식으로 교환이 매우 자주 일어난다. 따라서 N의 범위가 크면 사용하기 어려운 알고리즘이다. 아래 코드를 보자. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); ..
2024.02.07 -
이번 문제는 우선순위 큐를 이용하는 문제이다. Comparable과 Comparator라는 인터페이스가 있다. 이 두 개의 인터페이스는 두 값을 비교해 어떠한 기준으로 정렬을 시키는 인터페이스이다. 그래서 이 인터페이스를 이용하여 정렬을 한 후 큐에서 poll() 메소드를 사용하면 된다. 필자는 Comparator라는 인터페이스를 사용했는데 compare라는 메소드를 오버라이딩하여 사용하면 된다. 우리가 생각해야할 기준은 두 가지이다. 먼저 절댓값이 서로 다를 때. 절댓값이 서로 다르면 어느 하나의 절댓값이 더 크다는 소리다. 절댓값이 더 큰 수가 뒤로 배치되어야 한다. 절댓값이 같으면 원래의 수가 더 작은 것이 앞에와야한다. 이 두가지를 생각하고 로직을 짜면 된다. 아래 코드를 보자. import ja..
[백준] 스택, 큐 - 11286_절댓값 힙 Java[자바]이번 문제는 우선순위 큐를 이용하는 문제이다. Comparable과 Comparator라는 인터페이스가 있다. 이 두 개의 인터페이스는 두 값을 비교해 어떠한 기준으로 정렬을 시키는 인터페이스이다. 그래서 이 인터페이스를 이용하여 정렬을 한 후 큐에서 poll() 메소드를 사용하면 된다. 필자는 Comparator라는 인터페이스를 사용했는데 compare라는 메소드를 오버라이딩하여 사용하면 된다. 우리가 생각해야할 기준은 두 가지이다. 먼저 절댓값이 서로 다를 때. 절댓값이 서로 다르면 어느 하나의 절댓값이 더 크다는 소리다. 절댓값이 더 큰 수가 뒤로 배치되어야 한다. 절댓값이 같으면 원래의 수가 더 작은 것이 앞에와야한다. 이 두가지를 생각하고 로직을 짜면 된다. 아래 코드를 보자. import ja..
2024.02.07 -
이번 문제는 큐의 자료구조를 파악하는 문제이다. 큐는 First In First Out으로 처음 넣는 값을 처음으로 뺄 수 있는 자료구조이다. 그래서 이번 문제는 어렵지 않다고 볼 수 있다. 주어진 숫자만큼 큐에 넣어준다. 예를 들어 6이면 1 2 3 4 5 6 순서로 큐에 넣어준다. 여기서 1을 poll() 메소드로 꺼내오고 2를 6뒤에 붙이려면 que.add(que.poll())의 형식으로 붙일 수 있다. 이 과정을 큐 안에 데이터가 하나만 남을 때까지 반복하면 쉽게 답을 구할 수 있다. 아래 코드를 보자. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOExc..
[백준] 스택, 큐 - 216_카드 2 Java[자바]이번 문제는 큐의 자료구조를 파악하는 문제이다. 큐는 First In First Out으로 처음 넣는 값을 처음으로 뺄 수 있는 자료구조이다. 그래서 이번 문제는 어렵지 않다고 볼 수 있다. 주어진 숫자만큼 큐에 넣어준다. 예를 들어 6이면 1 2 3 4 5 6 순서로 큐에 넣어준다. 여기서 1을 poll() 메소드로 꺼내오고 2를 6뒤에 붙이려면 que.add(que.poll())의 형식으로 붙일 수 있다. 이 과정을 큐 안에 데이터가 하나만 남을 때까지 반복하면 쉽게 답을 구할 수 있다. 아래 코드를 보자. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOExc..
2024.02.07 -
이번 문제는 스택을 사용하는 문제이다. 스택에 인덱스를 넣어주며 활용을 하면 되는데 예시를 들어서 설명을 하면 편할 것 같다. 3 2 5 8 이라는 배열이 있다고 하자. 스택에 먼저 첫 인덱스인 0을 넣어준다. stack.push(0) 그 후 반복문을 돌며 해당 인덱스에 해당하는 값보다 더 큰 값을 찾으면 된다. arr[stack.peek()] == arr[0] == 3 이고 저 값보다 더 큰 값을 가지는 것은 arr[1] == 5이다. while(arr[stack.peek()] < arr[i]) { result[stack.pop()] = arr[i] } 로 표현할 수 있는데 배열을 하나하나 조사하며 해당 값보다 더 큰 값이 나오면 해당 값까지의 오큰수를 모두 arr[i]로 설정하는 것이다. 아래 자세한..
[백준] 스택, 큐 - 17298_오큰수 Java[자바]이번 문제는 스택을 사용하는 문제이다. 스택에 인덱스를 넣어주며 활용을 하면 되는데 예시를 들어서 설명을 하면 편할 것 같다. 3 2 5 8 이라는 배열이 있다고 하자. 스택에 먼저 첫 인덱스인 0을 넣어준다. stack.push(0) 그 후 반복문을 돌며 해당 인덱스에 해당하는 값보다 더 큰 값을 찾으면 된다. arr[stack.peek()] == arr[0] == 3 이고 저 값보다 더 큰 값을 가지는 것은 arr[1] == 5이다. while(arr[stack.peek()] < arr[i]) { result[stack.pop()] = arr[i] } 로 표현할 수 있는데 배열을 하나하나 조사하며 해당 값보다 더 큰 값이 나오면 해당 값까지의 오큰수를 모두 arr[i]로 설정하는 것이다. 아래 자세한..
2024.02.07 -
이번 문제는 스택이 어떤 자료구조인지를 파악하는 문제였다. 스택은 Last in, First out으로 제일 먼저 넣은 값이 제일 마지막에 나오는 자료구조이다. 그래서 입력된 값을 기준으로 1부터 순차적으로 stack에 넣은 뒤 입력된 값이 stack에 들어가는 값보다 작으면 그 때 stack에서 pop() 메소드를 사용해 배열을 완성시켜 간다. 그리고 입력되는 값이 stack의 젤 마지막에 들어간 값보다 작으면 NO를 반환하고 그렇지 않으면 pop() 메소드를 사용해 배열을 마저 완성시키면 된다. 아래 코드를 참고하자. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws..
[백준] 스택, 큐 - 1874_스택 수열 Java[자바]이번 문제는 스택이 어떤 자료구조인지를 파악하는 문제였다. 스택은 Last in, First out으로 제일 먼저 넣은 값이 제일 마지막에 나오는 자료구조이다. 그래서 입력된 값을 기준으로 1부터 순차적으로 stack에 넣은 뒤 입력된 값이 stack에 들어가는 값보다 작으면 그 때 stack에서 pop() 메소드를 사용해 배열을 완성시켜 간다. 그리고 입력되는 값이 stack의 젤 마지막에 들어간 값보다 작으면 NO를 반환하고 그렇지 않으면 pop() 메소드를 사용해 배열을 마저 완성시키면 된다. 아래 코드를 참고하자. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws..
2024.02.07 -
이번 최솟값 찾기 문제는 DNA 비밀번호 문제와 비슷하지만 살짝 다른 문제이다. DNA 비밀번호는 슬라이딩 윈도우 배열의 크기가 일정하게 유지가 되었다면 이번 문제의 배열의 크기는 일정하게 유지되는 것이 아닌 변한다는 점이다. 여기서는 Deque를 사용하여 슬라이딩 윈도우 알고리즘을 사용할 것이다. 먼저 Deque는 Que 종류 중 하나로 Que의 양쪽으로 엘리먼트의 삽입과 삭제가 가능한 자료구조이다. 문제 해결 방법에 대해 말을 해보면 Deque에 현재 들어갈 값의 index와 value를 가진 객체를 넣어준다. 그 다음 들어갈 값의 value가 현재 들어가있는 마지막 값의 value보다 작으면 현재 들어가있는 마지막 값을 지우고 다음 들어갈 값을 Deque에 넣어준다. 여기서 최솟값을 조회하는 인덱스..
[백준] 슬라이딩 윈도우 - 11003_최솟값 찾기 Java[자바]이번 최솟값 찾기 문제는 DNA 비밀번호 문제와 비슷하지만 살짝 다른 문제이다. DNA 비밀번호는 슬라이딩 윈도우 배열의 크기가 일정하게 유지가 되었다면 이번 문제의 배열의 크기는 일정하게 유지되는 것이 아닌 변한다는 점이다. 여기서는 Deque를 사용하여 슬라이딩 윈도우 알고리즘을 사용할 것이다. 먼저 Deque는 Que 종류 중 하나로 Que의 양쪽으로 엘리먼트의 삽입과 삭제가 가능한 자료구조이다. 문제 해결 방법에 대해 말을 해보면 Deque에 현재 들어갈 값의 index와 value를 가진 객체를 넣어준다. 그 다음 들어갈 값의 value가 현재 들어가있는 마지막 값의 value보다 작으면 현재 들어가있는 마지막 값을 지우고 다음 들어갈 값을 Deque에 넣어준다. 여기서 최솟값을 조회하는 인덱스..
2024.02.07 -
슬라이딩 윈도우는 창문이 열리듯 같은 범위를 유지하며 한 칸씩 이동하면서 값을 찾는 알고리즘이다. 이 문제는 초기 구간을 설정한 뒤 한 칸씩 이동을 하며 값을 찾으면 되는 문제이다. 0부터 P까지 반복문을 돌며 초기 문자열이 비밀번호에 부합하는지 확인 후 한 칸씩 이동하며 값을 찾아내면 된다. 초기 최소 개수를 설정을 해줄 때에 최소 개수가 0이면 count를 하나씩 증가 시켜줘야 값이 달라지지 않는다. 아래 코드를 보자. import java.util.*; import java.io.*; public class Main { static int count; static int[] myArr; static int[] checkArr; public static void main(String[] args) t..
[백준] 슬라이딩 윈도우 - 12891_DNA 비밀번호 Java[자바]슬라이딩 윈도우는 창문이 열리듯 같은 범위를 유지하며 한 칸씩 이동하면서 값을 찾는 알고리즘이다. 이 문제는 초기 구간을 설정한 뒤 한 칸씩 이동을 하며 값을 찾으면 되는 문제이다. 0부터 P까지 반복문을 돌며 초기 문자열이 비밀번호에 부합하는지 확인 후 한 칸씩 이동하며 값을 찾아내면 된다. 초기 최소 개수를 설정을 해줄 때에 최소 개수가 0이면 count를 하나씩 증가 시켜줘야 값이 달라지지 않는다. 아래 코드를 보자. import java.util.*; import java.io.*; public class Main { static int count; static int[] myArr; static int[] checkArr; public static void main(String[] args) t..
2024.02.04 -
이번 문제는 살짝 헤맸다.. 먼저 어떤 식으로 풀어갈지 생각을 하고나서 풀었어야 했는데 너무 무턱대고 문제부터 풀어서 생각이 잠시 멈췄나보다..ㅎ 어찌어찌 책을 참고하며 풀었다. 일단 이번 문제도 투 포인터 방식으로 푸는 문제였다. 먼저 주어진 숫자를 배열에 넣은 뒤 오름차순 정렬을 해주는 것부터가 시작이다. 그리고 반복문을 돌며 배열에서 하나의 값을 찾아낸 뒤 투 포인터로 두 숫자의 합과 같은 것을 고르면 된다. 여기서 중요한 점은 투 포인터에 해당하는 인덱스가 처음 고른 인덱스와 같으면 서로 다른 두 수의 합이 아니므로 주의해야한다. 필자는 여기서 헤맸다..ㅎㅎ 아래 코드를 한번 보자 import java.io.*; import java.util.*; public class Main { public ..
[백준] 투 포인터 - 1253_좋다 Java[자바]이번 문제는 살짝 헤맸다.. 먼저 어떤 식으로 풀어갈지 생각을 하고나서 풀었어야 했는데 너무 무턱대고 문제부터 풀어서 생각이 잠시 멈췄나보다..ㅎ 어찌어찌 책을 참고하며 풀었다. 일단 이번 문제도 투 포인터 방식으로 푸는 문제였다. 먼저 주어진 숫자를 배열에 넣은 뒤 오름차순 정렬을 해주는 것부터가 시작이다. 그리고 반복문을 돌며 배열에서 하나의 값을 찾아낸 뒤 투 포인터로 두 숫자의 합과 같은 것을 고르면 된다. 여기서 중요한 점은 투 포인터에 해당하는 인덱스가 처음 고른 인덱스와 같으면 서로 다른 두 수의 합이 아니므로 주의해야한다. 필자는 여기서 헤맸다..ㅎㅎ 아래 코드를 한번 보자 import java.io.*; import java.util.*; public class Main { public ..
2024.02.04