문제풀이/백준
-
[백준]2887: 행성 터널 - JAVA문제풀이/백준 2021. 2. 16. 18:57
[백준]2887: 행성 터널 www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 MST유형의 문제로, 모든 간선의 정보를 만들어서 그 중에 작은 간선을 선택하면서 최소 간선을 찾을 수 있게 kruskal 알고리즘을 사용하여 구현하였다. 행성의 정보를 입력받을때 이차원배열을 사용하여 2중 반복문으로 모든 노드의 거리의 최솟값을 구해 q에 넣어주었더니 메모리 초과가 났다. 행성의 정보를 저장하는 class를 따로 구현해주었고 x..
-
[백준]1922: 네트워크 연결문제풀이/백준 2021. 2. 16. 16:52
[백준]1922: 네트워크 연결 www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 어제 MST를 공부한 기념으로 MST문제를 풀어보았다! MST는 prim알고리즘과 kruskal알고리즘으로 풀 수 있다. 두 알고리즘을 모두 사용하여 문제를 풀어보았다. 이번 문제는 변형 1도 없이 MST알고리즘만 쓰면 답이 나온다! 코드 prim algorithmn 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 ..
-
[백준]1766: 문제집 - JAVA문제풀이/백준 2021. 2. 15. 15:21
[백준]1766: 문제집 www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 어제 위상정렬 공부한 기념으로 위상정렬 문제를 풀어보았다. 이 문제는 위상정렬 문제를 풀 줄 안다면 기본적인 개념을 이해하는데 어렵지 않다. 그러나 여기서 중요한 점은 문제 풀 순서의 조건중 3번인 가능한 쉬운 문제부터 풀어야 한다는 점이다. 예를들어서 예제입력을 보면, 4 -> 2, 3 -> 1순서대로 문제를 풀어야하고 3, 4의 진입간선이 모두 0..
-
[백준]10026: 적록색약 - JAVA문제풀이/백준 2021. 2. 14. 18:03
[백준]10026: 적록색약 www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 탐색 문제로 dfs, bfs로 둘다 풀어도 될 듯하다. 적록색약이 아닌 사람이 봤을 때의 구역의 수는 일반적인 dfs와 똑같고, 적록색약인 사람의 구역의 수를 구할 때는 R, G인 값을 같다고 생각하고 체크해주었다. 이정도는 이제 어렵지 않다! 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26..
-
[백준]1939: 중량제한 - JAVA문제풀이/백준 2021. 2. 14. 15:56
[백준]1939: 중량제한 - JAVA www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 풀이 이 문제는 이분탐색 문제이며 이전에 풀었던 프로그래머스의 징검다리 건너기 문제와 비슷했다. 처음에는 인접행렬을 사용해서 풀었더니 메모리 초과가 났다. 그래서 다시 인접리스트로 바꾸어 풀어주었다. 이런 문제는 항상 인접행렬로 풀다보니 인접리스트르 바꾸는데 시간이 오래 걸렸다. 인접행렬은 N*N의 메모리 공간을 사용하므로 ..
-
[백준]17136: 색종이 붙이기 - JAVA문제풀이/백준 2021. 2. 13. 17:10
[백준]17136: 색종이 붙이기 - JAVA www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 풀이 완전 탐색을 통해서 풀어야 하는 구현 문제이다. 이번 문제는 풀고나니 어렵지 않았는데 구현하면서 생각해 줘야 하는 조건들을 놓쳐 다시 구현하느라 시간이 오래 걸렸다. 구현 문제는 꼭꼭 문제를 정확히 읽고 조건을 하나라도 빠트리지 않는 것이 가장 중요하다! 탐색 방향은 오른쪽 아래로만 확인하면 되므로 탐색할 때 x, y좌표 값에 따라 이동 방향을 지정해..
-
[백준]2225: 합분해 - JAVA문제풀이/백준 2021. 2. 12. 17:01
[백준]2225: 합분해 www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 (dp는 너무 어려워..휴우) dp함수를 이차원 배열을 사용하여 표현하였다. 각각의 인덱스는 dp[n][k]일때 0부터 n까지의 정수로 k를 표현할 수 있는 경우의 수를 저장하도록 하였다. 우선 예제입력인 20,2의 경우의 수를 모두 찾아 보았다. 0, 20 20, 0 1, 19 19, 1 2, 18 18, 2 3, 17 17, 3 4, 16 16, 4 5, 15 15, 5 6, 14 14, 6 7, 13 13, 7 8, 12 12, 8 9, 11 11, 9 10, 10 더하는 순서가 다르면 다른 경우로 계..
-
[백준]1759: 암호 만들기 - JAVA문제풀이/백준 2021. 2. 11. 20:55
[백준]1759: 암호 만들기 www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 순열을 사용한 백트랙킹문제! 결과가 사전 순서대로 저장되어야 하므로 sort를 해주었다. 그리고 값을 뽑을때 알파벳이 증가하는 순서대로만 뽑아야 하므로 compareTo 메소드를 사용하여 이전의 뽑은 값과 비교해 주었다. 또한 모음인지 체크하는 함수를 만들어 주었고 조건에 모든 문자를 다 뽑은 후에는 모음의 수, 자음의 수가 조건에 맞는지 확인한 후 맞다면 출력하도록 해주었다. 별..