HyeLog

🌿문제: https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 🌿알고리즘: 브루트포스 - 순열 이 문제를 저번에는 재귀로 풀었었는데, 이번에는 순열로 풀었다. 연산자의 개수가 N-1개로 정해져있고, 그들의 순서를 정하는 문제이기 때문에 순열로 풀 수 있다. 🌿algorithm 헤더의 minmax_element 함수를 사용하면 최대/최소값을 쉽게 구할 수 있다. 🌿코드: #include #incl..

언제 사용? 🌿 브루트포스 중 순열은 [모든 경우의 수를 해봐야 할 때 + 이 때 순서가 중요한 경우]에 사용한다. 시간복잡도? 🌿크기가 N인 수열이 있을 때, 순열의 개수는 N! 개이다. 그리고, 어떤 순열의 다음 순열을 알아내는 연산의 시간복잡도는 O(N) 이다. (Ex. next_permutation 함수의 시간복잡도) 따라서, 모든 순열 찾기 알고리즘의 시간복잡도는 N! * O(N) 이다. 참고: https://intrepidgeeks.com/tutorial/use-of-violence-sequence 🔵 brute force - 순열 사용하기 안녕하세요 :) 오늘은 순열을 사용하는 BF 알고리즘에 대해 알아보겠습니다. 줄서는 방법, 특정 작업 순서의 모든 경우의 수 등, 순서가 중요한 작업에 있..

📍문제: https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 📍알고리즘: 브루트포스 - 순열 (Greedy 또는 브루트포스-재귀로도 풀 수 있음) 📍아이디어: ASCII 코드를 이용해서 char형 배열을 다른 배열의 index로 사용해서 알파벳을 숫자로 치환. 🔭 벡터 중복 제거 방법: 반드시 sort 한 후에 unique 함수를 이용해서 제거. // alphabets 벡터 중복 제거 sort(alphabets.begin(), alphabet..

📍문제: https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 📍알고리즘: 브루트포스 - 순열 (백트래킹(재귀)으로 풀 수 있음. → 속도 향상 가능) 📍아이디어: 부등호에 따른 숫자들의 순서만 정해지면, 실제로 각 숫자들이 어떤 숫자인지는 상관 없이, 그 순서에 맞게 고르면 부등호를 무조건 만족한다. 따라서, 최대수와 최소수를 구하는 문제이므로, 각각 987··· / 123··· 부터 시작해서 부등호의 순서를 정한다. 📍시간복잡도: (k+1)! * O(k) 👉..

📍AWS RDS 의 파라미터 그룹 설정을 아래와 같이 변경한다. 변경한 후에는 반드시 RDS 인스턴스를 재부팅 해야한다. character_set_client = utf8mb4 character_set_connection = utf8mb4 character_set_database = utf8mb4 character_set_filesystem = binary character_set_results = utf8mb4 character_set_server = utf8mb4 skip-character-set-client-handshake = 1 collation_connection = utf8mb4_unicode_ci collation_server = utf8mb4_unicode_ci 🚨RDS 인스턴스에 파라미..

📍문제: https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 📍알고리즘: 백트래킹 (이 문제는 백트래킹으로 풀 수 있는 경우의 수로 주어져서 백트래킹으로 해결 가능) 📍아이디어: N-Queen 문제와 유사하게 bool형 배열 활용 + exit(0) : 프로그램을 성공적으로 종료. (알고리즘 문제에서 원하는 값이 나왔을 경우 바로 종료하기 위해 주로 사용) 📍코드: #include using namespace std; int board[9][9]; ..

📍백트래킹 개념 백트래킹은 브루트포스에 조건을 추가해서 절대 정답이 될리 없는 경우에서는 함수 호출을 중단하는 알고리즘이다. 즉, 브루트함수-재귀 패턴의 '다음 호출' 부분에서 무조건 다음 호출을 하는 브루트포스와 달리, 조건을 검사해서, 만족하면 다음 호출을 하는 방식이다. 📍N-Queen 문제 예시 코드 void calc(int row) { // 성공한 경우 if (row == n) { ans += 1; } // 다음 호출 for(int col=0; col> N; cout

📍문제: https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 📍알고리즘: 브루트포스-재귀 풀이 1 📍아이디어: 브루트포스-재귀함수의 패턴을 생각해보면, 재귀함수의 구조는 쉽게 코드를 짤 수 있었던 문제였다. 구슬 하나를 제거하고 양 옆 에너지를 더하는 것은 isRemoved 배열과 prev, next 변수로 해결했다. '다음 호출'을 한 후에 isRemoved[i]를 다시 false로 바꿔 주어야 dfs가 아닌 브루트포스로 모든 경우를 따질 ..