03_basic_exercise
08_소수구하기문제
# 클래스를 사용하는 가장 대표적인 유형 : 소수들을 출력하는 문제!!!
예) 1부터 100까지 소수들을 출력하세요1!!
예) 약수, 배수, 공약수, 공배수 등......
기본적인 문제들은(정수 관련된 문제들)
-1) 정의대로 코드를 구현을 할 것인가 : 반복/ 제어/ 연산 etc
-2) 이론적으로 가지는 속도/ 효율성에 대한 문제점!!!!
==> 수학 이론에서는 여러가지 알고리즘/ 방법론...
알고리즘 대회 : 여러 방법들을 자세히 잘 알아야 됨(지식!!)
취업 코테 : 여러 방법론들은 지양하고, 지식적인 줄이고 있음!!!
: ==> 살짝 간단한 아이디어 정도로 해결하는 수준...
# 참고 : 2022년 카카오 2번 문제
- https://school.programmers.co.kr/learn/courses/30/lessons/92335
20개 test 1~2개 경우를 시간 초과!!!!!
===> 효율성을 하세요!!!!!( 간단한 아이디어!)
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
# 1~100까지 소수들을 출력하세요!!
정의 :소수의 정의 ==> 1하고, 자기 자신만 나눠 떨어지는 경우1!!!
n까지 소수들을 찾아주세요!!!!!
--> 2~~(n-1)까지 다 나눠보면서,,, for
n-1까지 나눠 떨어지지 않으면 if % , ==/ !=
소수
혹,중간에 나눠 떨어지면 if
합성수...
===> n = 6 : n % 2 ==0 ---> 합성수
n = 7 : 7%2(X), 7%3(X), 7%4(X), 7%5(X), 7%6(X)
==> 7은 소수구나!!!!!!
기본문제 : 전체적인 2중 for문의 구조를 정확히 이해하는지 기본!!!!
+ if문 + 컨트롤(continue, break, pass etc)
==> 전체적인 골격을 정확히 이해하는지 체크에 용이한 문제!!
n =100
# 할 일 : 1부터 n까지 소수들을 다 출력하세요!!!!!!+++인덱스 처리!!!!
for i in range(2, n+1): # 2~n까지가 테스트 할 숫자들을 롤링!!!!
# 1개 숫자가 선택이 된다면 예) i= 8, i = 7
# i라는 숫자를 바탕으로 할 일 : 2부터~~~나눠서 i까지 살아오면,,출력
for j in range(2,i+1):
if i % j ==0:
break
if j ==i:
print(i)
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
---> 2중 for문에 대해서 기본적인 처리!!!!!
---> 골격에 대해서 구체적인 인덱스 처리!!본인 로직에 맞춰서 미묘하게 잘 해야함!!
: 정확하게 안 하면,,대충 소수는 나온데, 정확하게 안 나옴!!!!
---> 가장 기본 유형 중 하나임!!!!
간단하지만, 기본적인 유형들에 대한 문제들을 잘 파악을 하셔야 함!!
==> 기본 문제를 내가 응용하면,어떻게 출제하지!!!!!
++++ 이런 숫자 관련된 (배수, 약수, 소수 등) : 효율성/ 기본 골격 좀 더 관심 !!
점심 식사 하시고
있다가 이어서
식사후에 k진수 문제 풀어보세요
==> 2시에 이어서
04_cotest
19_2022_k진수
# ref : https://school.programmers.co.kr/learn/courses/30/lessons/92335
==> 기본 유형/ 기본 문제들이 어떻게 응용이 되어서 나오는지!!!1
==> ++ 전통적인 기본 유형을 어떻게 코테화 시키는지!!!!
참고) 정답률 5X % --> 엇;;;;;( 지식적인X, 아이디어!!! )
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
==> n자연수 ---> k진법으로 변환 --> 조건에 맞는 경우의 소수 카운팅!!!
엇;;; 우리가 아는 일반적인 P의 기준과 약간 뭔가 이상하네;;;
101은 사람입장에서 소수로 판단을 하는데,,
여기선느 인정을 안 한다는 입장!!!!
# 문제를 체크
1) n(입력 10진수) ---> k진법( 3~10진법으로 제한) --> 변환!!!
==> 규칙 : n을 k로 몫이 0이 될 때 까지....나머지들을 모아서 & 역순
2) 0을 중심으로 쪼갠다!!! *****
3) 쪼갠 부분들을 돌려가면서 ,for
---> 10진수 기준으로 소수인지 체크!!!!!
if 소수라면 : 카운팅!!!!
# Step 1) 입력 n을 k진법으로 변환하는 함수!!!!
입력 : 숫자n, 진법k
출력 : k진법으로 변환된 n의 결과 ---> 개취: 문자열(역순처리, 쪼갠다)
---> k진법 변환하는 규칙 : n을 k로 계속 계속 나누면 됨!!! : while
: 이유) 조건 중심으로 표현/규칙!!!
==> 중간에 탈출 경호 break : 몫이 0이하인
: 나누면서 할 일 : 몫 & 나머지
몫 : while --> go / stop
나머지 : 기록--> 나중에 역순으로(문자열)
a = [1,2,3,4]
a.reverse()
a
[4,3,2,1]
a = [1,2,3,4]
a[::-1]
[4,3,2,1]
"1234".reverse()
AttributeError
a = list("1234")
a.reverse()
a
['4', '3', '2', '1']
"1234"[::-1]
'4321'
def convert_k_system(n,k):
# 나머지들을 문자열로 하나씩 기록을 하자!!
k_sys = "" # 본인 기준별로 리스트로 하셔도 상관없습니다.
while n>0: # 몫이 0이상일 때 까지..
k_sys += str( n % k) # 리스트면 append() ==> 나머지 모아두기
n = n // k # 나눈 수를 계속 몫으로 갱신!!!!
# ----> k_sys = "나눈 순서대로 나머지들이 정리"
# ==: k진법으로 변환 : 역순!!
k_sys = k_sys[::-1]
return k_sys
# test
n = 437674
k =3
convert_k_system(n,k)
'211020101011'
# test
n = 110011
k = 10
convert_k_system(n,k)
'110011'
# step2) 0을 중심으로 쪼개기!!!! ==> 참고: 리스트인 경우 필터링!!!
( 0,1을 제외한 값들만 추려주세요!!!)
temp = convert_k_system(n,k).split("0")
temp
['11', '', '11']
# 걸러내려는 부분에 대해서 여러 방식이 존재를 함!!!
for i in temp:
if i != "":
print(i)
# 소수인지 판별할 덩어리 선택!!!
# ==> 소수인지 판별을 하고, 소수이면 카운팅!!!!!
else:
pass
11
11
# Step3) 소수 판별 함수!!!!
입력 : 숫자
출력 : 소수판별Y/N --> True(소수), False(소수X)
point) 정의대로 구현을 해보고,,이상하면 수정할까!!!!!
point) 1에 대한 필터링을 여기서 그냥 할께요!!!!!
def check_prime(m):
c = 2 # --> 2부터 계속 나눠보자!!!!
if m == 1:
return False
else:
while c < m: # 2~m-1까지 계속 나누기!!!!!
if m % c ==0:
return False
else:
c += 1
return True # ---> 2부터 입력 m-1까지 중간에 나눠 떨어지지 않고 생존!!
# ==> 소수!!!
check_prime(211)
True
check_prime(2)
True
check_prime(10)
False
check_prime(101) # --> 앞에 step2에서 "101"--> "1","","1" 예외처리가 된다!!!
# 조립!!
def solution(n, k):
answer = 0 # <-- 기본 양식은 -1인데, 하나도 없는 경우 카운팅 : 0 초기화
# 1) 입력 n --> k진법으로 변환 함수 : 문자열
n_to_k = ~~~~!
# 2) n_to_k를 문자열 0을 기준으로 분리 : 리스트
# 3) n_to_k의 원소 덩어리들을 돌려가면서 : 소수인지 판별!!!!!
# +++ 소수라면 : +1로 카운팅!!!!
for ~~~
if 덩어리가 빈 문자열이 아니면~~~
if 그 숫자 덩어리가 소수면
answer += 1 # 카운팅!!!!
return answer
# 실질적인 조립!!
def convert_k_system(n,k):
k_sys = ""
while n>0:
k_sys += str( n % k)
n = n // k
k_sys = k_sys[::-1]
return k_sys
def check_prime(m):
c = 2 # --> 2부터 계속 나눠보자!!!!
if m == 1:
return False
else:
while c < m: # 2~m-1까지 계속 나누기!!!!!
if m % c ==0:
return False
else:
c += 1
return True
def solution(n, k):
answer = 0 # <-- 기본 양식은 -1인데, 하나도 없는 경우 카운팅 : 0 초기화
# 1) 입력 n --> k진법으로 변환 함수 : 문자열
n_to_k = convert_k_system(n,k) # "211020101011" ,
# 2) n_to_k를 문자열 0을 기준으로 분리 : 리스트
# 3) n_to_k의 원소 덩어리들을 돌려가면서 : 소수인지 판별!!!!!
# +++ 소수라면 : +1로 카운팅!!!!
for num in n_to_k.split("0"): # [ "211", "","2","","1","","1","","11"]
if num =="": # 구조적으로 설명을 하기 위해서...
continue
else: # 빈 문자 덩어리가 아닌 경우..--> 소수 체크!!!!
if check_prime( int(num)) == True:
answer += 1 # 카운팅!!!!
return answer
--> 아....2번 치고,,,,,너무 쉬운데;;;;코드도/문법도 쉽네;;
아주 복잡하거나 여러 경우가 그렇게 안 보이네;;;
===> 쌔.;;;
# test
n = 437674
k =3
solution(n,k)
3
# test
n = 110011
k =10
solution(n,k)
2
실제 업로드를 해서 채점을 하면,,,
===> 1개 빼고는 다 맞추는 코드가 됨!!!
기본 코드는 큰 문제는 없는 코드입니다1!!1
===> 어떻게 좀 더 효율화를 가져갈 것인가!!!!!!!!
나의 코드를 리뷰!!!! + n 의 값이 커질 수 있는 부분에 종속되는 무엇인가를 찾아!!!
++++ 종종 나오는 아이디어 중 하나가 : " 대칭성"
==> 카카오 or 다른 쪽에서도 대칭성을 활용하는 부분의 문제가 종종~~
==> 이런 간단한 적용 아이디어를 내 코드에 접목을 시도할 수 있음!!!
완전히 효율적으로 하는 수학에서 알고리즘 : 아리스토텔레스의 채!!!!
==> 지식적인 부분의 문제........
+++ 이런거 몰라도 간단하게 대칭성이나 아이디어 통해서 효율성!!!!
( +++ 탐색에서도 백트레킹 문제들이 종종 나오게 됨!!! )
def check_prime(m):
c = 2 # --> 2부터 계속 나눠보자!!!!
if m == 1:
return False
elif m==2:
return True
else:
c = 2
end = int(m**0.5) + 1
while c <= end: # 2~m-1까지 계속 나누기!!!!!
if m % c ==0:
return False
else:
c += 1
return True
55퍼센트 정답률 : 여러 다양한 문제들을 풀어봤어야 생각을 할 수 있는 문제!!!
==> 어렵거나, 코드가 어려운 부분은 아니여도
정답률이 낮게 나타는 경우가 있음!!!
==> 지식적인 부분보다는 간단 아이디어로 효율화!!!: 대칭화, 조건이 만족하면 컷!!!!
: 공회전을 최대한 미리 방지하자!!!!!!
## 정수의 범위가 벗어날 수 있음!!!!!
: 파이썬으로 사용해서,,운이 좋게도,,파이썬의 정수 범위가 커요;;;
==> 운이 좋게도 이 부분은 피할 수 있었음!!!!
import sys
a = sys.maxsize
a
9223372036854775807
# 참고) 전통적인 알고리즘 대회들은 이 주제도 상당히 자주 신경써야 하는
포인트 중 하나입니다!!! 유효 자리수 문제!!!!!
채용 코테에서는 굳이;;;;;;;;
전통적인 주제들을 바탕으로 응용을 하는 코테 문제!!!
==> 공약수에 대한 부분 : 2개/이상에 대한 수들을 약수들을 다 찾아서
공통된 값들을 찾아서,,,,최대값,,,,,
: 약수를 정의대로 찾으면 1부터 n까지 다 나눠봐야 함!!!
: --> 나눠 떨어지는 친구들을 리스트업!!
===> 여러 숫자들에 대한 공약수 : 유클리안 호제법!!! 알고리즘.....
+++ 기본적인 약수/배수/공약수/공배수 관련된 전통 주제들에 대해서도 고민!!!
파이썬 쪽지 시험
'ASAC 빅데이터 분석가 7기 > ASAC 일일 기록' 카테고리의 다른 글
| ASAC 빅데이터 분석가 과정 10일차 - 2 (24.12.17) (0) | 2024.12.17 |
|---|---|
| ASAC 빅데이터 분석가 과정 10일차 - 1 (24.12.17) (1) | 2024.12.17 |
| ASAC 빅데이터 분석가 과정 9일차 - 1 (24.12.16) (1) | 2024.12.16 |
| ASAC 빅데이터 분석가 과정 8일차 - 2 (24.12.13) (3) | 2024.12.13 |
| ASAC 빅데이터 분석가 과정 8일차 - 1 (24.12.13) (2) | 2024.12.13 |