⭐ 코딩테스트
[백준 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 >..
[백준 1780번 C/C++] 종이의 개수
[백준 1780번 C/C++] 종이의 개수
2023.07.05[백준 1780번 C/C++] 종이의 개수 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 해결전략 재귀 코드 #include #include #include using namespace std; int n, MinusCnt=0, ZeroCnt=0, OneCnt=0; vector v; bool Check(int y, int x, int size) { int firstValue = v[y][x]; for (int i = y; i < y..
[백준 1992번 C/C++] 쿼드트리
[백준 1992번 C/C++] 쿼드트리
2023.07.04쿼드트리 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 해결전략 재귀 코드 #include #include #include using namespace std; int n; string input; vector v; bool Check(int y, int x, int size) { int firstValue = v[y][x]; for (int i = y; i < y + size; i++) { for (int j = x; j < x..
[백준 14891번 C/C++] 톱니바퀴
[백준 14891번 C/C++] 톱니바퀴
2023.07.03[백준 14891번 C/C++] 톱니바퀴 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 해결방안 구현 #include rotate(v.begin(), v.begin() + 1, v.end()); 왼쪽 회전 rotate(v.begin(), v.end() - 1, v.end()); 오른쪽 회전 코드 #include #include #include #include using namespace std; int k, input, rDir; str..