⭐ 코딩테스트/백준
[백준 14725번 C/C++] 개미굴
[백준 14725번 C/C++] 개미굴
2024.02.04[백준 14725번 C/C++] 개미굴 https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다. 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정 www.acmicpc.net 해결전략 Tree 트리 Trie 트라이 자료구조 정답 코드 #include #include #include #include using namespace std; int n; // 먹이의 정보 개수 int k; // 먹이 사슬의 길이 struct Node{ // 노드를 표현하는 구조체 private: map child; // 자식 노드를 가리..
[백준 16946번 C/C++] 벽 부수고 이동하기 4
[백준 16946번 C/C++] 벽 부수고 이동하기 4
2024.01.31[백준 16946번 C/C++] 벽 부수고 이동하기 4 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 해결전략 너비우선탐색 BFS 풀이전략 0 위치 한 곳에서 BFS를 실행한다. 인접한 0을 모두 방문하고 카운팅(cnt)하고 방문체크한다. // 빈 공간이고 방문하지 않았다면 if (v[ny][nx] == 0 && ch[ny][nx] == 0) { Q.push({ ny, nx }); ch[ny][nx] = 1; cnt++;..
[백준 17387번 C/C++] 선분 교차 2
[백준 17387번 C/C++] 선분 교차 2
2024.01.30[백준 17387번 C/C++] 선분 교차 2 https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 해결전략 수학 기하학 선분 교차 판정 외적 Cross 행렬식 외적를 구할 때 사용하는 행렬식 int CCW(const Point& a, const Point& b, const Point& c) { // 행렬식을 사용해서 외적 구하기 long long result = (a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x); if (res..
[백준 1025번 C/C++] 제곱수 찾기
[백준 1025번 C/C++] 제곱수 찾기
2024.01.30[백준 1025번 C/C++] 제곱수 찾기 해결전략 정답 코드 #include #include #include #include using namespace std; int n, m; int answer = -1; bool flag = false; int arr[10][10]; bool isSqureNum(int n) { int root = (int)sqrt(n); if (root * root == n) return true; return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; string tmp = ""; for (int i = 1; i > tmp; for (int j = 1; j
[백준 17404번 C/C++] RGB거리 2
[백준 17404번 C/C++] RGB거리 2
2024.01.26[백준 17404번 C/C++] RGB거리 2 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 해결전략 동적계획법 Dynamic Programming (DP) 첫 번째 집을 각각 빨강, 초록, 파랑으로 칠하는 세 가지 경우를 각각 계산한다. 첫 번째 집을 특정 색으로 칠한 경우, 그 색을 제외한 다른 두 색의 비용은 계산할 수 없으므로 무한대(INF)로 설정한다. dp[1][0] = v[1].red; dp[1][1]..
[백준 15824번 C/C++] 너 봄에는 캡사이신이 맛있단다
[백준 15824번 C/C++] 너 봄에는 캡사이신이 맛있단다
2024.01.25[백준 15824번 C/C++] 너 봄에는 캡사이신이 맛있단다 https://www.acmicpc.net/problem/15824 15824번: 너 봄에는 캡사이신이 맛있단다 한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 해결전략 수학 정렬 조합론 분할 정복을 이용한 거듭제곱 정답코드 #include #include #include using namespace std; int n; // 메뉴의 총 개수 vector v; vector two; const int MOD = 1000000007; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; v.r..
[백준 1019번 C/C++] 책 페이지
[백준 1019번 C/C++] 책 페이지
2024.01.24[백준 1019번 C/C++] 책 페이지 https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 해결전략 수학 일단 이번 문제는 답지를 봤다. 풀이를 생각해내기 힘들었다. 문제 풀이 방향은 start 숫자부터 end 숫자까지 등장한 0~9 숫자를 카운팅 하는 것이다. 정답코드 #include using namespace std; long long digit[10]; // 0부터 9까지 각 자릿수가 등장하는 횟수를 저장 // 주어진 숫자 n에서 각 자릿수가 얼마나 많이 등장하는지 계산하는 함수 void Cal(long ..
[백준 10942번 C/C++] 팰린드롬?
[백준 10942번 C/C++] 팰린드롬?
2024.01.23[백준 10942번 C/C++] 팰린드롬? https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 해결전략 동적계획법 Dynamic Programming (DP) 메모이제이션 Memoization 시도한 코드 - 시간초과 처음 시도한 코드 #include #include using namespace std; int n, m; vector v; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; v.resiz..
[백준 9466번 C/C++] 텀 프로젝트
[백준 9466번 C/C++] 텀 프로젝트
2024.01.22[백준 9466번 C/C++] 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 해결전략 깊이우선탐색 DFS 정답코드 #include #include using namespace std; int T; // 테스트 케이스의 수 int n; // 노드의 수 vector v; // 각 노드에서 다른 노드로의 링크를 저장하는 벡터 vector visited; // 각 노드의 방문 여부를 저장하는 벡터 vector done; // 각 노드가 처리되..
[백준 9252번 C/C++] LCS 2
[백준 9252번 C/C++] LCS 2
2024.01.20[백준 9252번 C/C++] LCS 2 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 해결전략 LCS Longest 다이나믹 프로그래밍 Dynamic Programming 슬라이딩 윈도우 알고리즘 Sliding Window Algorithm 처음 시도한 코드 - 시간초과 #include #include using namespace std; string a, b; string answer; in..
[백준 2166번 C/C++] 다각형의 면적
[백준 2166번 C/C++] 다각형의 면적
2024.01.19[백준 2166번 C/C++] 다각형의 면적 https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 해결전략 기하학. 다각형의 넓이 실수한 부분 - 주어진 점들의 순서를 조작하면 안 된다 #include #include #include #include // 소수점 자리 설정을 위한 헤더. setprecision() 사용가능 using namespace std; struct Coor{ double x; double y; }; bool Compare(Coor& a, Coor& b)..
[백준 2252번 C/C++] 줄 세우기
[백준 2252번 C/C++] 줄 세우기
2024.01.18[백준 2252번 C/C++] 줄 세우기 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 해결 전략 위상 정렬 Topological Sort Algorithm 정답 코드 #include #include #include using namespace std; int n, m; // n은 학생의 수, m은 키를 비교한 횟수 vector graph; // 각 학생의 키를 비교한 결과를 나타내는 그래프 vect..