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/18232 18232번: 텔레포트 정거장 첫 번째 줄에 정수 N, M이 공백으로 구분되어 주어진다. (2 ≤ N ≤ 300,000, 0 ≤ M ≤ min(N×(N-1)/2, 300,000)) 두 번째 줄에 정수 S, E가 공백으로 구분되어 주어진다. (1 ≤ S, E ≤ N, S ≠ E) 그 다음 줄부터 M www.acmicpc.net 풀이 먼저 입력을 받으면서 텔레포트 정거장을 그래프를 이용해서 연결해주었습니다. 그런 뒤, S부터 시작하며 BFS를 실행하여 E까지의 최단거리를 구했습니다. 1. 해당 정거장이 텔레포트 정거장이면, 연결된 정거장들을 통해 최단거리를 비교하며 진행합니다. 2. 다음정거장이 범위안에 있으면, 최단거리를 비교하며 진행합니..

2022. 12. 18.

문제풀이/백준oj

https://www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주어진다. www.acmicpc.net 풀이 간단한 DP문제입니다. DP[N] = 2*N의 타일을 배치할 수 있는 경우의 수라고 한다면, 아래의 설명과 같은 논리로 인해 일반식이 완성이 됩니다. 1. 2*N의 타일은 2*(N-1)의 타일에 2*1타일을 세로로 배치하면 되기때문에 DP[N-1]일때의 개의 경우의 수가 생깁니다. 2. 2*N의 타일은 2*(N-2)의 타일에 2*1 타일 두개를 나란히 가로로, 세로로 배치하거나 2*2 타일을 배치하면 되기때문에 DP[N-2] * 3의 경우의 수가 생깁니다. 3. 하지만 ..

2022. 12. 15.

문제풀이/백준oj

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 가장 기본적인 BFS문제이다. 그림을 만나면 해당 그림에 대한 BFS 탐색을 실시하며 넓이를 구해주고, 최대 넓이를 갱신해주면 된다. 시간복잡도 최악으로 모든 원소를 탐색하기 때문에 O(NM)이 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.ut..

2022. 12. 13.

문제풀이/백준oj

https://www.acmicpc.net/problem/13022 13022번: 늑대와 올바른 단어 첫째 줄에 단어가 주어진다. 단어는 w, o, l, f로만 이루어져 있으며, 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 'w' = 0, 'o' = 1, 'l' = 2, 'f' = 3 으로 인덱스를 정해준 뒤, 문자열을 탐색하면서 조건을 확인해주었습니다. 이전 알파벳의 인덱스 == 현재 알파벳의 인덱스 이 경우에는 해당 인덱스의 cnt를 갱신시켜 줍니다. 이전 알파벳의 인덱스+1 == 현재 알파벳의 인덱스 이 경우에는, 이전 알파벳의 인덱스를 갱신시켜주고, 현재 알파벳의 개수를 갱신시켜줍니다. 현재 알파벳이 w인경우(새로운 wolf의 시작점인 경우) 현재까지 나온 w,o,l,f의 개수가..

2022. 12. 6.

문제풀이/백준oj

https://www.acmicpc.net/problem/13413 13413번: 오셀로 재배치 로봇을 좋아하는 세희는 로봇동아리에서 카메라와 센서, 라즈베리 파이, 집게발을 이용해 로봇을 완성하였다. 이 로봇을 통해서 오셀로 재배치라는 작업을 하려고 한다. 오셀로 말은 앞면이 검 www.acmicpc.net 풀이 2가지 작업중 하나를 골라서 최소 횟수로 원하는 목표상태를 만들어야 합니다. 따라서 초기상태와 목표상태를 비교하여 Black -> White 의 개수와 White -> Black의 개수를 카운트 해준 뒤, 짝을 맞춰서 맞는짝은 1번작업을, 나머지는 2번작업을 해줍니다. 예를들어 아래와 같은 상황인 경우 WBBWW WBWBW Black -> White 의 개수는 1개, White -> Black..

2022. 12. 5.