파게로그

완전이진트리(complete binary tree) 말단 노드를 제외한 모든 노드가 두 개의 자식 노드를 가지고 있는 이진 트리. 힙(heap) 완전이진트리에서, 모든 노드에 대해서 부모 노드의 값이 자식 노드의 값보다 크거나 같으면 Max heap, 작거나 같으면 Min heap이라 한다. heapify(힙 생성) 1. 루트 노드(A)부터 모든 노드를 순회하며, 2. A와 A의 자식 노드를 비교하여, 교환하거나 그대로 둔다. 3. 2를 반복한다. heapify는 하나의 노드에 대해 수행되는 과정을 반복하며, 해당하는 노드를 제외하고는 최대 힙이 구성되어 있는 상태라고 가정한다. 즉, 위에서부터 차례차례 서브 트리를 Max heap으로 만들어나가는 것이다. insert(삽입) 1. 마지막 자리에 추가할 ..

문제 링크: 1436번 영화감독 숌 https://www.acmicpc.net/problem/1436 처음에 cnt를 0으로 시작할지 1로 시작할지 헷갈렸다. 차근차근 생각하자! #include #include #define INF 1000000000 using namespace std; int main(void) { /* input */ int n; cin >> n; int answer; /* increase number */ int cnt = 0; // 6이 연속으로 3번 나오는 수의 개수 string st; int cnt6 = 0; // 숫자 내에서 연속으로 나오는 3의 개수 bool flag; for (int i = 666; i 2) { flag = true; break; } } else { //..

문제 링크: 1018번 체스판 다시 칠하기 https://www.acmicpc.net/problem/1018 체스판과 같은 크기로, 2차원 int 배열을 먼저 다음과 같이 2개 더 만든다. B로 시작하는 체스판, W로 시작하는 체스판에 대해서 각각의 칸에, 다시 칠해야 할 때 1, 다시 칠하지 않아도 될 때 0을 넣는다. 가로 8칸, 세로 8칸을 잘라낼 때 기준은 좌상단 모서리의 좌표로 설정했다. 이 좌표, 즉 board[row][col]의 row, col의 범위는 0

문제 링크: 7568번 덩치 https://www.acmicpc.net/problem/7568 모든 경우를 일일이 탐색하는 문제였는데 조금 빠른 속도를 내보겠다고 잘못된 선택을 했다. 처음에 시도한 방식은 다음과 같다. 에서 x+y를 통해 정렬한 후 위아래로 2개씩 비교하면서 덩치 등수를 크게 하거나, 그대로 두었다. 하지만 다음과 같은 반례가 존재한다. , , , 과 같은 경우에는 정렬 여부에 따라서 덩치 등수가 달라진다. 올바른 풀이는 다음과 같다. #include using namespace std; int main(void) { // declare int n; cin >> n; int *xarr = (int *)(malloc(sizeof(int)*n)); int *yarr = (int *)(mal..

https://learngitbranching.js.org/?locale=ko 아래와 같은 명령어들에 대해서, 다음의 그림과 같은 화면을 통해 연습할 수 있다. commit, branch, checkout, cherry-pick, reset, revert, rebase, merge 또한 다음과 같이 원격 저장소에 push 또는 pull하기, clone 등도 연습할 수 있다.

문제 링크: 2168번 타일 위의 대각선 https://www.acmicpc.net/problem/2168 가로 길이를 x, 세로 길이를 y라 하고 GCD(x, y) = G라 하면, x = GX, y = GY와 같이 표현할 수 있다. 이 때 대각선의 기울기는 y/x = GY/GX = Y/X이고, 가로로 X칸, 세로로 Y칸 이동할 때마다 타일의 경계점과 만난다. 대각선 위에 X*Y의 사각형은 G개 있고, 대각선을 우하향으로 그린다고 할 때 그려진 타일은 반드시 왼쪽 상단에서 우측 하단으로 한 칸씩 이동하므로 각 사각형마다 x+y-1개의 타일에 대각선이 지나간다. 따라서 대각선이 그려져 있는 타일의 개수는 G*(X+Y-1)개이다. 여기서 최대공약수를 빨리 구하는 방법을 헤맸는데 유클리드 호제법을 떠올려야 한..

문제 링크: 11729번 하노이 탑 이동 순서 https://www.acmicpc.net/problem/11729 from, mid, to가 있을 때, n개를 from에서 to로 옮기기 위해서는... 1. n-1개를 from에서 mid로 옮긴다. 2. 1개를 from에서 to로 옮긴다. 3. n-1개를 mid에서 to로 옮긴다. 이런 아이디어를 기본으로 생각하면 되는 것 같다. def hanoi(n, f, m, t, arr): if n==1: arr[0] += 1 arr.append("{f} {t}".format(f=f, t=t)) return hanoi(n-1, f, t, m, arr) hanoi(1, f, m, t, arr) hanoi(n-1, m, f, t, arr) return n = int(in..

문제 링크: 2447번 별 찍기 10 https://www.acmicpc.net/problem/2447 재귀는 어렵다. 하지만 피할 수 없기에 즐겨야(?) 한다. 프랙탈이 모니터를 채울 때의 그 쾌감을...! 배열을 사용하면 '비교적' 쉽게 해결할 수 있는 문제이다. 다른 풀이를 보니까, 엄청 큰 2차원 배열을 미리 선언해놓고 인덱스를 통해 채워나가는 풀이도 있다. def paint(n): if n==1: return ['*'] arr = [0 for i in range(n)] prev = n//3 prevArr = paint(prev) idx = 0 for i in range(3): for j in range(prev): if i == 1: arr[idx] = prevArr[j]+' '*prev+pre..