Tech/Coding61 바이트배열을 이용한 에라토스테네스의 체와 그 업그레이드 버전 바이트 배열을 이용한 에라토스테네스의 체가 가장 빠르다는 실험을 했는데 다른 방법을 찾았다.바이트 배열에 홀수만 저장하는 것이다.메모리를 반만 쓸 수 있다.그리고 온라인 저지 상에서는 더 빨랐다.실제로는 좀 더 느리지만 근소한 차이를 보였다.메모리까지 종합적으로 보면 더 우수하다고 할 수 있다.그리고 내가 살짝 튠을 해 보니 조금 더 빠르게 할 수 있었다.import timeimport mathimport matplotlib.pyplot as pltdef sieve_bytearray(n): """ # bytearray를 활용한 에라토스테네스의 체 # 메모리와 연산을 최적화하기 위해 bytearray 사용 """ if n n: # n보다 큰 경우 제외 .. 2025. 3. 1. 에라스토테네스의 체 추가실험(로컬에서 실험) import timeimport arrayimport mathimport matplotlib.pyplot as pltimport numpy as npdef sieve_segmented(n): """ # 세그먼트 체 (Segmented Sieve) # 메모리 사용량과 캐시 효율을 높이기 위해 세그먼트 단위로 처리 """ if n 2: prime.add(3) if n > 1: prime.add(2) for i in range(5, LIM, 6): if i in prime: prime -= RSET(i * i, MAX, i * 6) | RSET(i * (i + 2), MAX, i * 6) j = i +.. 2025. 2. 28. 가우시안 소거법 가우시안 소거법 (Gaussian Elimination)와 가우스-조던 소거법선형 대수학의 핵심 알고리즘인 가우시안 소거법은 선형 방정식 시스템을 풀거나 행렬의 역행렬, 행렬식, 그리고 행렬의 계수(rank)를 계산하는 데 널리 사용됩니다. 이 방법은 독일의 수학자 카를 프리드리히 가우스(Carl Friedrich Gauss)의 이름을 따서 명명되었으며, 연립 방정식을 행 사다리꼴(Row Echelon Form) 또는 기약 행 사다리꼴(Reduced Row Echelon Form)로 변환하는 것을 목표로 합니다.https://www.youtube.com/watch?v=L9fTll_vOxQ&pp=ygUT6rCA7Jqw7IqkIOyGjOqxsOuylQ%3D%3Dhttps://www.youtube.com/wa.. 2025. 2. 25. 벨만 포드 알고리즘 벨만 포드 알고리즘그래프에서 최단 경로를 찾기 위한 방법 중 하나로, 음수 가중치가 포함된 경우에도 사용할 수 있다는 점에서 큰 강점.1. 벨만 포드 알고리즘 개요음수 가중치 지원: 다익스트라 알고리즘과 달리 음수 가중치 간선이 존재해도 올바른 최단 경로를 계산할 수 있습니다.음수 사이클 검출: 알고리즘 수행 후, 추가적인 음수 사이클 존재 여부를 확인할 수 있습니다.시간 복잡도: 일반적으로 O(VE)로, 노드(V)와 간선(E)의 수에 비례하는 시간이 소요됩니다.벨만 포드 알고리즘은 단일 출발점 최단 경로 문제를 해결하는 데 유용하며, 특히 음수 간선을 포함한 다양한 문제에서 많이 활용됩니다.2. 알고리즘 동작 원리벨만 포드 알고리즘의 핵심 아이디어는 릴렉세이션(relaxation)입니다. 각 간선을 반.. 2025. 2. 24. 에라토스테네스의 체 import timeimport arrayimport math######################################## 기존 구현들def modsix_sieve(num: int): MAX = num + 1 LIM = int(num ** 0.5) + 1 RSET = lambda start, end, gap: set(range(start, end, gap)) # 5 (mod 6)와 1 (mod 6)에 해당하는 후보들 (단, 1은 소수가 아니므로 7부터) prime = RSET(5, MAX, 6) | RSET(7, MAX, 6) if num > 2: prime.add(3) if num > 1: prime.add(2) fo.. 2025. 2. 24. 1836🐨트리의 가짓수 세기 .py 1836번: 트리의 가짓수 세기시간 제한메모리 제한2 초128 MB문제 설명노드의 개수 n과 트리의 높이 k가 주어질 때, 각 노드가 자식 노드를 0개 또는 2개만 갖는 완전 이진트리 중에서 높이가 정확히 k인 트리의 가짓수를 구합니다. 단, 트리의 가짓수가 매우 클 수 있으므로 최종 결과는 9901로 나눈 나머지를 출력해야 합니다.예제 입력5 3예제 출력2해결 과정이 문제는 다이나믹 프로그래밍(DP)을 활용하여 해결할 수 있습니다. 알고리즘의 핵심 포인트는 다음과 같습니다.완전 이진트리의 조건: 각 노드는 자식이 0개 또는 2개여야 하므로, 전체 노드의 수 n은 반드시 홀수여야 합니다. 만약 n이 짝수라면 완전 이진트리를 구성할 수 없으므로 결과는 0입니다.높이4 노드9개인 예DP 테이블 정.. 2025. 2. 23. 14939🐨불 끄기-파이썬 불 끄기시간 제한메모리 제한1 초128 MB문제전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라입력10줄에 10글자씩 입력이 주어진다. #은 꺼진 전구고 O(대문자 알파벳 o)는 켜진 전구다. #과 O외에는 입력으로 주어지지 않는다.출력모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라. 불가능하면 -1를 출력하라.예제 입력 및 출력#O########OOO########O############OO#######O##O#######OO######################O####.. 2025. 2. 21. 이분그래프 이분 그래프 판별 알고리즘 설명1. 이분 그래프란?이분 그래프(Bipartite Graph)는 그래프의 정점들을 두 그룹으로 나눌 수 있어서, 각 그룹 내의 정점들 사이에는 간선이 없는 그래프를 말합니다.2. 알고리즘 흐름도3. BFS를 이용한 색칠 과정 이분 그래프와 관련 알고리즘이분 그래프는 노드를 두 그룹으로 나눌 수 있으며, 같은 그룹 내의 노드끼리는 간선이 연결되지 않는 그래프다. 이분 그래프와 알고리즘이분 그래프는 정점 집합을 두 개의 그룹(U, Vredcubes.tistory.com 4. 코드 구현 설명주요 구현 단계:그래프 생성 graph = [[] for _ in range(v + 1)] for u, w in edges: .. 2025. 2. 19. 해결한 문제 간단 리뷰(2.8~2.13) 기억에 남는 문제들문제번호문제이름문제설명상세리뷰 33277국방시계비례식:#24시간은 60*24분 1440분 , 충복무일수:복무일수=1440:x, 복무일수*1440/총복무일수=x b320310타노스0과 1을 반으로 줄여서 사전순 최선의 숫자 만들기 0은 최대한 뒤의 것을 지우고 1은 최대한 앞의 것을 지움(0,1의 개수를 세고 앞에서부터 한 글자씩 읽으면서 0은 절반개수만큼 포함, 1은 절반개수만큼 참았다가 포함. s314624전북대학교스트링 아트 모앙출력 반복문 연습문제 b210827a^b1보다 작은 소수를 제곱하면 정수부가 나오지 않고 소수부만 늘어나고 원래의 소수부길이의 2배가 되는 것을 이용하며 따로 계산예정g59414프로그래밍 대회 전용 부지정렬을 통해 큰 지수승을 작은 수가 받도록 계산 s458.. 2025. 2. 13. 백준9465🐨스티커🚀동적프로그래밍 문제상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 .. 2024. 12. 25. 백준18005🐨Even or Odd? https://www.acmicpc.net/problem/18005문제의 주요 조건을 살펴보자.picked n consecutive positive integers between 1 and 1018 guess if their sum is even or oddIf the sum must be even, write 2.If the sum must be odd, write 1.If the sum could be even or could be odd, write 0.The single line of input contains a single integer n (1 ≤ n ≤ 109). 일련의 n개 수의 합이 홀수가 되거나 짝수가 되는 것은홀수로 시작하는지 짝수로 시작하는지가 영향을 줄 것이다.홀수로 시작하는.. 2024. 8. 6. 🚧Intro2Algo🐨22장.기본 그래프 알고리즘 (01)그래프의 표현 G=(V,E)의미G (Graph): 그래프 자체, 정점들과 그 정점들을 연결하는 간선들의 집합.V (Vertices): 정점 집합. Vertex의 복수형으로, 그래프의 각 노드 또는 점.E (Edges): 간선 집합. 정점들을 연결하는 선.G=(V,E)는 "그래프 G는 정점들의 집합 V와 간선들의 집합 E로 구성된다"는 것을 수학적으로 표현한 것.그래프 G=(V,E)를 표현하기 위해서는 두 가지 표준 방법이 있음.1. 인접 리스트의 집합- 작은 밀도(|E|가|V|2보다 훨씬 작음) 그래프에 대해 효율적(Sparse Graph |E|≪|V|2 조건을 만족)2. 인접 행렬두 방법 모두 무방향 그래프에 적용할 수 있다.무방향 그래프 정점5개 간선 7개인접 리스트.. 2024. 8. 6. 이전 1 2 3 4 ··· 6 다음
