전체 글72 GCD(최대공약수), LCM(최소공배수) C++ 구현 최대공약수(GCD, Great Common Divisor)과 최소공배수(LCM, Least Common Multiple)을 구해보자 최대 공약수 최대공약수는 나머지 연산을 활용하는 유클리드 호제법을 이용하여 쉽게 구할 수 있다. 입력으로 들어온 두 수 a,b에 대하여 b = a*k +r이라 표현하면 a,b의 최대 공약수는 a,r의 최대공약수와 같다는 원리를 이용한다. 1) 반복문을 사용 int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a; } 2) 재귀함수 사용 int gcd(int a, int b){ if(b == 0) return a; // b == 0 인경우 더 이상 최대 공약수를 갖지 않아서 a 반환 el.. 2022. 6. 14. [BOJ] 3460번 - 이진수 주어진 10진수를 2진수로 나타내어 1의 위치를 표시하는 문제이다. %와 / 연산자를 통해 이진수를 구하고 1인 경우만 출력해주도록 한다. 테스트 케이스마다 자리를 표시하는 count를 0으로 초기화해야 한다. #include using namespace std; int T, n, num; int main() { cin.tie(0); ios_base::sync_with_stdio(false); cin >> T; while (T--) { cin >> n; int count = 0; while (n > 0) { num = n % 2; n /= 2; if (num == 1) cout 2022. 6. 14. [BOJ] 2501번 - 약수 구하기 단순 약수문제. 문제 조건상 N이 10000 이하 이므로 브루트포스로 탐색하면 clear. 약수의 개수가 K보다 작은 경우 0을 출력하는 조건을 빼먹지 않도록 한다. #include #include #include using namespace std; int main() { cin.tie(0); ios_base::sync_with_stdio(false); int N, K; int count = 0; cin >> N >> K; for (int i = 1; i 2022. 6. 14. 코딩 테스트 대비 백준 문제 추천 백준 문제 풀이를 하면서 풀어야 할 알고리즘 파트를 정하긴 했지만 누군가 정리해놓은 게 없을까 하여 구글링하다가 좋은 내용을 찾아 링크 남깁니다. https://covenant.tistory.com/224 코딩테스트 대비를 위한 백준 문제 추천 코딩테스트 대비를 위한 백준 문제 추천 끝 없는 훈련만이 실전에서 흐트럼없이 정답을 향해서 움직일 수 있습니다. (Photo by Specna Arms on Unsplash) 작년 한 해 수많은 코딩테스트를 직접 경험하고 covenant.tistory.com 2022. 6. 14. [BOJ] 2740번 - 행렬 곱셈 단순 수학, 구현 문제이다. 행렬의 곱셈을 코드화할 수 있다면 쉽게 풀 수 있다. res[i][j] += A[i][k] * B[k][j]; 이 부분이 행렬의 곱셈을 구현한 부분이다. #include #include #include using namespace std; int N, M, K; int A[101][101]; int B[101][101]; int res[101][101]; int main() { cin.tie(0); ios_base::sync_with_stdio(false); cin >> N >> M; for (int i = 0; i > A[i][j]; } cin >> M >> K; for (int i = 0; i.. 2022. 6. 14. [BOJ] 17298번 - 오큰수 스택을 활용하여 문제를 풀었다. 조건) 자기 자신 보다 오른쪽에 있는 수 중 크고 가장 왼쪽에 있는 숫자를 출력하고 없는 경우에는 -1을 출력한다. vector v에 입력값을 넣고 vector ans는 -1 값으로 초기화 시켜준다. 문제의 조건을 만족하고 stack이 비어있지 않을 경우 vector ans에 값을 넣어준다. #include #include #include using namespace std; int N; int main() { cin.tie(0); ios_base::sync_with_stdio(false); cin >> N; vector v; int num; for (int i = 0; i > num; v.push_back(num); } vector ans(.. 2022. 6. 14. [BOJ] 2493번 - 탑 자기 자신보다 왼쪽에 있으며 가장 가깝고 높이가 높은 탑의 인덱스값을 출력하는 문제이다. 스택을 활용하여 오른쪽에서 왼쪽으로 높이를 비교하여 답을 찾는 방식을 사용하였다. 처음에는 2중for문으로 그냥 돌려버렸더니 답은 나왔지만 시간 초과가 걸려버렸다. 해당 2중 for문에 대한 코드만 while문을 사용하여 시간제한을 해결하였다. 스택에는 가장 우측부터 탑의 높이와 인덱스를 저장한다. 자기자신보다 높은 탑을 만나면 res배열에 답을 저장하고 처음 res배열은 전역변수로 0으로 초기화 하였기 때문에 자기자신보다 높은 탑을 만나지 못한 경우는 자동적으로 답이 0으로 출력된다. #include #include using namespace std; int N, num; int flag = 1; int ans;.. 2022. 6. 14. [BOJ] 1874번 - 스택 수열 스택의 개념을 활용하여 입력된 수열의 형태를 표현하는 문제이다. 코드 작성 시 조건은 다음과 같다. 1. 스택에서 push하는 경우 + 출력 이 때 스택에 push하는 순서는 반드시 오름차순을 지킨다. 2. 스택에서 pop하는 경우 - 출력 3. 주어진 수열의 형태를 push, pop 연산으로 표현하지 못하는 경우 NO 출력 vector를 활용하여 스택처럼 사용하였다. 코드 작성 단계를 살펴보면 1. input 배열에 주어진 순열 값을 차례로 집어넣는다. 2. int형 vector v에 1부터 오름차순으로 숫자를 push_back하고 char형 vector res에 +를 push_back한다. 3. vector v가 비어있지 않고 input 배열의 값과 vector v의 마지막 요소를 반환한 back().. 2022. 6. 13. [BOJ] 18870번 - 좌표 압축 주어진 값에 대하여 중복을 허용하여 순서를 매기는 문제이다. 간단하게 sort(), vector와 pair 클래스를 이용하여 해결했다. -- pair pair구조체를 sort할 경우 first를 기준으로 오름차순을 진행하고 second값은 first값을 따라간다. 입력값 tmp vector tmp.first tmp.second 2 0 4 1 -10 2 4 3 -9 4 정렬된 tmp vector tmp.first tmp.second -10 2 -9 4 2 0 4 1 4 3 tmp vector의 num값 중복을 고려한 res vector 입력 res.first res.second 2 0 4 1 0 2 1 3 3 3 정렬된 res vector res.first res.second 0 2 1 3 2 0 3 3 .. 2022. 6. 13. 이전 1 ··· 4 5 6 7 8 다음
