stepBYstep

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 난이도 유니온파인드 / ⭐️⭐️⭐️ 문제풀이 유니온 파인드 문제이다. 하지만 유니온파인드로 풀었으나 계속 시간 초과가 났다. 유니온 파인드란, 한마디로 특정 원소가 어떤 유니온(집합)에 포함되어있는지 찾는 알고리즘이다. 서로소집합(disjoint-set) 이라고도 한다. 특정 원소가 여러 집합에 포함되지 않고 하나의 집합에만 포함되기 때문이다. 최적화를 위..

https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net #include #include #include using namespace std; void find_parent(int arr[], int n, vector &v) { if (arr[n] == n) { return; } else { v.push_back(arr[n]); find_parent(arr, arr[n], v); } } int main..

https://www.acmicpc.net/problem/11005 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 난이도 기본구현 / 난이도 ⭐️ 문제 풀이 n을 k진법으로 변환하기 위한 코드를 정리하기 위해 풀어봤다. #include #include #include using namespace std; int main() { int n, b; scanf("%d %d", &n, &b); int rest; string result = ""; while (n > 0) { rest = n % b; n = n ..

https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net #include #include #include #include #include #include using namespace std; void my_print(int arr[][22], int n) { printf("\n"); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { printf("%02d ", arr[i][j]); } prin..

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 난이도 단순구현 / 난이도 ⭐️ / 1시간 문제 풀이 단순 구현문제이다. 시간을 고민했었는데 20 * 20 * 20 = 8000 이라서 고민없이 구현했다. (n이 최대 20) #include #include #include #include using namespace std; int arr[450][5] = {0}; int seat[22][22] = {0}; int n; int dirx..

https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 난이도 단순구현 / 난이도 ⭐️⭐️⭐️ / 2.5시간 문제 풀이 단순 구현 문제이다. 구슬 이동을 어떻게 구현할 것인지가 가장 중요한 포인트이다. 나는 구슬 순서를 담은 일차원 벡터와, 일차원 벡터에 접근하기 위한 인덱스를 값으로 가지는 2차원 배열로 구현했다. 예를 들어 아래 조건일 경우 다음과 같은 자료형을 추가한 것이다. 구슬의 순서를 담은 일차원 벡터 : 0(상어), 1,..

https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 난이도 단순구현 / 난이도 ⭐️⭐️ / 1.5시간 / 실수할 수 있는 부분 있음 문제 풀이 (문제 일부) 모든 구름이 di 방향으로 si칸 이동한다. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다. 구름이 모두 사라진다. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있..