데이터 집합일때 빠르게 조회하기

<i,j>와 <j,i> 같을시 이 문제를 순열문제로 볼수있겠지만 한번더 생각하면 그래프문제로 풀수도 있다. 예로 동일한 원이 3개가 있는데 이를 각가 충돌처리한다고 생각해보자. 출돌체크하기위해서는 한 객체와 따른 객체를 비교를해야하는데 가지고 있는 모든 원에 대해 충돌체크하면 아래와 같은 코드가 발생한다. 하지만 이걸 배열 그래프로 표현하게 되면 아래와 같은 식이 나오게 된다. 위 그림을 보면 알겠지만 대각선을 기준으로 대칭이기 소개 더보기 <i,j> 데이터 집합일때 빠르게 조회하기[…]

[2993] 탑

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

알고리즘 배낭문제

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

스택을 이용한 미로찾기

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

[밸런싱 트리] AVL Tree

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