본문 바로가기

Tech/Coding113

위상 정렬 (Topological Sort) “누가 먼저?”를 정리하는 기술: 위상 정렬 (Topological Sort)게임 퀘스트를 하다 보면 이런 말을 종종 본 적 있을 것이다. “퀘스트 A를 완료한 뒤에만 퀘스트 B를 할 수 있습니다.” 혹은 학교에서는 “수학II는 수학I을 들은 다음에 수강할 수 있습니다.” 이처럼 어떤 작업이 선행되어야 하는 관계가 있을 때, 우리는 전체 순서를 어떻게 정할 수 있을까?1. 위상 정렬이란?위상 정렬(topological sort)은 순환이 없는 유향 그래프(DAG)에서 모든 노드를 선행 조건을 지키면서 순서대로 나열하는 알고리즘이다.예제: 과목 이수 순서수학I → 수학II물리학 → 전자회로수학II → 전자회로이 경우 전체 이수 순서는 수학I → 수학II → 물리학 → 전자회로 또는 물리학 → 수학I → 수.. 2025. 4. 19.
파이썬 heapq.heapreplace 동작 원리 파이썬 heapq.heapreplace 동작 원리heapreplace는 파이썬의 heapq 모듈에서 제공하는 유용한 함수로, 힙의 최솟값을 제거하고 새로운 값을 넣은 뒤, 힙을 재정렬하여 항상 최소 힙(min heap)의 조건을 유지하는 함수다.📌 기본 개념heapreplace(heap, item)은 다음과 같은 동작을 한다:힙의 루트(가장 작은 값)를 제거한다.새로운 값을 루트 자리에 넣는다.힙 조건(부모 📊 힙 구조 시각화 예제다음은 heap = [1, 3, 5, 7, 9, 11]일 때 heapreplace(heap, 2)가 어떻게 작동하는지 단계별로 나타낸 것이다.1️⃣ 초기 힙 구조 1 / \ 3 5 / \ \ 7 9 11 2️⃣ 루.. 2025. 4. 12.
파이썬 heapq : 힙큐 사용법 정리 🔍 힙(Heap)이란?힙은 완전 이진 트리 기반의 자료구조로, 최솟값이나 최댓값을 빠르게 찾을 수 있도록 정렬된 구조이다.최소 힙 (Min Heap): 부모 노드 ≤ 자식 노드최대 힙 (Max Heap): 부모 노드 ≥ 자식 노드파이썬의 heapq는 최소 힙을 기본으로 제공한다.📦 heapq란?파이썬 표준 라이브러리 heapq는 리스트를 힙처럼 다룰 수 있도록 해주는 함수 모음이다.import heapq🧩 heapq 함수 정리함수명설명heapq.heappush(heap, item)힙에 item 삽입heapq.heappop(heap)힙에서 가장 작은 원소 꺼냄heapq.heapify(iterable)리스트를 힙 구조로 변환heapq.heappushpop(heap, item)item 삽입 후 최소값 제.. 2025. 4. 11.
Python 고속 입력 처리법 🧵 Python 고속 입력 처리법:io.BufferedReader(io.FileIO(0), 1 은 왜 빠를까?Python으로 알고리즘 문제를 풀 때 input()이나 sys.stdin.readline()이 너무 느려서 시간 초과가 나는 경우가 있다.그럴 때 등장하는 구문이 바로 아래 코드다.import ioinput = io.BufferedReader(io.FileIO(0), 1 이 구문은 무려 최대 10배 이상 빠른 입력 처리가 가능하다.왜 이렇게 빠른지 아래에서 구조와 원리를 상세히 설명한다.🧠 Python 표준 입력은 어떻게 동작할까?Python의 입력은 보통 다음처럼 동작한다:input(): 한 줄 읽고 문자열 반환sys.stdin.readline(): 조금 더 빠르게 문자열 반환이 방식들은 .. 2025. 4. 11.
RSA 암호화와 모듈러 연산 개념 정리 1. RSA 암호화 알고리즘 기초1.1 RSA란?공개 키(Public Key)와 개인 키(Private Key)를 사용하는 비대칭 암호화 알고리즘이다.소인수 분해가 어려운 수학적 성질을 이용하여 보안을 확보한다.1.2 키 생성 과정두 개의 작은 소수 $p = 3$, $q = 11$ 선택$n = p \times q = 3 \times 11 = 33$오일러 함수: $\varphi(n) = (p - 1)(q - 1) = 2 \times 10 = 20$공개 키 지수 $e = 7$ 선택 (조건: $\gcd(7, 20) = 1$)개인 키 지수 $d$ 계산: $$ ed \equiv 1 \mod{20} \Rightarrow 7 \cdot d \equiv 1 \mod{20} $$ → $d = 3$ (왜냐하면 $7 \cd.. 2025. 4. 5.
RSA 암호화 알고리즘의 원리와 예시 RSA(Rivest-Shamir-Adleman)는 현대 정보 보안에서 가장 널리 사용되는 공개 키 암호화 알고리즘이다. 1977년 MIT의 연구자인 론 리베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman)이 개발하였으며, 이들의 이름 앞글자를 따서 RSA라는 이름이 붙었다.이 글에서는 RSA의 수학적 원리, 키 생성 과정, 암호화 및 복호화 방식, 그리고 실제 문제 풀이를 통해 RSA 알고리즘을 자세히 알아본다.1. RSA 암호화 알고리즘이란?RSA는 공개 키와 개인 키라는 두 가지 키를 사용하는 비대칭 키(Asymmetric-key) 암호화 방식이다. 여기서 공개 키는 데이터를 암호화할 때 사용되고, 개인 키는 데이터를 복호화할 때 사용된다. .. 2025. 4. 5.
PS(Problem Solving)에서의 컨볼루션과 컴퓨터 비전(CV, Computer Vision)에서의 컨볼루션 PS(Problem Solving)에서의 컨볼루션과 컴퓨터 비전(CV, Computer Vision)에서의 컨볼루션은 이름은 같지만 목적과 구현이 꽤 다릅니다.🎯 핵심 비교 요약항목   항목 PS에서의 컨볼루션 CV에서의 컨볼루션 목적수열/다항식 연산, 경우의 수 계산, 패턴 매칭 등이미지 필터링, 특징 추출, 패턴 인식수학적 정의선형 컨볼루션 (다항식 곱셈과 유사)2D 필터 커널을 슬라이딩하며 합성곱연산 대상1차원 수열 (또는 다항식)2차원 행렬 (이미지)연산 방식전 수열에 걸쳐 계산 (global)커널을 국소 영역에 적용 (local)알고리즘FFT로 고속화CNN 등에서 커널 학습대표 응용조합/경우의 수 문제, 문자열 패턴 매칭엣지 검출, 블러링, CNN 이미지 분류🔍 구체적인 차이1. 연산 대상.. 2025. 3. 31.
1067번 이동 이동시간 제한메모리 제한1 초512 MB문제$N$개의 수가 있는 $X$와 $Y$가 있다. 이때 $X$나 $Y$를 순환 이동시킬 수 있다. 순환 이동이란 마지막 원소를 제거하고 그 수를 맨 앞으로 다시 삽입하는 것을 말한다. 예를 들어, ${1, 2, 3}$을 순환 이동시키면 ${3, 1, 2}$가 될 것이고, ${3, 1, 2}$는 ${2, 3, 1}$이 된다. 순환 이동은 $0$번 또는 그 이상 할 수 있다. 이 모든 순환 이동을 한 후에 점수를 구하면 된다. 점수 $S$는 다음과 같이 구한다.$$S = X[0]×Y[0] + X[1]×Y[1] + ... + X[N-1]×Y[N-1]$$이때 $S$를 최대로 하면 된다.입력첫째 줄에 $N$이 주어진다. 둘째 줄에는 $X$에 들어있는 $N$개의 수가 주어진다.. 2025. 3. 30.
Black and White Stones 문제 개요검은 돌과 흰 돌이 섞여 일렬로 놓여 있습니다. 이 게임에서 플레이어는 돌들을 움직여 모든 검은 돌을 왼쪽으로, 모든 흰 돌을 오른쪽으로 모으는 것이 목표입니다. 하지만 돌을 옮길 때마다 코인이 들기 때문에, 최대한 적은 비용으로 목표를 달성해야 합니다. 최소한의 코인 비용으로 돌들을 정렬하는 방법을 찾아보겠습니다.예시작은 예로 초기 배치가 BWWB (B는 검은 돌, W는 흰 돌)인 경우를 생각해봅시다.위치1234초기BWWB목표BBWW이 예시에서 A = 2, B = 1이라면 인접 교환은 1코인, 비인접 교환은 2코인이 됩니다.해결 전략왼쪽의 흰 돌과 오른쪽의 검은 돌을 서로 교환해야 합니다. 이때 직접 교환할지, 인접 교환을 여러 번 할지를 비용 비교를 통해 결정합니다.직접 교환: A 코인인접 .. 2025. 3. 29.
백준 28237번 문제 풀이 - 수학 선생님의 고민(Easy) 문제 분석주어진 이차식은 다음과 같다. $nx^2 + (n+1)x - (n+2)$이를 정수 범위 내에서 인수분해 가능한지 판별하고, 가능하면 인수분해의 형태를 출력하는 문제이다.풀이 방법이 문제는 이차식을 정수 범위 내에서 인수분해하기 위한 정수 계수의 조합을 찾는 것이 핵심이다.일반적인 형태의 인수분해는 다음과 같다. $(ax + b)(cx + d) = acx^2 + (ad + bc)x + bd$즉, 이 문제에서는 아래의 방정식을 만족해야 한다.$ac=n$$ad+bc=n+1$$bd=−(n+2)$알고리즘 설계모든 $a,c$의 조합을 찾는다. 이 때, $ac=n$ 이므로 $n$의 모든 약수 조합을 탐색한다.각각의 조합에 대해 $bd=−(n+2)$를 만족하는 $b,d$의 조합을 찾는다. 즉, $−(n+2)$.. 2025. 3. 27.
Python의 memoryview 객체 심층 분석 Python의 memoryview 객체 심층 분석파이썬의 memoryview 객체는 버퍼 프로토콜을 지원하는 객체의 메모리에 직접 접근할 수 있는 기능을 제공합니다. 이를 통해 대용량 데이터 처리 시 메모리 복사를 최소화하여 성능을 향상시킬 수 있습니다. 이 글에서는 memoryview의 저수준 동작 원리와 다양한 활용 사례를 심도 있게 다루고자 합니다.1. 메모리뷰의 저수준 동작 원리파이썬은 내부적으로 버퍼 프로토콜을 사용하여 객체의 메모리에 직접 접근할 수 있도록 설계되어 있습니다. memoryview는 이러한 버퍼 프로토콜을 구현한 객체에 대한 뷰를 제공하며, 이를 통해 데이터 복사 없이도 메모리에 직접 접근할 수 있습니다. 이는 C 언어의 포인터 개념과 유사하며, 메모리 효율성을 크게 향상시킵니다.. 2025. 3. 11.
Python의 memoryview와 cast() 활용 Python의 memoryview와 cast() 활용1. memoryview란?memoryview는 파이썬에서 제공하는 강력한 기능 중 하나로, bytes 또는 bytearray 같은 바이너리 데이터를 복사 없이 조작할 수 있도록 해줍니다.이 기능을 사용하면 데이터의 복사를 최소화하여 성능을 최적화할 수 있습니다.예제 1: 기본적인 memoryview 사용data = bytearray([0, 10, 20, 30, 40, 50])view = memoryview(data)print(view[1]) # 10view[1] = 100print(data) # bytearray(b'\x00d\x14\x1e(2') 2. cast()를 활용한 데이터 변환memoryview의 cast() 메서드를 사용하면 데이터.. 2025. 3. 10.
16561🐨3의 배수 python 3의 배수를 덧셈으로 나타내는 방법의 가짓수를 구하는 문제이므로, 가장 단순한 경우인 3의 덧셈만으로 3의 배수를 표현하는 방법을 생각해 보자.예를 들어, 9를 고려해 보자.3 3 3여기서 덧셈 기호를 넣을 수 있는 자리는 두 군데이며, 우리는 세 개의 3을 사용해야 하므로 두 개의 덧셈 기호를 반드시 넣어야 한다. 따라서 가능한 방법은 한 가지뿐이다.이제 12의 경우를 살펴보자.3 3 3 3첫 번째 칸에 덧셈 기호를 넣으면 나머지 두 칸 중 하나를 선택할 수 있으며, 첫 번째 칸이 아닌 두 번째 칸에 덧셈을 넣으면 남은 한 칸에만 추가할 수 있다. 따라서 가능한 경우의 수는 \( 2+1=3 \) 가지가 된다.더 큰 수인 21의 경우를 살펴보고 일반화해 보자.3 3 3 3 3 3 3여기서 두 개의 덧셈 .. 2025. 3. 9.
(작성중)교차 매칭 (Crossed Matchings) 교차 매칭 (Crossed Matchings)시간 제한메모리 제한1 초128 MB문제양의 정수가 적힌 두 행이 있습니다. 첫 번째 행에 있는 숫자와 두 번째 행에 있는 숫자 중 서로 값이 같은 r인 두 숫자 사이에 선분을 그을 수 있습니다. 이 선분을 r-매칭 선분이라고 부릅니다. 아래 그림은 3-매칭과 2-매칭 선분을 보여줍니다.주어진 입력에 대해 다음 조건을 만족하면서 그릴 수 있는 최대 매칭 선분의 수를 찾고자 합니다:1. 각 a-매칭 선분은 정확히 하나의 b-매칭 선분과 교차해야 합니다. 단, a ≠ b입니다. 2. 한 숫자에서 두 개의 매칭 선분을 그릴 수 없습니다. 예를 들어, 다음과 같은 매칭은 허용되지 않습니다.입력 데이터에 대한 최대 매칭 선분의 수를 계산하는 프로그램을 작성하세요. 이 .. 2025. 3. 7.
33167번 - じゃんけん (Rock-Scissors-Paper) 33167번 - じゃんけん (Rock-Scissors-Paper)가위바위보 (Rock-Scissors-Paper)길이 N의 문자열 S, T가 주어진다. S의 각 문자는 R 또는 S 중 하나이다. T의 각 문자는 R 또는 P 중 하나이다.아오이와 비타로는 N번의 가위바위보를 했다. 아오이가 i번째(1 ≤ i ≤ N) 가위바위보에서 낸 것은 S의 i번째 문자가 R일 때는 바위, S일 때는 가위이다. 비타로가 i번째(1 ≤ i ≤ N) 가위바위보에서 낸 것은 T의 i번째 문자가 R일 때는 바위, P일 때는 보이다.전체 N번의 가위바위보에서 아오이가 이긴 횟수와 비타로가 이긴 횟수를 구하시오.입력입력은 다음 형식으로 주어진다.NST출력전체 N번의 가위바위보에서 아오이가 이긴 횟수와 비타로가 이긴 횟수를 단위(회.. 2025. 3. 3.

티스토리툴바