Tech/Coding113 바이트배열을 이용한 에라토스테네스의 체와 그 업그레이드 버전 바이트 배열을 이용한 에라토스테네스의 체가 가장 빠르다는 실험을 했는데 다른 방법을 찾았다.바이트 배열에 홀수만 저장하는 것이다.메모리를 반만 쓸 수 있다.그리고 온라인 저지 상에서는 더 빨랐다.실제로는 좀 더 느리지만 근소한 차이를 보였다.메모리까지 종합적으로 보면 더 우수하다고 할 수 있다.그리고 내가 살짝 튠을 해 보니 조금 더 빠르게 할 수 있었다.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. 후위표기식 def s(): v=[open(0).read().strip(),[],''] p={'+':1,'-':1,'*':2,'/':2} for c in v[0]: if c.isalpha():v[2]+=c elif c=='(':v[1].append(c) elif c==')': while v[1]and v[1][-1]!='(':v[2]+=v[1].pop() v[1].pop() else: while v[1]and v[1][-1]!='('and p[v[1][-1]]>=p[c]:v[2]+=v[1].pop() v[1].append(c) while v[1]:v[2]+=v[1].p.. 2025. 1. 30. 14930🐨구슬 (BEAD)-파이 구슬 (BEAD)시간 제한메모리 제한2 초512 MB문제물리를 사랑하는 민준이는 집에 마찰이 없는 무한한 수직선과 완전탄성충돌을 하고 질량이 동일하며 크기를 무시할 수 있는 구슬 N(1 ≤ N ≤100,000)개를 구비해놓고 있다. 어느 날 민준이는 모션캡처분석기기를 활용하기 위해 N개의 구슬 중 하나만 빨간색으로 색칠한 뒤 실을 연결해 N중 진자 실험을 하고 있었다. 이를 해석역학적으로 분석하며, r과 θ의 관계를 파악하던 중 구슬의 질량에 의한 장력을 이기지 못한 실들이 한 번에 끊어져 수직선 위에 널부러지게 되었다. 각각 다른 위치 xi에 떨어져 저마다의 초속도 vi를 가지고 운동하게 된 구슬을 보며 민준이는 가슴 아파 했지만 곧 새로운 물리 문제를 떠올리는 데에 성공한다! 바로 t(1 ≤ t ≤1.. 2025. 1. 27. 32777번 가희와 서울 지하철 2호선 가희와 서울 지하철 2호선서울 지하철 2호선은 3개의 노선으로 이루어져 있으며, 순환선을 운행하는 열차는 내선 순환과 외선 순환 중 하나의 방향으로 운행합니다.노선 정보본선 순환선: 201번 역부터 243번 역까지 총 43개 역신정지선 (신도림 ~ 까치산)성수지선 (성수 ~ 신설동)내선 순환 열차의 인접역은 아래와 같습니다:243번 역의 인접역은 201번 역입니다.i번 역의 인접역은 i+1번 역입니다. (단, 201 ≤ i ≤ 242)외선 순환 열차의 인접역은 아래와 같습니다:201번 역의 인접역은 243번 역입니다.i번 역의 인접역은 i-1번 역입니다. (단, 202 ≤ i ≤ 243)문제 설명가희는 2호선만을 이용하여 a번 역에서 b번 역으로 이동하려고 합니다. 마침, 외선 순환 열차와 내선 순환 열.. 2025. 1. 23. 백준#9291🐨스도쿠 채점::s4-파이썬 스도쿠 채점 프로그램스도쿠는 일본어로 "수독(數獨)"을 읽은 것이며, 9x9 격자판에서 다음 조건을 만족하도록 숫자를 채워 넣는 게임입니다:각 정수 1-9는 각 행에 정확히 한 번씩 등장해야 합니다.각 정수 1-9는 각 열에 정확히 한 번씩 등장해야 합니다.각 정수 1-9는 각 작은 3x3 정사각형에 정확히 한 번씩 등장해야 합니다.남규는 스도쿠를 풀었지만, 그것이 올바른 정답인지 확인하는 데 어려움을 겪고 있습니다. 이에 따라 완성된 스도쿠 판이 정답인지 확인하는 프로그램을 작성해야 합니다.입력입력의 첫 줄에는 테스트 케이스의 개수가 주어집니다.각 테스트 케이스는 9개의 줄로 이루어져 있으며, 각 줄에는 9개의 정수가 공백으로 구분되어 있습니다. 각 정수는 1 이상 9 이하입니다.테스트 케이스 사이에는.. 2025. 1. 22. 15889🐨호 안에 수류탄이야!!-파이썬-스위핑 호 안에 수류탄이야!!"호 안에 수류탄!!"대한건아 욱제는 수류탄 투척 훈련을 받고 있다. 욱제를 필두로, 훈련장에는 욱제를 포함한 N명의 전우들이 일렬(1열 횡대)로 서 있다. 군대에 끌려온 사실에 심술이 난 욱제는 수류탄의 안전핀을 뽑아 전우에게 던졌다. 마찬가지로 심술이 난 전우들도 욱제가 던진 수류탄을 받아 전우들에게 던지기 시작했다.이제 수류탄은 뜨거운 감자처럼 욱제와 전우들 사이를 옮겨 다닌다. 전우들은 팔 힘이 모두 다르기 때문에 수류탄을 던질 수 있는 사거리도 모두 다르다. 욱제와 전우들이 가지고 노는 훈련용 수류탄은 바닥에 떨어지기 전에는 절대 터지지 않는 특수한 수류탄이다.욱제와 전우들은 특급 전사이기 때문에 사거리 내에 있는 누구에게나 정확히 수류탄을 던질 수 있고, 마찬가지로 정확히.. 2025. 1. 22. 🐨이진 검색 트리 이진 검색 트리이 문제는 배열 P를 사용하여 이진 검색 트리를 생성한 후, 모든 노드의 높이 합을 구하는 알고리즘을 구현하는 문제입니다. 문제 원문은 아래와 같습니다:문제 원문시간 제한: 2 초메모리 제한: 256 MB문제:P는 크기가 N인 배열이다. P에는 0보다 크거나 같고, N-1보다 작거나 같은 정수가 중복 없이 채워져 있다. 이진 검색 트리는 루트가 있는 이진 트리로, 각각의 노드에 정수 값이 저장되어 있는 트리이다. 이진 검색 트리를 P배열을 이용해서 만드는 법은 다음과 같다. 일단 root를 만들고 거기에 P[0]의 값을 넣은 후에 다음과 같은 과정을 거친다.for (int i=1; iN과 배열 P에 있는 수가 주어졌을 때, P로 이진 검색 트리를 만들었을 때 모든 노드의 높이의 합을 출력하.. 2025. 1. 19. 이전 1 2 3 4 5 6 7 8 다음
