본문 바로가기

전체 글

 (160)
[백준 / 정수론] 1978 : 소수 찾기 (python) 문제 설명 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 예제 입력 1 4 1 3 5 7 예제 출력 1 3 풀이 # 소수 찾기 # 에라토스테네스의 체 # n < 1,000 이하의 자연수 import math n = int(input()) num = list(map(int, input().split())) cnt = 0 A = [i for i in range(1001)] A[1] = 0 for i in range(2, int(math.sqrt(len(A)) + 1)): if A[i] == 0:..
[백준 / 소수] 1456 : 거의 소수 (python) 문제 설명 문제 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. 입력 첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다. 출력 첫째 줄에 총 몇 개가 있는지 출력한다. 제한 1 ≤ A ≤ B ≤ 10^14 예제 입력 1 1 1000 예제 출력 1 25 예제 입력 2 1 10 예제 출력 2 3 예제 입력 3 5324 894739 예제 출력 3 183 풀이 import math A, B = map(int, input().split()) arr = [0] * (int(math.sqrt(B))+1) cnt = 0 for i in range(len(..
[10, 11일차] 06 그리디 함께 푼 문제 [백준 / 그리디] 1931 : 회의실 배정 (python) 문제 설명 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치 delicious-kimchi.tistory.com [백준 / 그리디] 2839 : 설탕 배달 (python) 문제 설명 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. delicious-kimchi.tistory.com 그리디 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알..
[백준 / 그리디] 2839 : 설탕 배달 (python) 문제 설명 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000) 출력 상근이가 배달하는 봉지의 최소 개수를 출력한다...
[백준 / 그리디] 1931 : 회의실 배정 (python) 문제 설명 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-..
[9일차] 05 탐색 : 05-3 이진 탐색 함께 푼 문제 [백준 / 이진 탐색] 10815 : 숫자 카드 (python) 문제 설명 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지 delicious-kimchi.tistory.com 이진 탐색 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다. 시간 복잡도 : O(logN) 데이터가 정렬돼 있어야 함 파이썬 구현 A = [4, 8, 10, 5, 2, 7, 6, 3, 9, 1] A.sort() # **데이터 정렬** start = 0 end = len(A) - ..
[8일차] 05 탐색 : 05-1 깊이 우선 탐색, 05-2 넓이 우선 탐색 함께 푼 문제 [백준 / DFS, BFS] 2606 : 바이러스 (python) 문제 설명 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리 delicious-kimchi.tistory.com 깊이 우선 탐색 (DFS) 그래프 완전 탐색 기법 중 하나로, 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 시간 복잡도 : O(V + E) 재귀함수 또는 스택으로 구현 가능 그래프는 보통 인접 리스트로 나타냄 인접 리스트 : 그래프를 표현하기 위한 방법 중 하나. 그래프의 한 꼭짓점에서 연결되..
[7일차] 04 정렬 : 04-5 병합 정렬, 04-6 기수 정렬 병합 정렬 (Merge Sort) 파이썬 구현 def merge_sort(arr): if len(arr) == 1: return arr mid = len(arr) // 2 left = arr[:mid] right = arr[mid:] left_arr = merge_sort(left) right_arr = merge_sort(right) return merge(left_arr, right_arr) def merge(left, right): i, j = 0, 0 #투포인터 sorted_arr = [] while i < len(left) and j < len(right): if left[i] < right[j]: sorted_arr.append(left[i]) i += 1 else: sorted_arr.app..
반응형

티스토리툴바