✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺

✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[BJ1260] DFS와 BFS
🚩 문제 설명 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net ⏱️ 시간 복잡도 ▪ 그래프의 정점의 개수가 N개라고 한다면, 시간 복잡도는 O(N)에 해당한다. ◾ 그래프가 주어지고 이를 DFS/BFS로 탐색한 결과를 출력하는 문제 ◾ 단, 정점 번호가 작은 것을 먼저 방문한다. ✅ 입출력 1) N, M, V : 정점의 갯수, 간선의 개수, 탐색을 시작할 정점 번호가 차례대로 주어진다. 2) 간선이 연결하는..
→2021.11.30
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[수학] [BJ1934] 최소공배수
🚩 문제 설명 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net ⏱️ 시간 복잡도 ▪ 최소공배수 LCM은 GCD를 구한다면 O(1)의 연산 시간으로 문제 해결 가능 ▪ 최소공약수 GCD를 구하는 데 O(N)의 시간복잡도가 걸린다. ◾ 두 자연수의 최소공배수를 구하는 문제 ✅ 입출력 1) 테스트 케이스 T가 주어진다. 2) 테스트 케이스의 수만큼 두 자연수 A, B가 주어진다. return ➡️ 두 자연수 A, B가 주어졌을 때..
→2021.11.30
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[수학] [BJ2609] 최대공약수와 최소공배수
🚩 문제 설명 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net ⏱️ 시간 복잡도 ▪ 최대공약수, 최소공배수 모두 O(N)의 시간복잡도로 구할 수 있다. ◾ 두 수의 최대공약수와 최소공배수를 구하는 문제 ◾ 최대공약수 (Greatest Common Divisor) 두 수의 공통된 약수 중에서 가장 큰 정수 최대공약수가 1인 두 수는 서로소 (Coprime) 라고 한다. 구하는 방법 2부터 min(A, B)까지 모든 정수로 나누어 본다. 유클리드 호제법을 사용한다. gcd(a, b) == gcd(b, a%b) r ..
→2021.11.30
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[수학] [BJ10430] 나머지
✅ 나머지 import sys A, B, C = map(int, sys.stdin.readline().split()) print((A + B) % C) print(((A % C) + (B % C)) % C) print((A * B) % C) print(((A % C) * (B % C)) % C) ◾ 수학 ◾ 주어진 숫자들을 이용하여 특정 식의 해답을 구하는 문제 # 코드 플러스 나머지 파이썬 python # 코드플러스 백준 10430 나머지
→2021.11.30
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/이것이 코딩 테스트다
[TC0502] [DFS/BFS] 미로 탈출
🚩 문제 설명 동빈이는 N x M 크기의 직사각형 형태의 미로에 갇혀있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. ✅ 입출력 1) 첫째 줄에 N, M 이 주어진다. 2) 다음 N개의 줄에 각각 M개의 정수가 주어진다. return ➡️ 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수 ✔️ 예제 1 5 6 101010 11..
→2021.11.30
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[자료구조(참고)] [BJ1918] 후위 표기식
🚩 문제 설명 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net ⏱️ 시간 복잡도 ▪ 문자열의 길이를 N이라고 가정한다면 대략적으로 O(N^2)의 시간복잡도가 걸린다. ◾ 중위 표기식을 후위 표기식으로 변환하는 문제 ◾ 차량기지 알고리즘 (Shunting-yard Algorithm) 중위 표시식을 후위 표기식으로 바꾸는 알고리즘이다. 연산자를 저장하는 스택을 기반으로 이루어져 있다. 1. 연산자는 스택에 push 한다. 2. 해당 연산자 우선순위
→2021.11.29

• 이전
• 1
• ···
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• ···
• 30
• 다음