Computer Science20 Array(배열)과 List(리스트) 차이 Array (배열) 특징 메모리 상에 데이터가 연속적으로 저장된다 같은 성질을 갖는 항목들의 집합 크기가 고정적이다. 랜덤 접근이 가능하다. 장점 인덱스가 있어 탐색의 경우 시간 복잡도는 O(1)이다. 단점 맨 앞이나 중간에 삽입이나 삭제시 그 뒤(오른쪽)에 있는 값들을 한쪽으로 한칸씩 옮겨야 하기 때문에 시간복잡도는 O(n)이다. (삭제나 삽입시 재배열이 필요하다) 배열 생성시 크기를 정해야하며, 추후에 변경하기 힘들다 배열을 사용할 때 읽기가 빈번하게 일어나는 경우 List (리스트) 특징 메모리 상에 데이터가 비연속적으로 저장된다. 크기가 가변적이다. 장점 메모리 공간을 미리 확보할 필요가 없다. 단점 읽기 시 시간 복잡도는 O(n)이다 리스트를 사용할 때 삽입과 삭제가 빈번하게 일어날 경우 추가적.. 2023. 5. 13. [자료구조] 우선순위 큐(Priority Queue) 우선순위 큐(Priority Queue) 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조 사용 용도 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야하는 경우 특징 힙(heap)을 이용한 구현 방법 루트 노드엔 우선순위가 높은 값이 들어간다. 힙에서는 항상 루트 노드를 제거한다. 힙은 완전 이진 트리 형태로 구성되어있다. import sys from heapq import heappush, heappop input = sys.stdin.readline n = int(input()) heap = [] for i in range(n, 0, -1): heappush(heap, i) print('-' * 15, 'heappop', '-' * 15) for i in ra.. 2023. 5. 10. [알고리즘] 소수 판별 : 에라토스테네스의 체 하나의 수가 소수인지 판별할 때는 간단하게 아래와 같이 짤 수 있다. # n : 소수인지 판단할 숫자 is_prime = 1 for i in range(2, n): if n % i == 0: is_prime = 0 소수를 여러번 판별할 경우 에라토스테네스의 체를 사용하는 것이 효율적이다! 10^12 의 큰 수를 소수 판별시 위의 방법 사용 10^6 이하의 모든 소수를 구할때는 에라토스테네스의 체를 활용!! 에라토스테네스의 체 시간 복잡도 O(nloglogn) 어떤 수가 소수가 아닌지를 판정하는 방식으로 동작 2부터 순서대로 그 수가 소수이면 그의 배수들을 모두 소수가 아님! 예시 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 .. 2023. 5. 9. [디자인 패턴] Factory 디자인 패턴 의미 각 모듈의 세분화된 역할이나 모듈들 간의 인터페이스와 같은 코드를 작성하는 수준의 세부적인 구현방안을 설계할 때 참조할 수 있는 전형적인 해결방식 또는 예제 즉, 로직에 따라 반복되는 패턴 생성 패턴(Creational Pattern) 객체 생성과 관련된 패턴 객체의 생성과 참조 과정을 캡슐화하여 객체가 생성되거나 변경되어도 프로그램의 구조에 영향을 크게 받지 않도록 하여 프로그램에 유연성을 더해줌 Factory object를 찍어 낼수있는 공장 공장 하나로 여러개의 오브젝트를 만든다. 장점 복잡한 오브젝트의 생성을 클라이언트가 다룰 필요가 없다. 클라이언트는 요청을 하여 팩토리에 넘겨주기만 하면 됨 추가 기능을 구현하기 어렵다. -> Factory Method을 사용하면 된다. 최상위.. 2023. 4. 7. 이전 1 2 3 4 5 다음