자바
-
[JAVA] 백준 16638 괄호 추가하기 2카테고리 없음 2021. 11. 16. 20:48
https://www.acmicpc.net/problem/16638 16638번: 괄호 추가하기 2 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 괄호 추가하기 문제와 다른 것은 연산자들의 우선순위가 생겼다는 점! 이전 문제에서는 바로바로 값을 구해서 넘겨주었지만, 이번 문제에서는 괄호를 넣어준 스트링을 구하고 그 스트링을 후위표기법으로 바꾸면서 계산하는 방법으로 하였다 주어지는 식에 괄호를 추가하는 식의 String 연산을 진행하기 때문에 StringBuilder를 이용했다. 살짝 후위표기법으로 변환하는 코드가 마음에 ..
-
[JAVA] 백준 3020 개똥벌레알고리즘 공부/문제 풀이 2021. 11. 14. 13:51
https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 처음에는 단순히 이중 포문을 생각했고, 시간초과가 날 것 같아서 어떻게 풀어야 할까 고민을 했다.. 누적합을 이용해야 하는 문제임을 알았음에도! (문제 유형 훔쳐봄) 어떻게 이용해야 할지 감이 오지 않았다... 결국,, 블로그 참고 (요즘 혼자 해결하는 문제가 많이 적어진 것 같다 흑흑) 내가 처음 생각한 이중 포문은 높이 크기의 배열을 만들어서 높이가 h인 장애물이 들어온다 => 1~h 까지 반복문..
-
[JAVA] 백준 2213 트리의 독립집합알고리즘 공부/문제 풀이 2021. 11. 9. 21:32
https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net - 어려웠다.. 결국 블로그의 도움을 받아 해결하였다 - 트리의 구조 -> 어느 정점이든 루트가 될 수 있다 -> 편의상 1번 정점을 루트로 생각하고 1번 노드부터 dfs 탐색을 진행한다 - 현재 접근한 노드를 포함할 때/포함하지 않을 때의 최대 독립 집합의 가중치를 구해본다 => memo[N][2] - 현재 노드를 집합에 포함한다면, 인접한 다음 노드는 포함되지 ..
-
[JAVA] 백준 16637 괄호 추가하기알고리즘 공부/문제 풀이 2021. 11. 5. 23:34
https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = Integer.parseInt(sc.nextLine()); str = sc.nextLine().toCharArray(); op = N/2; choice(0, str[0]..
-
[JAVA] 백준 2473 세 용액알고리즘 공부/문제 풀이 2021. 11. 4. 22:40
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net - 처음에는 조합이나 백트래킹을 떠올렸는데 5000이라는 범위가 시간초과가 날 것 같았다. - 투포인터는 O(N)으로 두 가지를 고를 수 있다는 것을 알고, 한가지 용액과 나머지 두 용액을 고르는 것으로 문제를 해결하였다. - 처음에는 투 포인터를 전체 범위에 대해 진행하였지만, i+1 ~ N-1에 대해서만 두 용액을 찾으면 된다는 것을 뒤늦게 깨달았다. 왜냐하면 이미 한 용..
-
[JAVA] 백준 16168 퍼레이드알고리즘 공부/문제 풀이 2021. 11. 2. 10:08
https://www.acmicpc.net/problem/16168 16168번: 퍼레이드 첫 번째 줄에 지점의 개수 V, 연결 구간의 개수 E가 주어진다. (1 ≤ V ≤ E ≤ 3000) 이후 E개의 줄에 걸쳐 각 연결 구간이 연결하는 두 지점의 번호 Va, Vb가 공백을 사이에 두고 주어진다. (1 ≤ Va, www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer..
-
[JAVA] 백준 1944 복제 로봇알고리즘 공부/문제 풀이 2021. 10. 31. 13:24
https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static class Node implements Comparable{ int row, col; int dist; public Node(int r, int c, int d){ row = r; col = c; dist = d; } public int c..