BLUE DOLPHIN

2448번: 별찍기 - 11 풀이 분할&정복을 하면 된다. 큰 삼각형에서 3개로 삼분할 되는 프랙탈이 생기게 된다. 재귀함수를 사용해 삼분할에서 배열에 할당해주면 된다. 코드 #include #include int n; char arr[3072][6143]; void f(int n, int x, int y) { if (n == 3) { arr[y][x] = arr[y + 1][x - 1] = arr[y + 1][x + 1] = '*'; for (int i = 0; i > 1; f(dv, x, y); f(dv, x - dv, y + dv); f(dv, x + dv, y + dv); } int mai..

2523번: 별찍기 - 13 풀이 증가하는 삼각형 만들고 감소하는 삼각형 그려주면 된다. 코드 #include int main() { int n; scanf("%d", &n); for (int i = 0; i < n - 1; ++i, puts("")) { for (int j = 0; j = 0; --i, puts("")) { for (int j = 0; j

2의 2000승 출력하기 설명 2천승이기 때문에 밖에 for문에서 2천 번 돌려주고 안에서는 곱하면서 받아 올림해주면 된다. 마지막으로 배열로 따지면 뒤에서부터 출력하면 된다. 코드 #include int main() { int digit[603] = { 0, }; digit[0] = 1; for (int i = 0; i = 10) { digit[j + 1] += digit[j] / 10; digit[j] %= 10; } } } for (int i = 602; i >= 0; --i) { printf("%d", ..

2447번: 별찍기 - 10 풀이 규칙성을 찾는 수 밖에 없는데 대개 한 칸 빈칸은 쉽게 찾을 수 있을텐데 큰 빈칸을 찾는 게 어려울 수 있다. 이것은 표를 그려보면 쉽게 알 수 있는데 n=9일 때를 그려보면 '나누기 3의 몫’이 1인 구간만 빈칸인 것을 알 수 있다. 코드 #include int n; int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { int dx = i, dy = j; while (dx) { if (dx % 3 == 1 && dy % 3 == 1) break; dx /= 3, dy /= 3; } putchar(dx ? ' ' : '*'); } puts(""); } return ..

1991번: 트리 순회 풀이 입력이 알파벳 순서대로 주어진다. 재귀 함수를 잘 이용한다!(재귀 함수 안 쓰면 굉장히 귀찮아짐) 코드 #include #include // hint: these alphabet inputs are inputed as increasing sequence struct Node { int mValue; int mNextLeft; int mNextRight; }; struct Node arr[26]; char root, left, right; void PrintPreorder(int c); void PrintInorder(int c); void PrintPostorder(int c); int main() { int N; for (int i = 0; i < 26; ++i) { arr..

비선형 구조 이번 글은 비선형 구조란 무엇이고 탐색하는 대표적인 방법, 그래프 구현 방법을 설명한다. Reference> 트리, 그래프 비선형 구조란? i번째 원소를 탐색한 다음 그 원소와 연결된 다른 원소를 탐색 할 때, 다음에 탐색 가능한 원소가 여러 개 존재하는 구조. 일반적으로 트리나 그래프 형태로 자료를 구성할 수 있을 때 해당한다. 비선형 구조에서 탐색 방법 주로 트리나 그래프가 비선형 구조의 대표적인 형태이다. 비선형 구조는 데이터가 순차적으로 있지 않기 때문에 스택이나 큐를 이용해서 탐색을 한다. 비선형 구조에서 키워드 데이터가 있는 곳: 노드(node)/정점(vertex) 데이터를 잇는 선: 간선(edge)/링크(link) 간선은 화살표 유무에 따라 양/단방향으로 표현 가능하고, 간선에는..

Using loop unsigned long long pow(unsigned long long base, int exp) { long long ans = base; for (int i = 1; i < exp; ++i) { ans *= base; } return ans; } 하지만 xnx^nxn에서 nnn이 굉장히 커졌다고 생각했을 때는 이 방법은 굉장히 느리다. Using Recursive Function unsigned long long pow(unsigned long long base, int exp) { if (exp == 0) return 1; if (exp & 1) return base * pow(base * base, (exp - 1) / 2); else return pow(base * bas..

1009번: 분산처리풀이를 해주면 된다. 하지만 long long형도 100^1000000까지는 저장하지 못하기 때문에 그리고 우리의 목적에만 두자면 굳이 a^b를 계산한 후 %10을 할 필요가 없고 연산 중간마다 %10 연산을 해주면 된다.또한 단순히 반복문을 돌려서 계산해도 되지만 제곱의 성질인 을 이용하면 훨씬 더 빠른 연산이 가능하다. 이 연산에 대한 설명은 여기를 눌러서 확인하길 바란다.코드1234567891011121314151617181920212223#include int pow(int a, int b){ int ans = 1; while (b) { if (b & 1) ans = (ans * a) % 10; a = (a * a) % 10; b >>= 1; } return ans;} int ..

선형 구조의 탐색 이번 글은 선형 구조란 무엇이고 선형 구조 속에서 탐색하는 대표적인 방법 2가지를 설명한다. 선형 구조란? 선형 구조란 프로그래밍 언어를 배울 때 배우는 배열, 연결 리스트 같은 말 그대로 선 같이 생긴 데이터 구조를 선형 구조라고 한다. 반대로 비선형 구조는 트리, 그래프 등이 있다. [배열] - 대표적인 선형 구조 [연결 리스트] - 얘도 선형 구조다. 선형 탐색 선형 탐색에는 대표적으로 전체 탐색과 이분 탐색(이진 탐색)이 있다. 전체 탐색은 말 그대로 전체를 순환해서 어떠한 값을 찾는 것을 말하고 이분 탐색은 정렬된 선형 구조에서 부분적으로만 탐색을 해서 값을 찾는 부분 탐색을 말한다. 구체적인 예시와 설명을 보면서 설명하면 좋을 것 같다. 전체 탐색 전체 탐색은 전체를 순환하기..

오름차순으로 정렬하는 것을 기본으로 한다. 그림삽입 정렬은 인덱스에서 하나를 잡아서, 올바른 곳에 삽입하는 그림을 가지고 있다.보통 오름차순 정렬을 하기 때문에 왼쪽부터 순차적으로 인덱스를 하나씩 잡아서 작업을 하게 된다.선택한 인덱스의 왼쪽에 정렬된 배열과 비교하여 정렬을 한다. 이 알고리즘의 그림은 이 정도만 기억하면 될 것 같고 예시를 보면서 구체적으로 살펴보자.예시3 4 1 2 75개의 정렬되지 않은 숫자들이 있다.위에서 설명했다시피 인덱스 하나를 왼쪽부터 잡아서 올바르게 삽입하면 된다.첫 번째 위치에 있는 '3'은 해봤자 왼쪽에 아무 배열이 없으므로 두 번째 위치부터 작업한다. 1) 3 4 1 2 7왼쪽 배열과 비교했을 때 변경할 것이 없으므로 그대로 유지한다.2) 3 4 1 2 7왼쪽 배열과 ..