본문 바로가기
반응형

전체 글123

백준 17298번 : 오큰수 java 이 문제는 자료구조 중에서 스택을 이용하여 푸는 문제입니다. 이 문제를 풀 때 해당 인덱스의 수보다 오른쪽에 있으면서 해당 수보다 큰 수 중에서 가장 왼쪽에 있는 수를 찾으면 됩니다. 이를 위해서는 입력받은 수들을 먼저 배열에 넣은 후 0번 index부터 차례대로 값을 stack에 넣습니다. 그리고 stack에 새로 들어오는 값이 이전에 있던 값보다 작다면 이전에 있던 값을 pop하지 않고 새로운 값을 add합니다. 만약 새로 들어오는 값이 이전에 있던 값보다 작다면 우리가 찾던 오큰수이므로 answer배열에 그 값을 넣어줍니다. 이 과정을 그림을 통해서 설명드리겠습니다. 예제 1번을 예시로 풀어보겠습니다. 0번 index는 stack에 비교할 값이 없기 때문에 그 값을 바로 stack에 넣어줍니다. 1.. 2022. 6. 13.
백준 2096번 : 내려가기 java 이 문제는 다이나믹 프로그래밍을 이용하여 푸는 문제입니다. 그런데 이 문제를 보시면 N이 어떤 값이 입력되든지 한 행에는 3개의 값이 들어옵니다. 이렇게 일정한 크기의 부분들에서 반복되는 작업을 할 때 우리는 이것을 더 효율적으로 하기 위해서 슬라이딩 윈도우라는 알고리즘을 사용할 수 있습니다. 슬라이딩 윈도우에 대해서 먼저 설명드리겠습니다. 다음과 같이 위 문제에서 입력값이 들어왔다고 가정해보겠습니다. 이 문제에서 입력값은 한 행의 크기가 3으로 고정되어 있기 때문에 우리는 이것을 한 행씩 처리할 수 있습니다. 1번 행을 처리하고 그 다음 행의 연산을 처리하는 식으로 고정된 크기의 영역을 처리하며 문제를 해결할 수 있습니다. 위 그림의 구간을 먼저 처리한 후 아래 그림의 과정들을 계속 처리합니다. 이 알.. 2022. 6. 13.
백준 15666번 : N과 M (12) java 이 문제는 입력된 값들을 저장하여 중복되는 수열이 출력되지 않게 비내림차순으로 출력하는 문제입니다. 이 문제를 풀 때 입력값이 중복된 값이 올 수 있다는 것을 유의해야 합니다. 따라서 저는 HashSet을 이용하여 중복된 값들을 저장하지 않고 중복되지 않은 값들로만 배열을 만들었습니다. 그 배열로 조건과 같이 출력하게 하여 문제를 해결하였습니다. 코드를 바로 보여드리도록하겠습니다. import java.io.*; import java.util.*; public class Main { static int M; static Integer[] intArr; static int[] answer; public static void main(String[] args) throws IOException{ Buffer.. 2022. 6. 12.
백준 1759번 : 암호 만들기 java 이 문제는 데이터를 입력받은 후 dfs를 이용하여 중복된 값이 나오지 않게 탐색하는 알고리즘입니다. 이 문제를 풀 때 조심해야하는 점은 모음이 1개 이상, 자음이 2개 이상 들어가야 한다는 조건입니다. 문자들을 입력받은 후 정렬하여 dfs를 실행하며 모음이 1개 이상, 자음이 2개 이상 들어 있는지 확인하면 되는 문제입니다. 바로 코드를 보여드리도록 하겠습니다. import java.util.*; import java.io.*; public class Main { static char[] charArr; static int L, C; static char[] answer; static boolean[] visited; public static void main(String[] args) throws IO.. 2022. 6. 11.
백준 14938번 : 서강그라운드 java 이 문제는 다익스트라 알고리즘을 이용하여 탐색하는 알고리즘입니다. 저는 이 문제를 처음 봤을 때 bfs로도 풀 수 있을 것 같았습니다. 그래서 bfs로 문제를 먼저 풀어보았는데 bfs로 문제를 풀 때 탐색하지 않는 부분이 있을 수 있다는 것을 알게 되었습니다. 위의 그림과 같이 그래프가 존재할 때 bfs로 이 문제를 풀면 A -> B 경로를 탐색한 후 바로 A -> C 경로를 탐색합니다. 수색 범위가 10이라고 했을 때 A->C를 통해 C 노드에 이미 접근했기 때문에 A -> B -> C 경로가 더 짧음에도 불구하고 경로가 새로 생성되지 않습니다. 따라서 A -> B -> C -> D 경로로 가면 총 거리가 6이기 때문에 탐색할 수 있는 노드이지만 bfs를 이용하면 탐색할 수 없게 됩니다. 따라서 다익스.. 2022. 6. 11.
백준 15657번 : N과 M (8) java 이 문제는 입력을 받은 후 정렬하고 dfs를 이용하여 조건에 맞게 출력하는 문제입니다. 예제 2번을 예시로 그림을 통해 이 문제를 설명해드리도록 하겠습니다. 위의 그림은 예제 2번에 맞게 N크기의 배열과 M 크기의 배열을 만들었습니다. M 배열에 들어있는 자료들이 출력될 값입니다. 위 그림과 같이 M배열의 첫 번째에 들어갈 자료는 초록색 박스로 두 번째에 들어갈 자료는 빨간색 박스로 표시하였습니다. 이제 출력이 어떻게 되는지 계속해서 보여드리겠습니다. 초록색 박스가 N배열의 첫번째 칸을 가리킬 때는 이렇게 진행이 됩니다. 이제 초록색 박스를 N배열의 두 번째 칸으로 옮겨보겠습니다. 그럼 위의 그림과 같이 초록색 박스가 시작되는 지점부터 빨간색 박스도 시작합니다. 계속 진행시켜보도록 하겠습니다. 초록색 박.. 2022. 6. 10.
백준 11725번 : 트리의 부모 찾기 java 이 문제는 루트 노드가 정해져 있으니 루트 노드로부터 시작하여 간선들을 bfs를 이용하여 만나는 노드들을 조건에 맞게탐색하는 문제입니다. 저는 이 문제를 해결하기 위해 N개의 ArrayList를 List안에 넣어서 각각의 자리를 노드의 시작점으로 사용하였습니다. 그리고 1번 노드가 루트 노드이니 루트 노드에서 시작하여 연결된 간선들에 부모 노드를 입력하면서 진행하였습니다. 코드를 보여드리도록 하겠습니다. import java.util.*; import java.io.*; public class Main { static List l; static int[] answer; public static void main(String[] args) throws IOException{ BufferedReader br.. 2022. 6. 10.
백준 17144번 : 미세먼지 안녕! java 이 문제는 조건에 따라서 미세먼지를 확산시킨 후 공기청정기를 작동시키는 문제입니다. 저는 이 문제를 확산시키는 함수와 공기청정기에 의해서 미세먼지들이 이동하는 함수로 나누어 풀었습니다. 우선 확산시키는 함수는 map배열을 검사하며 미세먼지의 농도가 5 이상일 때만 ArraList에 입력했습니다. 그 후 ArrayList에 있는 데이터들을 꺼내서 그 주변으로 확산시켰습니다. 미세먼지의 농도가 5 이상일 때 바로 확산시키지 않은 이유는 바로 확산시킨다면 확산된 미세먼지가 주변에 영향을 주어서 제대로 정답을 구하기 어렵기 때문입니다. 그 후 미세먼지들을 이동시키는 함수를 실행시켰습니다. 코드를 보면 이해하실 수 있으실 겁니다. import java.util.*; import java.io.*; public c.. 2022. 6. 9.
반응형

티스토리툴바