본문 바로가기

공부67

파이썬 자주 사용하는 라이브러리 모음 - 코테 꿀팁 1. mathimport mathprint(math.factorial(5)) # 5! = 120print(math.gcd(36, 60)) # 최대공약수(GCD) = 12print(math.sqrt(25)) # 제곱근 = 5.0print(math.ceil(3.1)) # 올림 = 4print(math.floor(3.9)) # 내림 = 32. itertoolsimport itertoolsarr = [1, 2, 3]# 순열 (3개 중 2개를 선택하는 모든 경우) -> 순서 의미 있음print(list(itertools.permutations(arr, 2)))#[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]# 조합 (3개 중 2개를 뽑는 경우) -> 순서 .. 2025. 3. 22.
2D 누적 합(Prefix Sum) 기법 이런게 있더라고요. 2D 누적 합은 이차원 배열(행렬)에서 특정 부분 영역의 합을 빠르게 계산해야 할 때 주로 사용됩니다. 언제 사용 할까요?1. 특정 부분 영역의 합을 자주 계산할 때 (O(1)로 최적화) 기본적으로 특정 부분의 합을 구하려면 O(N*M)이 걸리지만, 누적 합 배열을 미리 만들어두면 O(1)로 구할 수 있음.ex) 2D 배열에서 (r1, c1)부터 (r2, c2)까지의 합을 여러 번 구해야 하는 경우 부분 합 = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1] 2. 다차원 배열에서 특정 범위를 여러 번 업데이트해야 할 때 (차이 배열과 함께 사용) 특정 영역을 업데이트하는 연산이 많을 때, 차이 배열(D.. 2025. 3. 21.
배낭 문제(Knapsack Problem) 제한된 용량을 가진 상태에서 여러 개의 아이템을 선택하여 최대 가치를 구하는 방식입니다. 이때 아이템의 무게를 나눌 수 있는지 없는지로 나눠집니다. 1. 0-1 배낭 문제 각 아이템은 선택하거나(1) 선택하지 않거나(0) 두 가지 경우만 존재할 경우DP를 사용하여 해결하며, 시간 복잡도는 O(nW)문제 정의배낭의 최대 용량이 Wn개의 아이템이 있으며, 각 아이템 i는 무게 w[i]와 가치 v[i]를 가진다.배낭에 넣을 수 있는 최대 가치를 구하는 것이 목표이다. 코드# 0-1 Knapsack Problem (Dynamic Programming)def knapsack_01(W, weights, values, n): dp = [[0] * (W + 1) for _ in range(n + 1)] .. 2025. 2. 28.
알고리즘 접근 방법 1. 문제를 읽고 이해한다.2. 문제를 익숙한 용어로 재정의한다.3. 어떻게 해결할지 계획을 세운다.4. 계획을 검증한다.5. 프로그램으로 구현한다.6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다. 나는 보통 계획을 세운 후(3번) 바로 구현하려고 하는데 검증하는 과정(4번)을 추가해야겠다. 작은 기능에서 시작해서 점차 키워가기 => 점진적 개선문제를 풀 수는 없더라도 해결법을 알아가는데 도움을 줌 2025. 2. 24.
C++ - stack, que, deque, priority_que 자료구조 특징 삽입 삭제조회Stack (LIFO)후입선출push()pop()top()Queue (FIFO)선입선출push()pop()front(), back()Priority Queue우선순위 높은 원소가 먼저 나감push()pop()top()Deque양쪽 삽입/삭제 가능push_back(), push_front()pop_back(), pop_front()front(), back() 어떤 것을 써야 할까?스택: "뒤집기", "DFS", "연산기록 저장"큐: "선입선출", "BFS", "작업 스케줄링"우선순위 큐: "최댓값/최솟값 관리", "힙(Heap) 활용"덱: "양방향 삽입/삭제", "슬라이딩 윈도우" 2025. 2. 22.
String을 replace 하는 방법들 방법사용목적코드str.replace(위치, 길이, 새 문자열)특정 위치의 문자열을 변경str.replace(6, 5, "C++");std::regex_replace()여러 개의 특정 문자열 변경(정규식 가능)std::regex_replace(str, std::regex("apple"), "banana")std::replace()특정 문자 변경std::replace(str.begin(), str.end(), 'a', 'X');std::string::find() + replace()문자열 전체 변경 (반복)while ((pos = str.find(...)) != std::string::npos) str.replace(...);std::erase() + std::remove()특정 문자 제거str.erase(.. 2025. 2. 22.

티스토리툴바