python알고리즘 익히기-1일차

알고리즘들 정리하기 및 백준 문제 풀이하기

소수(feat. 에라토스테네의 체)

• 약수의 성질 -> 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 지닌다!
  가운데 약수(제곱근)까지만 확인하면 된다!

  	1.남은 수중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다(자연스럽게 소수를 고르게 됨!)
  
  	2. 남은 수 중에서 i의 배수를 모두 제거한다(i는제거 안함)
  
  	3. 더 이상 반복 할수 없을때 까지 앞에 과정 반복
  
  	메모리는 많이 필요하다! -> 10억이 소수인지 아닌지 파악 가능? -> 메모리 비효율 조심!

투 포인터

• 리스트에 순차적으로 접근 해야 할때 두 개의 점의 위치를 기록 하면서 처리

  	ex) 합이 M인 부분 연속 수열의 개수를 구하시오
  
  	1. 시작과 끝점이 첫번째 원소의 인덱스를 가리키게 함
  
  	2.현재 부분합이 M과 같다면 카운트
  
  	3.M보다 작으면 end 증가
  
  	4.M보다 크면 start를 증가!
  	이걸 반복!

heapq

이진트리기반의 최소 힙 자료구조를 제공해준다 - 정렬된 상태로 추가됨 가장작은 값은 인덱스 0

From heaps import heap push
heap = []
heapq.heappush(heap,4)
heaps.heappop() -> 맨 처음 0번째 인덱스가 리턴되면서 삭제

최댓값이나 최솟값을 찾으려 할때는 힙을 생각하기! -> 힙은 이진트리를 기본으로 함!

백준 문제 풀이

에라토스테네스의 체 알고리즘 - 2960번 문제

문제 링크

설명 : 에라토스테네스의 체 방식으로 소수가 아닌 모든 것에 False를 줬고, 
소수도 카운트에 개수로 세야하기 때문에 소수까지도 False를 줘서 카운팅 했다

짧은 한 줄평 : 이렇게 풀면 arr[i] 검사를 두번 하는거여서 좋은 코드는 아닌거 같긴하다 ㅋㅋ

n,k = map(int,input().split())
count = 0

arr = [True for i in range(n+1)]

for i in range(2,n+1):
    if arr[i] == True:
        for j in range(i,n+1,i):
            if arr[j] == True:
                arr[j] = False 
                count +=1 
            if count == k:
                print(f"{j}")
                break 

heapq - 2075번 문제

이건 솔직하게 답 봤는데도 heapq를 제대로 몰라서 바로 이해는 안되서 따로 heapq를찾아봤던 문제다

import sys
import heapq
input = sys.stdin.readline # 반복적으로 입력할때는 사용하기!

n = int(input().strip()) #개행 문자를 제가해줘야하기때문에 split() 작성했다
hq = []

for _ in range(n):
    nums = list(map(int, input().split()))

    if not hq:
        for num in nums:
            heapq.heappush(hq, num) # 잊지말자 무조건 완전 이진 트리형태로 들어간다! 작은숫자가 위로 !!
    else:
        for num in nums:
            if hq[0] < num:
                heapq.heappush(hq, num)
                heapq.heappop(hq)
print(hq[0]) # N개의 숫자중 N번째를 뽑으려면 가장 작은 숫자인 hq[0]을 뽑야야해서 이걸 출력했다