본문 바로가기

📕 STUDY/Algorithm

(19)

[C / C++] 백준 11651번 - 좌표 정렬하기 2 https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net ✅ 문제 설명 숫자 N을 입력한 후 N개의 x, y좌표를 입력하면, y좌표를 중심으로 오름차순으로 정렬하여 출력하는 문제이다. ✅ 알고리즘 설명 y좌표를 기준으로 오름차순으로 정렬하되 y좌표가 같으면 x좌표를 비교해야 하는 문제이다. 따라서 간단하게 C++ STL sort()를 사용해서 풀었다. 💡 sort() vector에 있는 값을 정렬..

[C / C++] 백준 1003번 - 피보나치 함수 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net ✅ 문제 설명 테스트 케이스 T를 입력한 후 T개의 숫자 N을 입력하면, N의 피보나치 수열에서 0과 1이 몇 번 출력되는지 묻는 문제이다. ✅ 알고리즘 설명 1. 일반 피보나치 함수 처음에는 C를 사용하여 평범한 피보나치 함수를 사용했다. #define _CRT_SECURE_NO_WARNINGS #include #include int zero[40]; int one[40]; int fibonacci(int n, int i) { if (n == 0) { zero[i]++; return 0; }..

[알고리즘] DP 동적계획법 ✅ 동적계획법(DP) 1. 동적계획법이란? - 하나의 큰 문제를 여러 개의 작은 문제로 분할하여 푸는 방법 - 이미 계산된 작은 문제의 결과 값을 별도의 메모리 영역에 저장해두고 활용함. - 메모리를 적절하게 사용하여 수행시간 효율성을 비약적으로 향상시킬 수 있음. 답을 재활용하는 것! "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘 2. 동적계획법 사용 조건 1) 큰 문제를 작은 문제로 나눌 수 있음. 2) 작은 문제에서 구한 값이 그것을 포함하는 큰 문제에서도 동일한 값으로 사용됨 (피보나치 수열) ✅ 분할정복법 VS 동적계획법 공통점 큰 문제를 쪼개서 가장 작은 단위로 분할한다. 차이점 - 분할정복법 : 부분 문제는 서로 중복되지..

[C / C++] 백준 10989번 - 수 정렬하기 3 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net ✅ 문제 설명 숫자 N을 입력한 후 N개의 숫자를 입력하면, N개의 숫자를 오름차순으로 출력하는 문제이다. ✅ 알고리즘 설명 1. C++ STL sort() 처음에는 간단하게 C++ STL 을 사용하여 정렬을 했다. #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int main() { ios_base::sync_with_..

[C / C++] 백준 1929번 - 소수 구하기 / 에라토스테네스의 체 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net ✅ 문제 설명 정수 M과 N을 입력하면, M ~ N 사이의 소수를 출력하는 문제이다. ✅ 알고리즘 설명 처음에는 단순하게 생각하여, M ~ N을 차례로 하나씩 나눠지는 수가 있는지 검사하여 출력하는 방식을 사용했다. 그러나 이 방법을 사용하면 시간복잡도가 O(N^2)으로 시간초과가 나게 된다. 따라서 이 문제에서는 '에라토스테네스의 체' 방식을 사용했다. 💡 에라토스테네스의 체 (Sieve of Eratosthenes) 💡 소수..

[C / C++] 백준 11653번 - 소인수분해 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net ✅ 문제 설명 정수 N을 입력하면, N의 소인수분해 결과를 작은 수부터 차례로 출력하는 문제이다. ✅ 알고리즘 설명 소인수분해의 결과를 작은 수부터 차례로 출력해야 하기 때문에 가장 작은 수인 2부터 시작하여, 나눠지지 않을 경우 1씩 더하여 N의 소인수를 찾도록 했다. ✅ 코드_C++

[C / C++] 백준 2562번 - 최댓값 백준 2562번 : https://www.acmicpc.net/problem/2562 2562번: 최댓값 9개의 서로 다른 자연수가 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 번째 수인지를 구하는 프로그램을 작성하시오. 예를 들어, 서로 다른 9개의 자연수 3, 29, 38, 12, 57, 74, 40, 85, 61 이 주어 www.acmicpc.net ✅ 문제 설명 총 9개의 숫자를 입력하여 그 중 최댓값을 찾고, 최댓값이 몇 번째 수인지 구하는 문제이다. ✅ 알고리즘 설명 🛠 C의 경우 간단하게 입력할 때마다 max 값과 비교하여 가장 큰 수를 찾았고, 가장 큰 수일 경우 인덱스 값까지 저장하도록 했다. 🛠 C++의 경우 *max_element / max_element 함수 사용! 1. 가장..

[C / C++] 백준 1244번 - 스위치 켜고 끄기 백준 1748번 : https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net ✅ 문제 설명 먼저 스위치 개수 N을 입력하고, 스위치 N개의 상태를 입력한다. (상태 1 - 켜짐 / 0 - 꺼짐) 그 후 뽑을 학생의 수 M을 입력하고, 학생의 성별과 지정 숫자를 하나씩 입력한다. (1 - 남자 / 2 - 여자) 🌈 남학생의 스위치 변경방법 지정 숫자의 배수가 되는 숫자의 스위치를 변경한다. ex) 지정숫자 = 3 ⏩ (3, 6, 9 ... < N) ..

이전 1 2 3 다음

티스토리툴바