Doby's Lab

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net Solved By: Knapsack DP 처음으로 시도해본 Knapsack DP문제입니다. 이론을 공부하면서 코드를 써봤는데 아직 완전히 이해되지는 않았습니다. 각 아이템 당 무게와 가치는 pair형 배열을 선언하여 저장해주었습니다. #include using namespace std; int n, k; int cache[101][..

https://www.acmicpc.net/problem/20301 20301번: 반전 요세푸스 첫째 줄에 정수 $N$, $K$, $M$이 주어진다. ($1 \leq N \leq 5\ 000$, $1 \leq K, M \leq N$) www.acmicpc.net Solved By: Deque 뺀 사람의 수가 M명이 되었을 경우, 방향을 바꿔야 하기 때문에 큐가 아닌 덱을 사용하여 양방향을 고려하게 해주고, M명이 되었을 때 bool type flag변수를 사용하여 방향을 바꿀지 말지에 대한 여부를 설정해줬습니다. #include #include using namespace std; int main(){ ios_base::sync_with_stdii(false); cin.tie(NULL); int n, k..

파이썬 기본 문법 챙길 겸 올솔 배경이 예쁘길래 한 번 시간 내어서 해봤습니다😁😁

https://www.acmicpc.net/problem/24262 24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 www.acmicpc.net Solved By: thinking(?) 주어진 함수는 인덱스에 접근하므로 시간 복잡도는 O(1)입니다. 그리고, Recursive Call도 아니고 일반 함수이므로 1번 호출됩니다. #include #include using namespace std; int main(){ int n; cin >> n; cout

https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net Solved By: MST, DFS 최대 스패닝 트리를 만들어서 해당하는 edge들끼리 인접 리스트를 구성하고, 인접 리스트로 DFS를 돌리면서 s에서 e로 가는 길 중 최솟값을 구하면 됩니다. #include #include #include #define MAX 100001 #define ll long long #define INF 1e9 using na..

C++을 공부했던 것처럼 CodeUp 기초 100제를 통해 Python 기본 문법을 공부했습니다. PS를 하면서 Python을 써보고 싶다거나 다른 프로그래밍을 할 때, Python을 쓸 일이 많아질 거 같아 더 이상 미룰 수 없다고 생각했고, 지금이 최적의 타이밍이 아닌가 했습니다. 풀면서 배워두어야 할 문법들에 관련된 문제들로 정리 해두었습니다. 6005 print("\"Hello World\"") 큰 따옴표나 작은따옴표는 C++처럼 앞에 \(역슬래시)를 붙여주면 출력할 수 있습니다. 6011 n = float(input()) print(n) 파이썬에서 실수형은 float을 사용합니다. C++에서는 범위에 따라 double이나 long double을 사용할 일이 많았는데 파이썬은 없는 거 같군요. 6..

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net Solved By: Segment Tree 저번에도 포스팅했던 문제이지만 세그트리 관련 문제를 푼 지가 오래되어서 다시 풀어보았습니다. 구성은 다행히 기억하고 있더군요. 다만 원래 배열 값에도 업데이트를 하지 않아서 맞왜틀을 시전하고 있었습니다...ㅎ #include #define MAX 1000001 #define ll long long..

https://www.acmicpc.net/problem/4233 4233번: 가짜소수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, p와 a를 포함하고 있다. 입력의 마지막 줄에는 "0 0"이 주어진다. (2 < p ≤ 1,000,000,000, 1 < a < p) www.acmicpc.net Solved By: Exponentiation By Squaring, Primality Test 페르마의 소정리 개념을 공부하려다가 풀게 된 문제입니다. 입력값으로 p와 a가 들어오면 a ^ p를 구하고 p로 나누었을 때, a인지 판정 후에 나누었던 p가 소수인지 아닌지를 판정하면 끝나는 문제입니다. 다만, int형의 오버플로우, 분할 정복을 이용한 거듭제곱, Mo..