⭐ 코딩테스트/백준
[백준 1339번 C/C++] 단어 수학
[백준 1339번 C/C++] 단어 수학
2023.11.27[백준 1339번 C/C++] 단어 수학 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 해결전략 탐욕법 Greedy Algorithm 그리디 알고리즘 각 알파벳 [ 예제 ] 2 GCF ACDEB G=100 C=10 F=1 -> GCF = 100G + 10C + 1F A =10000 C=1000 D=100 E=10 B=1 -> ACDEB = 10000A + 1000C + 100D + 10E + 1B A = 10000 * 9 C = 1010..
[백준 10830번 C/C++] 행렬 제곱
[백준 10830번 C/C++] 행렬 제곱
2023.11.26[백준 10830번 C/C++] 행렬 제곱 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 해결전략 분할 정복 long long mod_pow(long long base, long long exponent, long long mod) base^exponent를 mod로 나눈 나머지를 반환한다. 지수가 0인 경우: base^0 = 1 다. 따라서 1을 반환한다. 지수가 홀수인 경우: base^(2 * k + 1) = (base^k) * (base^k) * ba..
[백준 1715번 C/C++] 카드 정렬하기
[백준 1715번 C/C++] 카드 정렬하기
2023.11.20[백준 1715번 C/C++] 카드 정렬하기 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 해결전략 탐욕법, Greedy 그리디 알고리즘 priority_queue pQ; priority_queue는 기본적으로 내림차순 정렬(큰 수부터 차례대로 나오는 정렬)이다. priority_queue 선언을 하면 오름차순 정렬(작은 수부터 차례대로 나오는 정렬)로 바꿀 수 있다. 코드 #include #include #include #in..
[백준 14502번 C/C++] 연구소
[백준 14502번 C/C++] 연구소
2023.11.19[백준 14502번 C/C++] 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 해결전략 구현, 브루트 포스 Brute Force 너비우선탐색 BFS 코드 #include #include #include using namespace std; int dirY[4] = { -1, 0, 1, 0 }; int dirX[4] = { 0, -1, 0, 1 }; int n, m; // n: 세로 길이, m: 가로 길이 int safe; // 안전 영역의 최대 크..
[백준 15683번 C/C++] 감시
[백준 15683번 C/C++] 감시
2023.11.18[백준 15683번 C/C++] 감시 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 해결전략 백트랙킹, Backtracking 코드 #include #include #include using namespace std; // 우, 상, 좌, 하 int dirY[4] = { 0, -1, 0, 1 }; int dirX[4] = { 1, 0, -1, 0 }; int n, m; int answer = 2147000000; vector v, ..
[백준 15686번 C/C++] 치킨 배달
[백준 15686번 C/C++] 치킨 배달
2023.11.16[백준 15686번 C/C++] 치킨 배달 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 해결전략 백트래킹, Backtracking 정답 코드 #include #include #include using namespace std; int n, m; // n: 도시 크기, m: 선택할 치킨집의 개수 int answer = 2147000000; // 최소 치킨 거리를 저장할 변수 vector v; vector house, ch..
[백준 16953번 C/C++] A → B
[백준 16953번 C/C++] A → B
2023.11.14[백준 16953번 C/C++] A → B https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A > a >> b; bool success = false; while(b > 0) { if (b == a) { success = true; break; } int temp = b; if (b % 2 == 0){ b /..
[백준 7576번 C/C++] 토마토
[백준 7576번 C/C++] 토마토
2023.11.06[백준 7576번 C/C++] 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 해결방안 너비우선탐색, BFS 코드 #include #include #include using namespace std; int m, n; // m: 가로(열) 크기, n: 세로(행) 크기 vector v, day; // v: 각 위치의 토마토 상태, day: 각 위치에서 토마토가 익는 데 걸리는 날짜를 저장 int totalDays; // 토..
[백준 1806번 C/C++] 부분합
[백준 1806번 C/C++] 부분합
2023.10.31[백준 1806번 C/C++] 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N > n ..
[백준 2470번 C/C++] 두 용액
[백준 2470번 C/C++] 두 용액
2023.10.30[백준 2470번 C/C++] 두 용액 https://www.acmicpc.net/problem/2470 해결방안 투 포인터 처음 시도한 코드 #include #include #include using namespace std; struct Solution { int first, second, ave; Solution(int a, int b, int c) { first = a; second = b; ave = c; } bool operator> n; v.resize(n); for(int i=0; i> v[i]; } sort(v.begin(), v.end()); int left = 0; int right = n - 1; while (left < right) { int sumSol = v[left] + v[..
[백준 3273번 C/C++] 두 수의 합
[백준 3273번 C/C++] 두 수의 합
2023.10.29[백준 3273번 C/C++] 두 수의 합 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 해결방안 투 포인터 알고리즘 코드 #include #include #include using namespace std; int n, x; vector a; int answer; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin..
[백준 11054번 C/C++] 가장 긴 바이토닉 부분 수열
[백준 11054번 C/C++] 가장 긴 바이토닉 부분 수열
2023.10.28[백준 11054번 C/C++] 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 해결전략 가장 긴 증가하는 부분 수열 종류의 문제 코드 #include #include using namespace std; int n; // 수열의 길이 vector v, dpF, dpB; // 입력 받을 수열, 앞에서부터의 가장 긴 증가하는 부분 수열, 뒤에서부터의 가장 긴 감소하는 부분 수열 int main(){ ios::sync_with_stdio(..