[소수 나열하기]
문제설명
정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환 하시오.
(소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.)
의사코드(수도코드)
- 소수를 담을 배열 -> primeArr = []
- for문을 사용하여 소수인 지 아닌 지 판별
https://inten.tistory.com/entry/Python-3x-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0
-> 소수라면 primeArr 배열에 append를 사용해서 넣는다.
->> (아래 코드 참고)
-> 소수가 아니라면 아무것도 하지 않는다.
- primeArr 배열을 return 한다.
문제 풀이
input = 20
def find_prime_list_under_number(number):
# 소수를 담을 배열
primeArr = []
# 소수인 지 아닌 지 판별
for i in range(number+1):
result = True
if(i < 2):
result = False
for j in range(2, i):
if(i % j==0):
result = False
if result :
primeArr.append(i)
return primeArr
result = find_prime_list_under_number(input)
print(result)
이 함수의 시간 복잡도는 O(1)이다.
[문자열 뒤집기]
문제설명
0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자열에 있는 모든 숫자를 전부 같게 만들려고 한다. 할 수 있는 행동은 문자열에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.
의사코드(수도코드)
- 모두 0으로 만드는 방법에서 최소로 뒤집는 숫자 -> count_to_all_zero 변수
->> 0 -> 1로 문자열이 전환되는 순간 => count_to_all_zero += 1
- 모두 1로 만드는 방법에서 최소로 뒤집는 숫자 -> count_to_all_one 변수
->> 1-> 0으로 문자열이 전환되는 순간 => count_to_all_one += 1
1) 문자열이 뒤집어 질 때, 즉 0에서 1 혹은 1에서 0으로 바뀔 때
2) 첫 번째 원소가 0인지 1인지에 따라서 숫자를 추가 해줘야 한다.
선생님이 푼 문제 풀이
input = "011110"
def find_count_to_turn_out_to_all_zero_or_all_one(string):
count_to_all_zero = 0
count_to_all_one = 0
# 앞에 있는 숫자에 따라서 변수에 +1을 해줘야 한다.
if string[0] == '0':
count_to_all_one += 1
elif string[0] == '1':
count_to_all_zero += 1
for i in range(len(string) - 1):
# 앞뒤의 문자들을 봐야 하기 때문에 len(string)-1을 사용하여 i를 인덱스로 사용했다.
if string[i] != string[i + 1]: # 1-> 0 or 0 -> 1
if string[i + 1] == '0':
count_to_all_one += 1
# 1에서 0으로 변환이 됐다는 얘기는
# 앞에 있는 숫자들을 전부 0으로 변환 시켜야 한다는 것이다.
if string[i + 1] == '1':
count_to_all_zero += 1
# 0에서 1로 변환이 됐다는 얘기는
# 앞에 있는 숫자들을 전부 1으로 변환 시켜야 한다는 것이다.
return min(count_to_all_one, count_to_all_zero)
result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)
이 함수의 시간 복잡도는 O(N)이다.
'항해 중 > 알고 보면 알기 쉬운 알고리즘' 카테고리의 다른 글
클래스, 객체, 생성자, 메소드 (0) | 2021.11.13 |
---|---|
Array(배열), Linked List(리스트), 둘의 차이점 (0) | 2021.11.13 |
곱하기 or 더하기, 반복되지 않는 숫자 (0) | 2021.11.12 |
점근 표기법(+배열에서 특정 요소 찾기) (0) | 2021.11.12 |
공간 복잡도 판단하기 (0) | 2021.11.12 |
댓글