본문 바로가기

Python

(4)
[Theory] 에라토스테네스의 체 * 소수 Prime number - 1 과 자기 자신을 제외한 수로는 나누어 떨어지지 않는 수 - 자신보다 작은 두 자연수의 곱으로 만들 수 없는 1보다 큰 수 '에라토스테네스의 체'는 고대 그리스의 수학자 '에라토스테네스'가 발견한 것으로 소수를 찾는 방법을 말합니다. '체'라는 표현을 쓴 이유는 소수를 찾는 방법이 체로 물질을 걸러내듯이, 숫자배열을 순회하며 소수를 걸러내고, 소수가 아닌 수를 버리는 방식이기 때문입니다. 파이썬을 통해 에라토스테네스의 체를 구현해보도록 하겠습니다. def sieve_of_Eratosthenes(input_num): sieve = [True] * input_num n = int(input_num ** 0.5) for i in range(2, n+1): if sieve[..
[Book] 파이썬과 함께하는 자료구조의 이해. Chapter 3. 스택과 큐 * 본 글에서 작성된 내용과 코드들은 도서[파이썬과 함께하는 자료구조의 이해] 의 내용을 참고 및 발췌한 것입니다. 스택 Stack stack 이라는 말 그대로 데이터가 한 쪽 끝에서 차곡차곡 쌓이는 형태의 자료구조를 말합니다. 데이터가 쌓여있는 형태이기 때문에, 데이터를 꺼낼 때도 맨 위쪽에 쌓여있는 데이터부터 순차적으로 꺼낼 수 있습니다. 나중에 들어온 데이터부터 꺼낼 수 있다고 해서 '후입선출'의 자료구조라고도 표현합니다. 이 글에서는 1. 파이썬의 리스트를 통해 스택을 구현하는 것과, 앞장에서 다루었던 2. 단순 연결 리스트를 이용해서 스택을 구현하는 것, 두 가지를 다뤄보겠습니다. 1. 파이썬 리스트를 이용한 Stack 구현 def push(item): stack.append(item) def ..
[Programmers] 주식가격 문제 ...더보기 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다. 가격이 1초 뒤에 떨어져도, 1초간은 떨어지지 않은 것으로 봅니다. 입출력 예 prices return [1, 2, 3, 2, 3] [4, 3, 1, 1, 0] 풀이 def solution(input_list): result_list = [0] * len(input_list) for i in range(len(input_list)): for j in range(i+1, len(inpu..
[Book] 파이썬과 함께하는 자료구조의 이해. Chapter 2. 연결리스트 * 본 글에서 작성된 내용과 코드들은 도서[파이썬과 함께하는 자료구조의 이해]의 내용을 참고 및 발췌한 것입니다. 1. 단순 연결 리스트 리스트를 구성하는 요소들이 한 방향으로만 연결돼있는 자료구조를 칭합니다. 파이썬에서의 리스트 자료형은 동적 메모리 할당을 통해 구현되는데, 즉 리스트를 구성하는 각 개체는 다음 객체로의 래퍼런스를 가지고 있어야 합니다. 단순 연결 리스트의 경우 이 래퍼런스가 단방향 적으로만 이루어져, 한 객체에서 이전 객체로의 접근은 불가능한 자료구조입니다. 이러한 형태로 인해, 단순 연결 리스트에서 항목을 탐색하려면 항상 첫 노트부터 시작하여 원하는 항목을 찾을 때까지 차례로 방문하는 순차 탐색의 과정을 거쳐야만 합니다. 예시 코드를 통해 단순 연결 리스트의 자료구조형을 이해해봅시다..