⭐ 코딩테스트
[프로그래머스 C++] 숫자 카드 나누기
[프로그래머스 C++] 숫자 카드 나누기
2023.12.21[프로그래머스 C++] 숫자 카드 나누기 https://school.programmers.co.kr/learn/courses/30/lessons/135807 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 최대 공약수 GCD 수학, 구현 정답코드 #include #include #include using namespace std; // 유클리드 호제법을 사용하여 GCD를 찾음 int gcd(int a, int b){ if (b == 0) return a; return gcd(b, a % b); } int solution(vector arrA, ve..
[백준 13549번 C/C++] 숨박꼭질 3
[백준 13549번 C/C++] 숨박꼭질 3
2023.12.20[백준 13549번 C/C++] 숨박꼭질 3 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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는 목표 위치 vector dist(100001, 2147000000); // dist 벡터는 각 위치에 도달하는 데 필요한 최소 시간을 저장 int..
[백준 11725번 C/C++] 트리의 부모 찾기
[백준 11725번 C/C++] 트리의 부모 찾기
2023.12.19[백준 11725번 C/C++] 트리의 부모 찾기 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 해결전략 트리 Tree 너비우선탐색 BFS vector v[ ] v[1] 6, 4 v[2] 4 v[3] 6, 5 v[4] 1, 2, 7 v[5] 3 v[6] 1, 3 v[7] 7 Q 1 6 4 3 2 7 ... 정답 코드 #include #include #include using namespace std; int n; vector v(100001); // 각 노드의 연결정보를 저장할 2차원 벡터 // vecto..
[백준 15650번 C/C++] N과 M(2)
[백준 15650번 C/C++] N과 M(2)
2023.12.18[백준 15650번 C/C++] N과 M(2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 해결전략 조합 Combination, 백트랙킹 Backtracking 정답 코드 #include #include using namespace std; int n, m; int arr[9], ch[9]; // arr는 선택된 수를 저장하는 배열, ch는 해당 수가 선택되었는지를 확인하는 체크 배열 void DFS(int idx, int cnt) // ..
[백준 9251번 C/C++] LCS (Longest Common Subsequence, 최장 공통 부분 수열)
[백준 9251번 C/C++] LCS (Longest Common Subsequence, 최장 공통 부분 수열)
2023.12.15[백준 9251번 C/C++] LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 해결방안 다이나믹 프로그래밍 Dynamic Programming, DP LCS (Longest Common Subsequence, 최장 공통 부분 수열) 정답 코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(fal..
[백준 1238번 C/C++] 파티
[백준 1238번 C/C++] 파티
2023.12.14[백준 1238번 C/C++] 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 해결전략 Dijkskra 다익스트라 정답 코드 #include #include #include using namespace std; int n, m, x; // n: 마을의 수(각각의 마을에 1명의 학생이 거주), m: 단방향 도로 수, x: 파티가 벌어지는 마을 vector v(1001); // 각 마을 간의 도로 정보를 저장하는..
[백준 1043번 C/C++] 거짓말
[백준 1043번 C/C++] 거짓말
2023.12.13[백준 1043번 C/C++] 거짓말 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 해결전략 Set 처음 시도한 코드 - 테스트 케이스 모두 통과 #include #include #include using namespace std; int n, m; // n: 사람의 수, m: 파티의 수 int k; // k: 진실을 아는 사람의 수 set truth; // 진실을 아는 사람들을 담는 배열 int nVisiters; // nVisiters: 파티에 오는..
[백준 7662번 C/C++] 이중 우선순위 큐
[백준 7662번 C/C++] 이중 우선순위 큐
2023.12.12[백준 7662번 C/C++] 이중 우선순위 큐 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 해결방안 우선순위 큐 priority_queue set 처음 시도한 코드 #include #include using namespace std; int t, k; priority_queue pQ1; priority_queue pQ2; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)..
[백준 7569번 C/C++] 토마토
[백준 7569번 C/C++] 토마토
2023.12.11[백준 7569번 C/C++] 토마토 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 해결전략 너비 우선 탐색 BFS 정답 코드 #include #include #include using namespace std; int dirY[4] = { -1, 0, 1, 0 }; int dirX[4] = { 0, -1, 0, 1 }; struct Coor { int ht, y, x; }; int m, n, h; vector v; /..
[백준 25682번 C/C++] 체스판 다시 칠하기 2
[백준 25682번 C/C++] 체스판 다시 칠하기 2
2023.12.09[백준 25682번 C/C++] 체스판 다시 칠하기 2 https://www.acmicpc.net/problem/25682 25682번: 체스판 다시 칠하기 2 첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 해결전략 누적합, 동적 프로그래밍 Dynamic Programming DP 체스판 위에 k x k 크기의 정사각형을 놓았을 때, 정사각형 내의 체스판 칸 색깔을 바꿔서 모두 같은 색으로 만드는 데 필요한 최소 변경 횟수를 찾는다. 처음 시도한 코드 - 98%에서 실패 #include #include #include using namespace std; int n, m, k; vect..
[프로그래머스 C++] 시소 짝꿍
[프로그래머스 C++] 시소 짝꿍
2023.12.08[프로그래머스 C++] 시소 짝꿍 https://school.programmers.co.kr/learn/courses/30/lessons/152996 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 조합(Combination)과 해시맵(Hash Map) '조합'이란 n개의 원소 중에서 r개를 순서 없이 선택하는 것을 의미한다. 이 코드에서는 동일한 몸무게를 가진 사람들의 쌍을 찾기 위해 조합을 사용한다. '해시맵'이라는 데이터 구조를 사용했다. 해시맵은 키와 값을 한 쌍으로 저장하는 데이터 구조로, 여기서는 몸무게를 Key로, 그 몸무게를 가진 사..
[백준 1753번 C/C++] 최단경로
[백준 1753번 C/C++] 최단경로
2023.12.07[백준 1753번 C/C++] 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 해결전략 Dijkstra 다익스트라 처음 시도한 코드 - 시간초과 #include #include #include using namespace std; int v, e; // v: 정점의 개수, e: 간선의 개수 int k; // k: 시작 정점 vector graph; struct Edge { int vertex; in..