[2993] 탑

https://www.acmicpc.net/problem/2493 맨첨에 좀 어려워서 해맨거같은데 다음과 같은 방식으로 풀면된다. 타워를 하나씩 스택에 집어넣으면서 가능성이 없는애들을 제거해주면 바로 스택에 남아 있는 애가 수신하고 있는 애가 된다. 만약에 스택에 데이터가 없으면 그냥 0으로 대입하면된다.

최대 공약수 문제

이거보고 B의 약수를 뭘로 정해야하는지 계속 생각했는데 보니까 낚시 문제 그냥 회수상관없이니 0번해도된다. 결국 A와 B의 공약수를 구하고 공통된부분이 있으면 곱해주면된다.

알고리즘 배낭문제

가장 흔한 문제인 배낭문제는 다양한 문제 풀이법이 있습니다. 먼저 가장 쉽게 재귀로 풀어보겠습니다. 재귀는 내가 이재품을 살때와 안살때를 재귀함수로 구현해주면됩니다. 일단 간단하게 배낭크기를 10으로 잡고 5개의 물건이 있다고 보면됩니다. 간단한 코드는 위와같다. 하지만 위의 코드는 계산했음에도 불구하고 계산할려는 특징이 있어 메모리로 계산을 했는지 안했는지 추가해야합니다. 이를 가지치기라고 하는데 다음에 설명하고 더보기…

스택을 이용한 미로찾기

  스택을 이용한 미로찾기입니다. 원리는 매우 간단합니다. 일단 가본 길을 전부 스택에 쌓고 갈수 있는 공간이 없으면 스택의 데이터를 POP하고 위에 작업을 계속 진행합니다. 길이냐 벽이냐는 원핫코딩으로 코딩하였습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 더보기…

글쓴이 kudwafter,

[밸런싱 트리] AVL Tree

밸런싱 트리에서 가장 간단한 AVL트리이다. 이 트리는 밸런싱은 회전으로 구한다. 적당한 그림이 없어 위키피디아에서 가져왔다. 위의 그림에서 보듯이 오른쪽으로 편향되어있어서 RR트리라고 한다. 반대로 왼쪽이면 LL이라고 한다. 이런 경우 밸런싱하기 위해서는 RR트리인경우 오른쪽으로 편향되어있으니 왼쪽으로 회전시켜 밸런싱을 구한다. LL경우인경우는 RR트리를 반대로 회전 하면된다. 위의 그림은 오른쪽하고 왼쪽으로 편향되어 있는걸 볼수 있다. 더보기…