Junior-Developer

1일 1커밋! 1일 1 백준!

문제풀이/백준oj

https://www.acmicpc.net/problem/15991 15991번: 1, 2, 3 더하기 6 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 DP를 이용해서 문제를 해결했습니다. DP[N] = 조건에 맞춰서 N을 만드는 경우의 수 입니다. 먼저 차근차근 규칙을 찾아가봅시다 1 = 1 2 = 1+1 / 2 3 = 1+1+1 / 3 4 = 1+1+1+1 / 2+2 5 = 1+1+1+1+1 / 1+3+1 6 = 1+1+1+1+1+1 / 1+2+2+1 / 1+1+2+1+1 / 2+2+2 / 3+3 6을 기준으로 규칙을 살펴보면 1+(조건에 맞게 4를 만드는 경우)+1 => 1+(1+1+1..

2023. 1. 2.

문제풀이/백준oj

https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 풀이 먼저 그래프를 루트를 기준으로 dfs를 돌며 " 해당 노드를 루트로 하는 서브트리를 구성하는 노드의 개수" 를 구해줍니다. 문제의 예를 들어보겠습니다. 이렇게 DFS를 돌며 개수들을 모두 구해 저장한 뒤, 쿼리에 맞는 답을 출력하면 됩니다. 시간복잡도 DFS과정 = O(N) 쿼리 하나당 시간복잡도 = O(1) 따라서 모든 시간복잡..

2023. 1. 2.

문제풀이/백준oj

https://www.acmicpc.net/problem/19542 19542번: 전단지 돌리기 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민 www.acmicpc.net 풀이 먼저 시작점을 루트라고 생각하고 트리라고 생각해봅니다. 모든 노드를 기준으로 하는 서브트리의 최대 깊이를 구해줍니다. 그런 뒤, 시작지점 (루트) 를 기준으로 DFS를 돌며 거리를 구해줍니다. 1. 먼저 현재의 노드를 기준으로한 서브트리의 최대 깊이가 D와 같거나 작다면, 해당 노드에서는 이동할 필요가 없습니다. 2. 1번이 아닌 경우에는 다음과 같이 구해줍니다. 현재 노드를 시작점(루트)로 하..

2023. 1. 2.

문제풀이/백준oj

https://www.acmicpc.net/problem/2160 2160번: 그림 비교 N(2 ≤ N ≤ 50)개의 그림이 있다. 각각의 그림은 5×7의 크기이고, 두 가지 색으로 되어 있다. 이때 두 가지의 색을 각각 ‘X’와 ‘.’으로 표현하기로 하자. 이러한 그림들이 주어졌을 때, 가장 비 www.acmicpc.net 풀이 5*7 사이즈의 격자판이 최대 50개이기 때문에 모든 그림을 하나하나 비교해도 시간초과가 나지 않을것입니다. 하지만 5*7사이즈의 격자판을 비교하는 시간을 줄이기 위해 비트연산자 XOR을 이용했습니다. 예를들어 ..X.... .XXX... .XX.... .....X. .X...X. 와 같은 격자판을 일자로 늘려 ..X.....XXX....XX.........X..X...X. 로..

2023. 1. 2.

문제풀이/백준oj

https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 풀이 일반적으로 BFS를 이용하여 문제를 푸는데 주의해야할 것이 있습니다. 한 칸이 아닌 직사각형을 움직이기 때문에 직사각형 범위내에 1이 있는지를 확인해야하는데, 여까지 완전탐색을 진행한다면 Time Out이 날것입니다. 따라서 이 로직을 줄여야 하는데, 여기서 누적합을 이용하여 문제를 해결해주면 시간복잡도를 줄일 수 있습니다. 예를들어 0 0 0 0 0 0 0 1 0 ..

2022. 12. 31.

문제풀이/백준oj

https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 풀이 모든 경우의수를 다 대입해서 탐색했습니다. 순서에 대한 모든 경우를 결정한 뒤, 결정된 배열의 각 층을 모두 돌려서 모든 경우를 구한 뒤, BFS를 통해 최소경로를 찾았습니다. 이때 어차피 모든 경우의 수를 다 탐색하기때문에, 임의로 입구를 (0,0,0), 출구를 (4,4,4)로 고정해도 문제가 해결됩니다. 시간복잡도 순서를 정하는 경우의 수 O(5!), 각 순서를 정한..

2022. 12. 31.

문제풀이/백준oj

https://www.acmicpc.net/problem/18511 18511번: 큰 수 구성하기 첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3) 둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 www.acmicpc.net 풀이 기본적인 완전탐색 알고리즘을 이용한 문제입니다. 만들 수 있는 모든 수를 DFS를 이용하여 만들어주며, N값보다 작을때 Answer를 갱신시켜주며 진행하였습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.ut..

2022. 12. 28.

문제풀이/백준oj

https://www.acmicpc.net/problem/21943 21943번: 연산 최대로 $N$개의 양의 정수 $X_{i}$와 곱하기 연산자, 더하기 연산자가 총 $N - 1$개가 존재하고 괄호는 무수히 많이 사용해도 된다. 이 연산에는 곱하기 연산자와 더하기 연산자의 우선순위가 동일하다. www.acmicpc.net 풀이 백트래킹을 이용하여 모든 경우의수를 구해주었습니다. 이때 만약 곱셈이 2개가 있다면, 아래와 같이 3개의 그룹을 생성해준 뒤, 곱해주며 갱신하는 방식으로 백트래킹을 진행했습니다. 시간복잡도 백트래킹의 시간복잡도이고, N개 각각 최대 N-1개의 선택지가 있기때문에 O(N^(N-1)) 이 됩니다. 코드 import java.io.BufferedReader; import java.io..

2022. 12. 28.