⭐ 코딩테스트
[백준 12851번 C/C++] 숨바꼭질2
[백준 12851번 C/C++] 숨바꼭질2
2024.01.08[백준 12851번 C/C++] 숨바꼭질2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 해결전략 너비우선탐색 BFS 정답코드 #include #include #include using namespace std; int N, K; // N: 수빈이의 현재 위치, K: 동생이 있는 위치 int minTime = 2147000000, num; // 최소 시간, 방법의 수 vector ch(100001, -1)..
[백준 17144번 C/C++] 미세먼지 안녕!
[백준 17144번 C/C++] 미세먼지 안녕!
2024.01.05[백준 17144번 C/C++] 미세먼지 안녕! https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 해결전략 브루트포스 Brute Force, 구현 정답코드 #include #include using namespace std; int dirY[4] = { -1, 0, 1, 0 }; int dirX[4] = { 0, -1, 0, 1 }; int r, c, t; vector v; int airLocY, airLocX; void Spread(int y..
[백준 2096번 C/C++] 내려가기
[백준 2096번 C/C++] 내려가기
2024.01.04[백준 2096번 C/C++] 내려가기 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 해결전략 동적계획법 Dynamic Programming, DP 슬라이딩 윈도우 알고리즘 Sliding Window Algorithm 처음 시도한 코드 - 메모리 초과 #include #include using namespace std; int n; vector v; vector dp, dpMax; int minValue = 2147000000, maxValue = 0; i..
[백준 15486번 C/C++] 퇴사2
[백준 15486번 C/C++] 퇴사2
2024.01.03[백준 15486번 C/C++] 퇴사2 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 해결전략 동적계획법 Dynamic Programming, DP 처음 시도한 코드 - 시간초과 #include #include using namespace std; int n; int total; vector T, P; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(..
[백준 9935번 C/C++] 문자열 폭발
[백준 9935번 C/C++] 문자열 폭발
2024.01.02[백준 9935번 C/C++] 문자열 폭발 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 해결전략 문자열 처음 시도한 코드 - 메모리 초과 #include #include using namespace std; string input, boom; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> input >> boom; while(true) { ve..
[백준 5639번 C/C++] 이진 검색 트리
[백준 5639번 C/C++] 이진 검색 트리
2023.12.28[백준 5639번 C/C++] 이진 검색 트리 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 해결전략 깊이 우선 탐색 DFS 트리 후위 순회 정답 코드 #include #include using namespace std; vector v; void DFS(int start, int end) { if (start >= end) { return; } if (start == end - 1) { cout
[프로그래머스 C++] 가장 큰 정사각형 찾기
[프로그래머스 C++] 가장 큰 정사각형 찾기
2023.12.27[프로그래머스 C++] 가장 큰 정사각형 찾기 https://school.programmers.co.kr/learn/courses/30/lessons/12905 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 동적계획법 Dynamic Programming, DP 다른 방식으로 풀면 시간초과(효율성 테스트 실패)가 나온다. 정답 코드 #include using namespace std; int solution(vector board){ int row = board.size(); int col = board[0].size(); vector dp(row..
[백준 1967번 C/C++] 트리의 지름
[백준 1967번 C/C++] 트리의 지름
2023.12.26[백준 1967번 C/C++] 트리의 지름 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 해결전략 깊이우선탐색 DFS 정답코드 #include #include using namespace std; struct Node { int next; int cost; }; int n; int maxCost, maxNode; // maxCost: 최대 비용, maxNode: 최대 비용을 가지는 노드 번호 vector v; //vecto..
[백준 15655번 C/C++] N과 M (6)
[백준 15655번 C/C++] N과 M (6)
2023.12.25[백준 15655번 C/C++] N과 M (6) https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 해결전략 백트래킹 Backtracking 정답코드 #include #include #include using namespace std; int n, m; vector v; vector result; int ch[9]; // 선택된 숫자의 사용 여부를 체크하는 배열 void BackT(int idx, int cnt) { if(cnt == m)..
[백준 15654번 C/C++] N과 M (5)
[백준 15654번 C/C++] N과 M (5)
2023.12.24[백준 15654번 C/C++] N과 M (5) https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 해결전략 백트래킹 Backtracking 정답코드 #include #include #include using namespace std; int n, m; vector v; vector result; int ch[9]; // 선택된 숫자의 사용 여부를 체크하는 배열 void BackT(int cnt) { if(cnt == m){ for(int..
[백준 9465번 C/C++] 스티커
[백준 9465번 C/C++] 스티커
2023.12.239465번 C/C++] 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 해결전략 동적구현법, 다이나믹 프로그래밍 Dynamic Programming (DP) 정답 코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { ..
[백준 1799번 C/C++] 비숍
[백준 1799번 C/C++] 비숍
2023.12.22[백준 1799번 C/C++] 비숍 https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 해결전략 백트랙킹 Backtracking 처음 시도한 코드 #include #include #include using namespace std; int n; // 체스판의 크기 n x n vector v; vector place; int answer; // 주어진 체스판 위에 놓을 수 있는 비숍의 최대 개수 bool CheckDiagonals(int y, int x, v..