알고리즘-python

✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[수학] [BJ1929] 소수 구하기
🚩 문제 설명 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net ⏱️ 시간 복잡도 ▪ 총 N개의 수가 있다. ▪ 해당 수열에서 어떤 수가 소수인지 알아내는 데에는 O(abs(N)) 이 걸린다. ▪ N개의 수열 중에서 모든 소수를 찾는 데에는 O(N x abs(N)) 이 걸린다. ▪ 해당 문제에서 N의 최대 범위가 100만 이므로 총 시간복잡도는 10^9가 되고 이는 시간초과를 일으킨다. ▪ 따라서 에라토스테네스의 체 라는 방식으로 소수를 구하면 O(NlogN)으로 좀 더 빠르게..
→2021.12.01
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[수학] [BJ1978] 소수 찾기
🚩 문제 설명 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net ⏱️ 시간 복잡도 ▪ ◾ 소수를 찾아서 개수를 구해 출력하는 문제 이다. ◾ 소수 (Prime Number) 약수가 1과 자기 자신밖에 없는 수 N이 소수가 되려면, 2
→2021.12.01
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/프로그래머스
[PG12910] 나누어 떨어지는 숫자 배열
🚩 문제 설명 https://programmers.co.kr/learn/courses/30/lessons/12910 코딩테스트 연습 - 나누어 떨어지는 숫자 배열 array의 각 element 중 divisor로 나누어 떨어지는 값을 오름차순으로 정렬한 배열을 반환하는 함수, solution을 작성해주세요. divisor로 나누어 떨어지는 element가 하나도 없다면 배열에 -1을 담아 반환하 programmers.co.kr ⏱️ 시간 복잡도 ▪ arr의 배열의 크기가 N이라고 가정한다면, 시간복잡도는 O(N)에 해당한다. ◾ 주어지는 배열 중에서 특정 정수로 나누어 떨어지는 정수를 반환하는 문제 ✅ 입출력 arr : 자연수를 담은 배열 divisor : 나누어 떨어지는 기준 정수 return ➡️ a..
→2021.11.30
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[BJ2178] 미로 탐색
🚩 문제 설명 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net ◾ 1 일 경우 ➡️ 지날 수 있음. ◾ 0 일 경우 ➡️ 지날 수 없음. ✅ 입출력 1) 두 정수 N, M이 주어진다. : 미로의 크기 2) 다음 N개의 줄에 M개의 정수로 미로가 주어진다. return ➡️ 지나야하는 최소의 칸 수를 출력. ✔️ 예제 1 4 6 101111 101010 101011 111011 15 ✔️ 예제 2 4 6 110110 110110 111111 111101 9 ✔️ 예제3 2 25..
→2021.11.30
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘
[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

• 이전
• 1
• ···
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• ···
• 14
• 다음