본문 바로가기

Algorithm/Baekjoon208

[백준] 14890: 경사로 - JAVA https://www.acmicpc.net/problem/14890 풀이구현 문제 였다. 이전 칸과 비교하여 체크해주는 문제. 높이가 이전과 같다면 지나갈 수 있고, 1 차이나면 경사로를 설치해야 한다. 경사로의 높이는 1로, 길이는 L로 고정되어 있어서 이전 칸과 1 차이날 때,  L길이의 for문을 통해 경사로를 놓을 수 있는지 탐색했다. 경사로의 바닥면의 높이가 다 같은지, 이미 설치된 경사로가 없는지 체크해 주었다. 이차원배열의 행과 열을 모두 체크해야 했다. 함수를 재사용 하기 위해 탐색할 부분을 일차원배열로 만들어 하나의 함수를 이용했다.  메모리: 15048KB시간: 144ms언어: Java 11import java.io.*;import java.util.*;public class Main .. 2024. 5. 12.
[백준] 1535: 안녕 - JAVA https://www.acmicpc.net/problem/1535 풀이DP, 배낭 문제. 인사를 할때마다 체력을 잃고 기쁨을 얻는다. 체력 100에서 시작해서 0이 되면 죽는다. dp배열을 dp[사람의 수][100] 으로 설정했다. 사람마다 잃는 체력, 얻는 기쁨을 통해 이전 dp배열과 비교해준다. 점화식은 다음과 같다.dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - L[i]] + J[i]);  메모리: 14196KB시간: 176ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2024. 5. 12.
[백준] 6198: 옥상 정원 꾸미기 - JAVA https://www.acmicpc.net/problem/6198 풀이그리디스러운 문제였다. 알고리즘 분류는 자료 구조, 스택. 자기보다 오른쪽에 있는 빌딩을 보는데 높이가 자기보다 낮은 빌딩을 볼 수 있다. 중간에 같거나 높은 빌딩을 만나면 그 다음부터 빌딩은 보지 못한다. 나는 현재 빌딩의 높이를 기준으로 이 빌딩을 볼 수 있는 왼쪽 빌딩들의 개수를 카운트했다. stack에 빌딩의 높이를 담으면서 진행하며 현재 빌딩보다 낮은 빌딩을 스택에서 빼줬다. stack의 사이즈를 답에 더해주고 현재 빌딩을 stack에 넣어주면 끝.  메모리: 24236KB시간: 324ms언어: Java 11import java.io.*;import java.util.*;public class Main { public s.. 2024. 5. 12.
[백준] 2800: 괄호 제거 - JAVA https://www.acmicpc.net/problem/2800 풀이브루트포스 문제. 괄호의 쌍을 매칭하여 출력하거나 출력 안 하거나 하면 되는 문제였다. 서로의 짝을 매칭 시킬 방법으로 여는 괄호가 나오면 스택에 넣고, 닫는 괄호가 나오면 스택의 제일 위에 있는 괄호와 짝을 맺는다. 서로의 짝의 번호를 배열에 저장했다. 짝을 모두 저장한 후 dfs 탐색을 통해 해당 괄호를 boolean 배열에 true, false로 체크하여 출력할지 안 할지를 저장했다. 중복 식을 제거하기 위해, 사전 순으로 정렬하기 위해 TreeSet을 이용했다.  메모리: 24900KB시간: 280ms언어: Java 11import java.io.*;import java.util.*;public class Main { st.. 2024. 5. 12.
[백준] 2624: 동전 바꿔주기 - JAVA https://www.acmicpc.net/problem/2624 풀이dp문제. 동전으로 특정 금액을 만드는 문제였는데 동전의 개수가 정해져있어서 어려웠다. 동전 금액과 각각의 개수가 주어지는데 동전들을 이용해서 T원을 만들어야 한다. 금액에 대해 동전 몇 개를 썼을 때 경우의 수를 저장하는 dp배열을 만들었다. 동전 * 개수를 price라고 하면 점화식은 다음과 같다. `dp[k][i + 1] += dp[k - price][i];`dp[k][i+1]은 동전 (i+1)개를 썼을 때 k의 금액을 만들 수 있는 경우의 수이다.  메모리: 18072KB시간: 164ms언어: Java 11import java.io.*;import java.util.*;public class Main { public sta.. 2024. 5. 12.
[백준] 1991: 트리 순회 - JAVA https://www.acmicpc.net/problem/1991 풀이트리, 재귀. 이진 트리가 주어지고 전위순회, 중위순회, 후위순회한 결과를 출력하면 되는 문제이다. 이진 트리는 각 노드와 왼쪽 자식 노드, 오른쪽 자식노드로 주어져 트리를 구현하여 저장해야 했다.  메모리: 14188KB시간: 124ms언어: Java 11import java.io.*;import java.util.*;public class Main { static StringBuilder sb = new StringBuilder(); static class Node { char ch; Node left; Node right; public Node(char ch) { .. 2024. 5. 12.
[백준] 12919: A와 B 2 - JAVA https://www.acmicpc.net/problem/12919 풀이문자열, 브루트포스 문제이다. A와 B로만 이루어진 단어들이 있는데 첫번째 주어지는 단어(S)로 두번째 단어(T)를 만들 수 있는지 확인하는 문제이다. 문자열을 바꿀 때는 "문자열의 뒤에 A를 추가한다", "문자열의 뒤에 B를 추가하고 문자열을 뒤집는다" 이 두가지의 연산이 가능하다. S에서 T를 만드려면 두 가지 연산을 모두 시도해야 하지만 T에서 S를 만들 때는 문자열의 뒤에 A가 있는지, 문자열의 앞에 B가 있는지 확인하여 그 경우에만 연산을 하면 된다. 문자열을 뒤집는 방법으로는 for문을 이용한 방법과 StringBuilder의 reverse를 이용한 방법이 있다. String reverse = "";for (int i = .. 2024. 5. 12.
[백준] 15686: 치킨 배달 - JAVA https://www.acmicpc.net/problem/15686 풀이브루트포스, 백트래킹문제. 치킨집 중 M개를 골라 집들과의 거리를 구한 합의 최솟값을 구하는 문제. 치킨집과 집을 리스트에 넣고 치킨집중 M개의 조합을 만들었다. 만들어진 치킨집의 조합을 이용해 집과 치킨집 거리의 최솟값들의 합을 구해주었다.  메모리: 15112KB시간: 220ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node { int r; int c; public Node(int r, int c) { this.r = r; this.c = c; .. 2024. 5. 11.
[백준] 10819: 차이를 최대로 - JAVA https://www.acmicpc.net/problem/10819 풀이브루트포스, 백트래킹문제. N정수가 주어지고 순서를 적절히 바꿔 다음 식의 최댓값을 구하는 문제였다. `|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|` 배열을 저장하고 0 ~ N-1 까지의 인덱스를 순열로 만들어 계산 후 최댓값을 구해줬다. 비트마스크를 이용해 방문처리했다.  메모리: 14944KB시간: 148ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int N, ans; static int[] arr, selected; public static void main(Strin.. 2024. 5. 11.
[백준] 3980: 선발 명단 - JAVA https://www.acmicpc.net/problem/3980 풀이브루트포스, 백트래킹문제였다. 선수들의 능력치가 주어지고, 11개의 포지션에 배치하여 최댓값을 얻어야 한다. 능력치가 0인 포지션에는 들어갈 수 없다. 1번 선수부터 포지션을 선택하면서 dfs탐색을 했다. 11번 선수까지 포지션 배정을 마치고 최대값을 정해주면 끝. 해당 포지션에 선수가 배치되었는지 방문처리를 하는 부분이 필요했는데, 비트마스크를 이용해 boolean배열을 만드는 것보다 조금 속도가 빨랐다.  메모리: 15640KB시간: 160ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int[][] arr; static int ans.. 2024. 5. 11.

티스토리툴바