3584번: 가장 가까운 공통 조상 해결 트리의 노드는 모두 root node를 부모로 한다. 즉, 모든 노드가 연결되어있다. 따라서 각 노드의 부모 노드를 찾다보면 root node에서 만날 것이다. 💡 다르게 말하자면 트리는 내 부모노드와 내가 공통 조상을 가지고 있다. 트리 구조 저장 x, y의 레벨을 찾고 부모 노드를 저장하는 방법은 union-find 알고리즘에서 root Parent를 찾는 방법에서 아이디어를 떠올려 풀었다. union-find 알고리즘의 disjoint set에서 서로 다른 두 노드가 연결되었는지 알기 위해, Parent 배열이 존재하고, 두 노드가 연결될 경우 두 노드의 부모를 같게 한다. getParent라는 재귀함수를 통해 두 노드의 부모가 같다면 연결되었다고 판단한다...

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net q.pop()을 빼먹어서 queue 길이가 자꾸만 증가하는 이유를 찾으려 디버깅을 계속했다... ㅠㅠ 76%에서 틀렸었는데, 아무 칸도 물에 잠기지 않을 수 있다는 조건을 빼먹었기 때문이다. 유사 문제 떨어진 영역(뭉탱이)의 개수를 구하는 방법을 모르겠다면 아래 문제와 해답을 참고하면 도움될 것이다. 2021.09.26 - [PS/백준] - 백준 4963번 (C++) 섬의 개수 백준 4963번 (C++)..

https://www.acmicpc.net/problem/23559 23559번: 밥 제주대 학생회관 식당에는 두 개의 메뉴가 있다. 코너 A로 가면 5,000원짜리 메뉴를 먹을 수 있고, 코너 B로 가면 1,000원짜리 메뉴를 먹을 수 있다. 준원이는 대면 수업이 시작되는 바람에 이제 남 www.acmicpc.net 틀린 코드 #include #include #include #include using namespace std; int n, x; vector v; bool cmp(pair p1, pair p2) { double a = (double)(p1.first) / (double)(p1.second); double b = (double)(p2.first) / (double)(p2.second); i..

아이디어 처음엔 삼각형의 위에서부터 1층, ..., k층, ..., n층으로 생각하고 k층까지의 최적의 경로가 n층까지의 최적의 경로에 포함될 것이라 생각할 수도 있다. 그러나 예시로 주어진 테스트케이스가 그 반례이다. 따라서 최적의 경로는, 2차원배열의 각 인덱스에 해당하는 dp[i][j]에 저장되어있다. 그러므로 dp[i][j]에 도달하는 optimal한 경로와 dp[i][j+1]에 도달하는 경로가 다를 것이다. dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + arr[i][j]; 를 사용하여 해결하면 된다. 다시 말하자면, k층까지 탐색했을 때 합이 최대가 되는 것이 최적의 경로가 아니라, k층의 l열을 오는 데에 합이 최대가 되는 경로가 최적의 경로(dp의 점화식)을 구..

완전탐색으로 해결했다. https://www.acmicpc.net/problem/8892 8892번: 팰린드롬 팰린드롬은 어느 방향으로 읽어도 항상 같은 방법으로 읽을 수 있는 단어이다. 예를 들어, civic, radar, rotor, madam은 팰린드롬이다. 상근이는 단어 k개 적혀있는 공책을 발견했다. 공책의 단어는 ICPC www.acmicpc.net #include #include #include #include #include using namespace std; const int MAX = 1001; int t; vector v; int palindrome() { for (int i = 0; i < v.size() - 1; i++) { for (int j = i + 1; j < v.size..

아이디어 아스키 코드 차트표를 참고하면 대문자와 소문자가 십진수로 32가 차이나는 것을 알 수 있다. 따라서 소문자 a를 기준으로(97) 대소문자를 구분해서 대문자라면 32를 더하여 char로 출력하고, 소문자라면 32을 뺀다. 코드 #include #include using namespace std; using ll = long long; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); string s; cin >> s; for (int i = 0; i < s.size(); i++) { if (s[i] < 97) { cout

아이디어 1. input 2차원 배열을 예제의 모양대로 처럼 표현하기 위해서 그대로 넣을 수 없고 for (int i = y1; i < y2; i++) { for (int j = x1; j < x2; j++) { arr[m-i-1][j] = 1; } } 를 거쳐야 한다. 2. dfs dfs를 진행하면서, 인접한 행렬은 visit되었다고 체크해주고, main함수에서 이차원 배열이 visit되었는지 세면서 섬처럼 인접한 부분을 cnt해주면 분리된 영역의 개수를 알 수 있다. 여기서 각 분리된 영역의 넓이를 알기 위해 visit되지 않은 칸에 (값은 0) dfs함수가 재귀적으로 호출될 때마다 영역의 넓이를 더해줬다. 그리고 매 영역마다 넓이를 0으로 다시 초기화한다. 코드 #include #include #i..

수의 규칙을 보고 떠오르는 점화식을 적었다. dp[MAX] 배열에 저장했다. 자료형이 long long이 되어야 함에 유의하자. #include using namespace std; using ll = long long; const int MAX = 105; int n,t; ll dp[MAX]; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); dp[1] = 1; dp[2] = 1; dp[3] = 1; for (int i = 4; i > t; while (t--) { int n; cin >> n; cout

기본적인 구현 문제였다. 이런 문제는 c++의 stl인 queue를 사용해도 되지만, 자료구조 학습 기간이 길지 않은 초보자라면 직접 구현해보길 권장한다. front 와 back을 증가시키기만 하는 linear queue를 구현해도 주어진 input이 배열의 범위를 넘어가지 않아서 circular queue가 필요하지 않은 것 같다. circular queue는 modulo를 사용하면 된다. https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmic..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 아이디어 위상정렬. 근데 약간의 다이나믹 프로그래밍을 곁들인... 위상정렬을 아는 사람이라면, 문제를 보고 위상 정렬 진행해서 같은 노드로부터 출발하면 큰 값의 delay(d[i]) 를 더하면 되겠구나, 하고 생각했을 것이다. 현재 노드를 cur, cur의 다음 노드를 nxt라고 했을때 result[nxt] 는 result[cur] + d[nxt] 중 최댓값이다. 틀렸습니다 를 받았다면? 1..