하루살이 개발자

골드바흐의 추측 문제입니다. 문제링크: https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 풀이 소수 찾는 알고리즘인 에라토스테네스의 채 알고리즘 이용 Code from itertools import combinations, product # 소수 찾는 알고리즘(에라토스테네스의 체) def prime_list(n): # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주) sieve = [True] * n m =..

베르트랑 공준 문제입니다. 문제링크: https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 풀이 소수 찾는 알고리즘인 에라토스테네스의 채 알고리즘 이용 Code # 소수 찾는 알고리즘(에라토스테네스의 체) def prime_list(n): # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주) sieve = [True] * n m = int(n ** 0.5) for i in range(2, m + 1): if sieve[i]..

집합의 표현 문제입니다. 문제링크:https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 풀이 union-find 알고리즘을 이용한 문제 Code import sys input = sys.stdin.readline n, m = map(int, input().split()) # 부모 테이블 초기화 parent = [i for i in range(n + 1)] # 부모가 같으면 같은 집합 def find(targe..

* 수학에서 서로소 집합 - 공통 원소가 없는 두 집합 * 서로소 집합 자료구조 - 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 - 연산: union + find 1) union - 2개의 원소로 이루어진 집합을 하나의 집합으로 합치기(합집합) 2) find - 특정 원소가 속한 집합이 뭔지 알려주는 연산 - 서로소 집합 자료구조는 union + find 연산으로 구성되어 union-find 자료구조라 불린다. * 서로소 집합 계산 알고리즘 1) 동작 방법 (1) union 연산 확인 - 서로 연결된 두 노드 확인 -> A의 루트노드 A'와 B의 루트노드 B'찾기(find) -> A'를 B'의 부모 노드로 설정하기(A' < B') (2) 모든 union 연산을 처리할 때까지 (..

연관관계 개념 1. N : 1 - N인 테이블이 FK이다.(공식1) - User기준 1 : N, 게시글 기준 1 : 1 2. N : N - 중간 테이블을 만들어야 한다.(공식2) - User와 영화의 관계에서 "예매"라는 중간 테이블을 만들어야 한다. - User기준 1 : N , Movie기준 1 : N 1. 구독하기 모델 만들기 Subscribe package com.cos.photogramstart.domain.subscribe; import java.time.LocalDateTime; import javax.persistence.Entity; import javax.persistence.GeneratedValue; import javax.persistence.GenerationType; impor..

def prime_list(n): # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주) sieve = [True] * n m = int(n ** 0.5) for i in range(2, m + 1): if sieve[i] == True: # i가 소수인 경우 for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정 sieve[j] = False # 소수 목록 산출 return [i for i in range(2, n) if sieve[i] == True] 임의의 자연수 n이 있으면 그 이하의 소수들을 전부 찾아내는 데 있어서 최적화된 알고리즘! * 관련 문제 https://thrainer.tistory.com/62?category=1007146 [Bae..

1. 우선순위 큐란? - 일반적인 큐(Queue)는 First in-First Out 구조이다. (부가적인 조건 없이 먼저 들어온 데이터가 먼저 나가는 구조) - 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것이다. - 우선순위 큐는 힙(Heap)이라는 자료구조를 가지고 구현할 수있다. - 큐나 스택과 비슷한 자료형이지만, 각 원소들은 우선순위를 가지고 있다. - 우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 같은 우선순위를 가진다면, 먼저 들어온 원소를 처리한다. - 우선순위 큐는 힙(heap)이라는 자료 구조를 통해 구현할 수 있다. - 우선순위 큐는 최소한 두 가지 연산이 지원되어야 한다. 하나..