⭐ 코딩테스트/백준
[백준 2447번 C/C++] 별 찍기
[백준 2447번 C/C++] 별 찍기
2023.07.21[백준 2447번 C/C++] 별 찍기 해결전략 재귀 Recursion 코드 #include using namespace std; void Star(int y, int x, int num) { if ((y / num) % 3 == 1 && (x / num) % 3 == 1) cout n; for (int y = 0; y < n; y++) { for (int x = 0; x < n; x++) { Star(y, x, n); } cout
[백준 18405번 C/C++] 경쟁적 전염
[백준 18405번 C/C++] 경쟁적 전염
2023.07.19[백준 18405번 C/C++] 경쟁적 전염 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 해결전략 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색 (BFS) 코드 #include #include #include #include using namespace std; int n, k, s, row, column; vector v; int dirY[4] = { -1, 0, 1, 0 }; int dirX[4] = ..
[백준 1541번 C/C++] 잃어버린 괄호
[백준 1541번 C/C++] 잃어버린 괄호
2023.07.17[백준 1541번 C/C++] 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 해결전략 Greedy Algorithm 그리디 알고리즘 (탐욕 알고리즘) 코드 #include #include #include using namespace std; int main() { string input; cin >> input; int num = 0; bool minusFlag = false; int result = 0; for (char..
[백준 11053번 C/C++] 가장 긴 증가하는 부분 수열
[백준 11053번 C/C++] 가장 긴 증가하는 부분 수열
2023.07.14[백준 11053번 C/C++] 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 해결전략 최대 증가길이 수열 Longest Increasing Subsequence, LIS Dynamic Programming (DP) 다이나믹 프로그래밍 코드 #include #include using namespace std; int main() { io..
[백준 16139번 C/C++] 인간-컴퓨터 상호작용
[백준 16139번 C/C++] 인간-컴퓨터 상호작용
2023.07.14[백준 16139번 C/C++] 인간-컴퓨터 상호작용 https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 해결방안 누적 합 주의할 점 중간에 들어오는 문자가 달라질 수도 있다. 코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); string ..
[백준 2110번 C/C++] 공유기 설치
[백준 2110번 C/C++] 공유기 설치
2023.07.12[백준 2110번 C/C++] 공유기 설치 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 해결방안 이분 탐색 매개 변수 탐색 코드 #include #include #include using namespace std; int n, c; vector v; bool isValid(int distance) { int cnt = 1; int lastInstalled = v[0]; for (int i ..
[백준 1927번 C/C++] 최소 힙
[백준 1927번 C/C++] 최소 힙
2023.07.11[백준 1927번 C/C++] 최소 힙 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 해결방안 풀이 방법은 여러가지다. 이번의 경우, priority_queue를 사용하였다. priority_queue의 기본은 내림차순이다. 즉, 큰 수가 가장 위(앞쪽)에 있다. priority_queue 정렬 방법 오름차순 priority_queue pQ1; 내림차순 priority_queue pQ2; priority_queue의 기본형..
[백준 14500번 C/C++] 테트로미노
[백준 14500번 C/C++] 테트로미노
2023.07.10[백준 14500번 C/C++] 테트로미노 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 해결방안 Brute Force (브루트 포스) 구현 코드 #include #include #include #include using namespace std; int n, m; vector v; int sum1, sum2, sum3, sum4, sum5, sum6, sum7, sum8, sum9, sum10; int maxValue1, maxValue2,..
[백준 20920번 C/C++] 영단어 암기는 괴로워
[백준 20920번 C/C++] 영단어 암기는 괴로워
2023.07.09[백준 20920번 C/C++] 영단어 암기는 괴로워 https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 해결전략 map을 사용하여 중복하여 같은 문자가 들어가면 int값을 늘리는 방식으로 몇 번 들어가느지 체크한다. 문자열의 길이는 length()를 사용하여 체크한다. if (myMap.find(input) != myMap.end()) 로 입력값이 있는지 체크한다. 코드 #inc..
[백준 2108번 C/C++] 통계학
[백준 2108번 C/C++] 통계학
2023.07.08[백준 2108번 C/C++] 통계학 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 해결전략 코드 #include #include #include #include #include using namespace std; bool Comp(const pair& a, const pair& b) { if (a.second == b.second) return a.first b.second; } int mai..
[백준 1916번 C/C++] 최소비용 구하기
[백준 1916번 C/C++] 최소비용 구하기
2023.07.07백준 1916번 C/C++] 최소비용 구하기 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 해결전략 Dijkstra Algorithm (다익스트라 알고리즘) 코드 #include #include #include #include using namespace std; int n, m, result; int ch[1001]; struct Edge { int e; int cost; Edge(int a, int b) ..
[백준 2156번 C/C++] 포도주 시식
[백준 2156번 C/C++] 포도주 시식
2023.07.06[백준 2156번 C/C++] 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 해결전략 Dynamic Programming (DP) 동적 계획법 코드 - 방법1 #include #include #include using namespace std; int n; vector v; vector dp; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >..