파이썬13 11/06 WIL 1. 알고리즘 관련 공부 이번 주는 공부했던 알고리즘 지식을 정리하려 한다. DFS 그래프 탐색의 일종으로 재귀함수 알고리즘의 형태를 띄고 있다. 전위 순회, 중위 순회, 후위 순회의 형태의 트리 순회가 존재한다. 주로 사용하는 것은 전위 순회이다. 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다. 명심하자! 구현 방법은 재귀 함수 혹은 명시적 스택을 사용하는 것이다. 인접 리스트의 경우 O(N+E)(노드, 엣지), 인접 행렬의 경우 O(n^2)의 시간 복잡도를 갖는다. 예제) 합이 같은 부분 집합(DFS) N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇.. 2022. 11. 6. 10/30 WIL 1. 알고리즘 관련 공부 이번 주는 공부했던 알고리즘 지식을 정리하려 한다. 큐 선입출 방식 전 데이터를 저장하고 주어진 순서에 따라 순서를 바꾸지 않고 해결할 때 가장 사용을 많이 하는 자료구조다. 문제에서 원이나 순서, 입력 순서 등의 키워드가 언급될 때 처음 순서를 저장하고 싶을 때 쓴다. 파이썬의 경우 큐는 collection의 deque를 이용, popleft() 등을 통해 구현이 가능해서 리스트를 쓴다. 보통 in 함수를 사용해서 if의 조건문을 구성해서 이것이 있는지 없는지 체킹하는 방식이 주류다. 예제) 교육과정 설계(큐) 현수는 1년 과정의 수업계획을 짜야 합니다. 수업중에는 필수과목이 있습니다. 이 필수과목은 반드시 이수해야 하며, 그 순서도 정해져 있습니다. 만약 총 과목이 A, B,.. 2022. 10. 30. 10/23 WIL 1. 알고리즘 관련 공부 이번 주는 공부했던 알고리즘 지식을 정리하려 한다. 스택 선입후출 방식 후위 표기식, 가장 큰 수 등 이전에 사용한 데이터를 이용하여 해결할 때 가장 사용을 많이 하는 자료구조다. 연산자와 숫자 구분, 스트링 객체들을 차례로 저장하는 문제 등에 구분하거나 전 데이터를 이용한다. 파이썬의 경우 스택 또는 큐는 리스트의 인덱싱[-1] 과 pop(), popleft() 등을 통해 구현이 가능해서 리스트를 쓴다. 예제) 후위표기식 만들기(스택) 중위표기식이 입력되면 후위표기식으로 변환하는 프로그램을 작성하세요. 중위표기식은 우리가 흔히 쓰은 표현식입니다. 즉 3+5 와 같이 연산자가 피연산자 사이에 있 으면 중위표기식입니다. 후위표기식은 35+ 와 같이 연산자가 피연산자 뒤에 있는 표기.. 2022. 10. 23. 10/09 WIL 1. 알고리즘 관련 공부 이번 주는 공부했던 알고리즘 지식을 정리하려 한다. 에라토스테네스의 체 -> 소수를 판별하는 알고리즘 체로 치듯이 수를 걸러내서 '에라토스테네스의 체'라고 불림, 2 ~ N의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않는 숫자를 소수로 판별하는 방식 숫자마다 일일이 약수가 있는 검사X 이미 지워진 숫자는 바로 건너뜀, 실행시간이 매우 짦음 특정 범위에서 모든 소수를 찾을 때 제일 효율적인 알고리즘 시간 복잡도는 O(N log long N) 특정 숫자에서의 소수 판별은 그냥 2 ~ 루트 N까지의 for문을 돌리면서 특정 숫자의 제곱근까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다. 구현(파이썬) n = int(input()) # 체크리스.. 2022. 10. 9. 이전 1 2 3 4 다음
