컴퓨터 사이언스/Algorithm(31)
-
백준 파이썬 9020: 골드바흐의 추측
골드바흐의 추측 성공다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 256 MB 53440 22452 17139 40.620% 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 +..
2022.03.29 -
백준 파이썬 4948: 베르트랑 공준
베르트랑 공준 성공다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 61963 24574 19945 39.874% 문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이..
2022.03.26 -
파이썬 해시법
해시법 해시법이란 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 의미한다. 아래의 표를 보며 해시법의 단어들을 자세히 설명해보겠습니다. 키 5 6 14 21 25 34 해시값(6으로 나눈 나머지) 5 0 2 3 1 4 이렇게 키의 값을 배열의 크기(길이)나 특정 기준으로 나눈 것을 해시값이라고 합니다. 해시값은 데이터에 접근할 때 기준 인덱스가 됩니다. 위에서 구한 해시값을 인덱스로 하여 원소를 새로 저장한 배열을 해시 테이블이라고하며, 아래와 같습니다. 6 25 14 21 34 5 -키를 해시값으로 변환하는 과정(나누는 과정)을 해시 함수라고 합니다. _해시 테이블에서 만들어진 원소(=배열 한 칸)를 버킷이라고 합니다. _만약 위의 해시 테이블에 18이라는 키값을 추가하고 싶을 때 ..
2022.02.15 -
파이썬 배열 이진 검색
이진 검색 _이진 검색이란 배열의 원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검사할 수 있는 알고리즘입니다. _이진 검색의 조건은 배열의 데이터가 정렬된 상태이어야 합니다. 배열 a가 아래와 같을 때 우리는 a에서 39라는 값을 찾고 싶습니다. 5 7 15 28 29 31 39 40 44 53 이진 검색은 검색 범위를 맨 앞, 맨 끝, 중앙의 인덱스를 각각 0, n-1, (n-1) // 2 로 설정합니다. 이에 따라 첫번째 검색시 중앙 검색범위 (n-1) // 2 를 이용하여 범위를 줄여나갑니다 5 7 15 28 29 31 39 40 44 53 _첫번째 검색 범위를 마치고 난 뒤의 배열 a입니다. 39 40 44 53 다시 위 중앙 검색범위 (n-1) // 2 를 이용하여 범위를 ..
2022.02.09 -
파이썬 배열 선형 검색
선형 검색 _선형 검색이란 직선 모양으로 늘어선 배열에서 검색하는 경우에 원하는 키 값을 가진 원소를 찾을 때 까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘입니다. _선형 검색의 종료 조건은 1. 검색할 값을 찾지 못하고, 배열의 맨 끝을 지나간 경우 -> 검색 실패한체 종료 2. 검색할 값과 같은 원소를 찾는 경우 -> 검색 성공 배열 원소가 n개 라면, 이 조건을 판단하는 횟수는 평균 n/2번입니다. 선형 검색의 기본 코드는 다음과 같습니다. _while문 사용 from typing import Any, Sequence def seq_search(a: Sequence, Key: Any) -> int: # 시퀀스 a에서 Key와 값이 같은 원소를 반복문을 통해서 선형 검색 i = 0 while T..
2022.02.08 -
파이썬 소수 나열하기
파이썬 소수 나열하기 소수란 1과 자기 자신 이외의 정수로 나누어 떨어지지 않는 수를 의미합니다. 즉 1과 자기 자신 이외의 정수로 나누어 떨어진다면 소수가 아님을 알 수 있습니다. 이를 통해 작성한 코드는 아래와 같습니다. cnt = 0 # 곱셈과 나눗셈을 합한 횟수 ptr = 0 # 이미 찾은 소수의 갯수 prime = [None] * 500 # 소수를 저장할 배열 prime[ptr] = 2 # 2는 소수이기에 미리 지정한다. ptr += 1 for n in range(3, 1001, 2): # 짝수는 확실한 합성수이므로, 5부터 1000까지 홀수만 대상으로 반복 for i in range(1, ptr): cnt += 1 if n % ptr[i] == 0: # n이 소수로 나누어지면, 합성수이므로 b..
2022.02.07