본문 바로가기

알고리즘

알고리즘/BOJ 2020. 3. 7. [C++] 백준 1463번 - 1로 만들기 0. 문제 1. 아이디어 1) 정수 N의 연산 횟수의 최솟값은 이전 값(N/2 or N/3 or N-1 중 최솟값)의 연산횟수에 +1한 값이 된다. 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include #include #include int main() { std::vector v; int N; std::cin >> N; v.resize(N + 1, -1); v[0] = v[1] = 0; for (int i = 2; i
알고리즘/써먹기 좋은 알고리즘 2020. 3. 6. next_permutation을 이용한 조합의 개수 구하기 #include #include #include using namespace std; int main() { vector v; int n, k; cin >> n >> k; for (int i = 0; i < n; i++) v.push_back(i + 1); vector ind; //0과 1을 저장할 배열 벡터 생성 for (int i = 0; i < k; i++) ind.push_back(1); // k개의 1을 추가 for (int i = 0; i < v.size() - k; i++) ind.push_back(0); // n-k개의 0을 추가 sort(ind.begin(), ind.end()); do { for (int i = 0; i < ind.size(); i++) { if (ind[i] == 1)..
알고리즘/BOJ 2020. 3. 6. [C++] 백준 1182번 - 부분수열의 합 0. 문제 1. 아이디어 1) 부분수열의 원소의 개수가 1개부터 N개까지의 케이스들을 나눠서 계산한다. 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include #include #include int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); int N, S,result=0; std::cin >> N >> S; std::vector v; // 수열의 원소가 들어갈 벡터 for (int i = 0; i > input; v.push_back(input); } for (int i = 1; i
알고리즘/BOJ 2020. 3. 5. [C++] 백준 1018번 - 체스판 다시 칠하기 0. 문제 1. 아이디어 1) N*M으로 주어진 체스판에서 8*8 크기의 체스판으로 잘라내려면 chess[0][0]부터 chess[N-6][M-6]의 범위만 검사하면 된다. (나머지는 범위가 겹침) 2) 가장 왼쪽 모서리에 있는 문자(시작하는 문자)가 'B'와 'W'일 경우를 나눠서 생각한다. 3) 시작하는 문자 또한 고정되는 값이 아니라 바뀔 수도 있으니 해당 경우의 수도 고려해서 최솟값을 리턴한다. 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 5..
알고리즘/BOJ 2020. 3. 4. [C++] 백준 2503번 - 숫자야구 0. 문제 1. 아이디어 1) 123부터 987까지의 모든 수들 중에서, 주어진 N개의 질문에 대해 같은 결과를 가지는 수를 카운트한다. 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include #include #include struct entry { std::string num; int strike; int ball; }; int main() { int N; std::cin >> N; std::vector entryV; for (int i = 0; i > input.num >> input.strike >>..
알고리즘/BOJ 2020. 3. 1. [C++] 백준 10448번 - 유레카 이론 0. 문제 1. 아이디어 1) 1000이하의 삼각수들만 들어있는 배열을 따로 하나 생성. 2) 완전 탐색을 통해 주어진 수가 3개의 삼각수들의 합으로 표현될 수 있는지 판단. 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include #include int tri[1000]; bool triangleSum(int total) { for (int p = 0; tri[p] != 0; p++) { for (int q = 0; tri[q] != 0; q++) { for (int r = 0; tri[r] != 0; r++) { int sum = tri..
알고리즘/BOJ 2020. 3. 1. [C++] 백준 3085번 - 사탕 게임 0. 문제 1. 아이디어 1) 2차원 배열을 직접 구현할 수도 있지만 string이 1차원 배열처럼 다룰 수 있다는 사실을 이용한다. 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 #include #include const int MAX = 50; int N; std::string board[MAX]; int ReadBoard() // 보드내에서 먹을 수 있는 사탕의 최대 개수 구하기 { int result = 1; for (int i..
알고리즘/BOJ 2020. 2. 29. [C++] 백준 2231번 - 분해합 0. 문제 1. 아이디어 1) 각 자릿수를 사용해 계산을 하기 위해 '%' 연산을 통해 한 자리씩 올라간다. 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include int main() { int N; std::cin >> N; for (int i = 1; i 0; d /= 10) { s += d % 10; } if (s + i == N) { std::cout

티스토리툴바