알고리즘 공부/문제 풀이
-
[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..
-
[JAVA] 백준 15684 사다리 조작알고리즘 공부/문제 풀이 2021. 10. 27. 12:10
https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이 후기 - 인덱스 처리가 힘들었다. 원래는 사다리 크기에 딱 맞는 배열을 생성하여 범위 체크해가며 풀이했는데 코드가 복잡해져서 좌우로 마진을 한칸씩 주고, 범위 체크 없이 좌우에 사다리가 있는지 없는지를 확인했다 - 나는 boolean 배열로 해당 칸에 사다리가 있다 없다를 체크했는데, 다른 코드를 보니 오른쪽으로 뻗은 사다리는 1로 왼쪽으로 뻗은 사다리는 -1로 한 코드가 많았다. 더 직관..