Development/Informatics2 [KOI]두부 모판 자르기(bean curd) [KOI]두부 모판 자르기(bean curd) 개인적으로 좋아하는 문제다. 2006년도 정보올림피아드 고등부 2번이다. 이걸 풀 땐 정말 정보에 대한 의지가 불타올랐던 시절이었는데.. 암튼 시작한다. 결국 두부모판을 어떻게 하면 가장 비싸게 팔수 있을지 쪼개라는 거다. 이런건 누가봐도 백트랙킹이다. 그런데 어떻게 백트랙킹을 해야하는가 - 이게 관건이다. 어려웠지만 그때 죽이되든 밥이되든 해서 풀었다. 지금 보면 참 대견하다. 일단 백트랙킹을 하되 일반적인 재귀적, 그런 백트랙킹은 안된다. 아 물론 될수 있겠지만 나로써 별로 상상이 안간다. 그리고 원래 재귀는 안할수록 좋다고 하지 않은가. 이건 재귀의 내부 스택을 이용하지 않은 그냥 스택 자체를 만들어서 풀어야된다고 결론지었다. 그리고 스택을 직접 만든 .. 2016. 10. 13. [자료구조]이진탐색트리-Binary Search Tree 알고리즘 - 이진탐색 이진탐색(Binary Search)은 탐색 기법중 하나입니다. 이 알고리즘을 위해 우리는 이진트리(Binary Tree)를 사용하는데 이진트리는 아시다시피 다음 그림과 같습니다. 이진트리(Binary Tree)는 각 Node에 Sibling의 최대 개수가 2개입니다. 이 Binary Tree에 "좌측 노드에는 부모보다 작은 Value를, 우측 노드에는 부모보다 큰 Value를 갖는다." 라는 규칙을 정하면 이진 탐색 트리로 사용할 수 있습니다. Binary Search Algorithm의 시간복잡도(Time Complexity)는 O(lg n)으로 탐색중 가장 빠릅니다. (물론, O(1)의 Hash 탐색을 제외!!) (Wikipedia 인용) 트리의 구현은 다양한 방법이 있지만 배열.. 2014. 6. 26. 이전 1 다음
