0. 서문
4월의 마지막날이 되었다.
RBTree 구현을 위해 공부중인데 솔직히 잘 모르겠다. C언어 문법도 부족하고 구현 자체도 어떻게 해야할지 도저히 감이 잡히지 않는다. 오늘 이진트리를 구현해보기는 했으나 솔직히 이걸로는 감이 잘 안잡히는 느낌...
C언어 문법을 좀 더 공부해야할지 아니면 이진트리 구현쪽을 좀 더 중점적으로 연습해야 할지 감이 잡히지 않는다...둘다 하긴 해야겠다만 일주일이라는 기간에서 어떻게 배분을 해야할지...
Will Smith - Prince Ali (From "Aladdin")
1. 최대공약수와 최소공배수
https://www.acmicpc.net/problem/2609
처음에 작성한 코드는 for문을 5번을 돌려서 답을 찾는 코드였기에 돌리나마나 시간초과가 나올게 뻔해서 결국 답을 찾아보게 되었다.
답을 찾아보니 수학적인 능력이 필요했던 문제로 유클리드 호제법 이라는것을 알고 있었다면 쉽게 풀 수 있는 문제였다.
파이썬에 해당하는 것이 이미 라이브러리로 있었지만 라이브러리를 쓰지 않고서도 구현하는 코드로도 풀어보았다. 둘다 걸리는 시간은 비슷했다.
라이브러리 X
import sys
A, B = map(int, input().split())
x, y = A, B
while y != 0:
x = x % y
x, y = y, x
print(x)
print((A*B)//x)라이브러리 O
import math
import sys
a, b = map(int, input().split())
print(math.gcd(a, b))
print(math.lcm(a, b))2. 럭키 스트레이트
https://www.acmicpc.net/problem/18406
약간 게임 느낌이 나는 문제였다. 푸는것 자체는 주어진 문자열을 절반으로 나누고 문자열을 인트형으로 변환시켜서 갑을 더해서 비교한후 결과값을 출력하는 식으로 구현하였다.
import sys
score = input()
score1 = score[:len(score)//2]
score2 = score[len(score)//2:]
result_1 = 0
result_2 = 0
for i in range(len(score)//2):
result_1 += int(score1[i])
result_2 += int(score2[i])
if result_1 == result_2:
print("LUCKY")
else:
print("READY")3. 모험가 길드
이코테에 있던 문제였다. 유형은 그리드였고 솔직히 어떻게 해야할지 방법을 모르겠어서 답을 보고말았다.
숫자를 입력받은 후 입력받은 수 (해당맴버의 공포도) 가 현제까지의 카운트(파티원 수) 보다 작거나 같다면 해당하는 파티는 구성을 종료하고 다음 파티를 구성하는 그런 방식이었다.
n = int(input())
arr = list(map(int, input().split()))
result = 0
count = 0
for i in arr:
result += 1
if result >= i:
result = 0
count += 1
print(count)4. 곱하기 혹은 더하기
문제를 푸는 방법은 바로 보인것이 숫자가 0, 1 이 아니면 곱하고 0, 1이면 더하는 식으로 구현하면 된다는것이 바로 보였기에 구현함에 있어서 문제가 없었다.
확실히 이럴때마다 실력이 늘었다는 생각을 하게 된다.
number = input()
result = int(number[0])
for i in range(1, len(number)):
num = int(number[i])
if num <= 1 or result <= 1:
result += num
else:
result *= num
print(result)5. 이진트리구현 (탐색, 삽입, 삭제)
해당하는 강의영상을 보고 구현하였다.
RBTree 를 위해서 본 영상인데 어떻게 적용이 될거같으면서 방법이 쉽게 감이 잡히지 않는다...
#include <stdio.h>
#include <stdlib.h>
typedef char data;
typedef struct _Node
{
char key;
struct _Node* left;
struct _Node* right;
/* data */
}Node;
Node* searchBST(Node *root, char x)
{
Node* p = root;
while (p != NULL)
{
if (p->key == x)
return p;
else if (p->key < x)
p = p->right;
else
p = p->left;
}
return NULL;
}
Node* insertBST(Node *root, char x)
{
Node* p = root;
Node* parent = NULL;
while (p != NULL)
{
parent = p;
if (p->key == x)
{
printf("같은 키가 있습니다\n");
return p;
}
else if (p->key < x)
p = p->right;
else
p = p->left;
}
Node* newNode = (Node*)malloc(sizeof(Node));
newNode -> key = x;
newNode -> left = newNode -> right = NULL;
if (parent != NULL)
{
if(parent -> key < newNode -> key)
parent->right = newNode;
else
parent -> left = newNode;
}
return newNode;
}
Node* deleteBST(Node *root, char x)
{
Node* p = root;
Node* parent = NULL;
while ((p != NULL) && (p->key != x))
{
if (p->key == x)
{
printf("같은 키가 있습니다\n");
return p;
}
else if (p->key < x)
p = p->right;
else
p = p->left;
}
if (p==NULL)
{
printf("없음\n");
return root;
}
if (p->left == NULL && p->right == NULL)
{
if(parent == NULL)
root = NULL;
else
{
if (parent -> left == p)
parent -> left == NULL;
else
parent -> right = NULL;
}
}
else if (p->left == NULL || p->right == NULL)
{
Node* child = (p->left != NULL) ? p->left : p->right;
if (parent == NULL)
root = child;
else
{
if(parent->left == p)
parent -> left = child;
else
parent -> right = child;
}
}
else
{
Node* succ_parent = p;
Node* succ = p-> right;
while (succ->left != NULL)
{
succ_parent = succ;
succ = succ ->left;
}
p -> key = succ -> key;
if (succ_parent -> left == succ)
succ_parent->left = succ->right;
else
succ_parent -> right = succ -> right;
p = succ;
}
free(p);
return root;
}
void Inorder(Node* root)
{
if(root == NULL)
return;
Inorder(root->left);
printf("%c", root->key);
Inorder(root->right);
}
int main()
{
Node* root = insertBST(NULL, 'D');
insertBST(root, 'I');
insertBST(root, 'F');
insertBST(root, 'A');
insertBST(root, 'G');
insertBST(root, 'C');
insertBST(root, 'J');
Inorder(root); printf("\n");
return 0;
}