본문 바로가기

알고리즘/백준알고리즘

알고리즘/백준알고리즘 2021. 12. 3. [백준 알고리즘/Python3] 9020 골드바흐의 추측 문제이해 처음에 생각했던건 들어온 n값에 대해 소수를 구한다. 가장 작은 소수를 뺀다. 그 뺀값이 구한 소수들로 합쳐진 값이 나온다면 그것이 골드바흐 파티션이다. 나오지 않는다면 다음 소수 리스트로 넘어간다. 이렇게 했더니 시간초과가 나옵니다. 다른방법을 써야할 거 같습니다. 코드 #소수를 구하는 함수 def prime_num(n): a = [False, False] + [True] * (n-1) b = [] #에라토스테네스의 체로 리스트a를 조정한다. for i in range(2, n+1): if(a[i]): for j in range(i*2, n +1, i): a[j] = False #리스트a가 True일 때 인덱스를 출력 for i in range(n+1): #소수이면 if(a[i]): b.app..
알고리즘/백준알고리즘 2021. 12. 2. [백준 알고리즘/Python3] 4948 베르트랑 공준 문제이해 n과 2n 사이에는 적어도 소수 하나는 존재합니다. 즉, 소수를 구하는 모듈이 있다면 n과 2n사이에 서 나온 소수들의 수만 구하면 됩니다. n
[백준 알고리즘/Python3] 1929 에라토스테네스의 체
알고리즘/백준알고리즘 2021. 10. 31. [백준 알고리즘/Python3] 1929 에라토스테네스의 체 문제이해 에라토스테네스의 체에 대한 설명은 위키백과에도 잘 나와있다. -> https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 ​ 에라토스테네스의 체는 고전적인 방법이지만 소수 판정 알고리즘에서 빠질 수 없으며 소수를 이해하기 위한 최고의 알고리즘이라고 생각된다. 가볍게 설명하자면 1. 소수면 체크한다. 2. 체크한 값의 배수는 모두 소수판별에서 제외한다. 3. 이 과정을 반복한다. 코드 m,n = map(int, input().split()) count = 0 a = [False, False] + [True] * (n-1) #에라토스테네스의 체로 리스트a..
[백준 알고리즘/Python3] 11653 소인수분해
알고리즘/백준알고리즘 2021. 10. 28. [백준 알고리즘/Python3] 11653 소인수분해 문제이해 소인수분해라면 어떠한 수가 주어졌을 때 소수로 나눌 수 없을 때 까지 나눈 값들을 소인수분해라고 하지 않나? 예시이다. 1. 그러면 우리는 일단 소수를 구하고 2. 소수의 가장 작은 것 부터 3. 적어준 값에 나눠봐서 4. 몪이 정수형태로 나오지 않을 때까지 5. 나누면 되지 않을까? num = int(input()) sosu_nums = [] for i in range(1,num+1): count = 0 if(i > 1): for j in range(2, i): #소수가 아님 if(i % j == 0): count +=1 if(count == 0): sosu_nums.append(i) print(sosu_nums) 1번을 수행한 것이다. 값을 넣으면 sosu_nums에 소수가 쌓인다. 2부터 ..
알고리즘/백준알고리즘 2021. 10. 3. [백준 알고리즘/Python3] 2581 소수 문제 이해 소수를 찾는 방법 중 그 수를 2부터 n-1까지 나눠서 나머지값이 0이 아니라면 그것은 소수이다. 문제 입력은 공백으로 구분하는 것이 아니라 \n으로 구분했다. 코드 m = int(input()) n= int(input()) num =[] for i in range(m, n + 1): error =0 if(i > 1): for j in range(2, i): #2부터 들어온 값까지 if(i % j == 0): error += 1 break if(error == 0): num.append(i) if(len(num) >0): print(sum(num)) print(min(num)) else: print(-1) error 변수는 플래그 이다. if문에서 j는 2부터 n-1값 까지 돌고 나눠서 0이 ..
알고리즘/백준알고리즘 2021. 9. 27. [백준 알고리즘/Python3] 2839 설탕배달 문제 이해 처음에 5의 배수, 3의 배수가 되는 것을 찾고 그 외에 5의 배수의 나머지 값이 3의 배수인 것을 모두 찾았지만 문제를 잘못 접근 한거 같다. 처음에 5의 배수를 찾고 없다면 3을 빼면서 가방을 +1하고 그래도 5의 배수가 없다면 -1을 출력하는 방식이였다. 코드 n = int(input()) result = 0 while(n >= 0): if((n % 5) == 0): result += (n//5) print(result) break n -= 3 result += 1 else: print(-1) n은 주어진 값입니다.. result는 포대의 갯수입니다. while문으로 주어진 수가 음수 또는 0이된다면 -1을 출력합니다. if문으로 5의배수를 찾고 5로 나눈 몫을 가방 수에 더합니다. 없다..
[백준 알고리즘/Python3] 2775 부녀회장이 될테야
알고리즘/백준알고리즘 2021. 9. 7. [백준 알고리즘/Python3] 2775 부녀회장이 될테야 문제 이해 예를들면 203호의 사람 수를 알고싶다면 101호 + 102호 + 103호 의 사람을 더하면 된다. 103호의 사람 수를 알고싶다면 001호 + 002호 + 003호의 사람을 더하면 된다. 처음 0층의 배열을 1~14까지 만든다. 그리고 인덱스를 활용해 현재 인덱스와 전의 인덱스를 더하면된다. 코드 test_case = int(input()) for _ in range(test_case): k = int(input()) n = int(input()) f0 = [x+1 for x in range(14)] for i in range(k): for j in range(1,n): f0[j] += f0[j-1] print(f0[n-1]) 제일 밖에 for문은 테스트 케이스를 받는다. k는 층 ,n은 동..
[백준 알고리즘/Python3] 10250 ACM호텔
알고리즘/백준알고리즘 2021. 9. 6. [백준 알고리즘/Python3] 10250 ACM호텔 문제이해 위와 같은 방식으로 방에 손님이 들어옵니다. 먼저 층을 구하려면 N%H를 했습니다. 들어온 값을 층으로 나누면 나머지값은 가로 값이 됩니다. 가로값은 곳 층입니다. 여기서 들어온 값이 층과 같다면 (= N%H ==0)이라면 층은 h가 됩니다. 세로값 즉, 동수를 구하려면 N//H를 해야합니다. 세로값은 맨 꼭대기 층을 제외하고 N//H -1 값입니다. 맨 꼭대기층은 N//H값이 나옵니다. 예를 들어) N = 11인 값이 들어오면 N//H = 1.83.. 으로 절대 2값이 넘지 못합니다. 하지만 N = 11인 손님은 2동에 들어가야 하죠 그래서 +1를 합니다. 하지만 N = 12인 값이 들어오면 N//H = 2가 되므로 정확하게 602호에 들어가게 됩니다. 꼭대기 층만 특별하게 if문을 주면 되었..
[백준 알고리즘/Python3] 2869 달팽이는 올라가고 싶다.
알고리즘/백준알고리즘 2021. 9. 5. [백준 알고리즘/Python3] 2869 달팽이는 올라가고 싶다. 문제이해 처음 문제를 봤을 때 등차수열 인가 싶었습니다. 등차수열의 항의 개수 등차수열에서 첫째항을 a 마지막 항을 l, 공차를d라 할 때 항의 개수n은 a,b를 빼면 하루에 올라가는 양이 나오고 최대길이 v를 빼면 되지 않을까 생각했습니다. 고민은 첫째 항이였습니다. a-b를 첫번째 항으로 생각하니 달팽이가 v를 도달했을 때 이상함이 나옵니다. 목표 길이를 도달하고도 다시 내려와야 하는 상황이 나타납니다. 결국 목표길이를 도달해야하는 순간은 아침입니다. 목표에 도달하기 직전인 상황은 (a-b) *n인 상황입니다. 거기에서 a만 더가면 목표에 도달할 수 있죠 그래서 (a-b)*n +a가 목표에 도달할 수 있는 날짜입니다. n동안 날짜를 지나고 하루 +a만큼 가니깐 +1을 해줍니다. 다른사람의 풀이 날짜를..

티스토리툴바