VB.NET 알고리즘 구현 - Stack, Queue Data Type
2018.02.27 20:56
VB.NET 알고리즘 구현 - Stack, Queue Data Type
맨땅에 헤딩하면서 플그램을 배웠던 나로서는 좀 머리가 아팠던 부분이었다. 강의시간에는 졸았고 자격증시험에서는 외우기만 했으니 남는것은 없었다.다시 내공을 키우려고 맘먹고 구현해가면서 공부하던 시절 이 부분을 마치고 나서 무척이나 상쾌했던 기억이 있다.
재귀호출의 건셉 : 코딩라인수를 무척이나 줄여주는 재귀호출에는 무서운 함정이 있는데 잘못하면 무한히 반복되는 루틴이 되어버린다. Stack Overflow를 일으켜서 시스템을 바보로 만들어 버리곤한다. 재귀호출 알고리즘의 적용요건은 문제의 크기가 점점 감소해야 하고 종료조건이 있어야 한다. 간단한 예로 Factorial 의 경우 문제의 크기감소 : N! = N * (N-1)! 종료조건 : 0! = 1 이 있다.
예제소스를 실행해서 [VB알고리즘] - [알고리즘1] 메뉴클릭
"재귀호출" 창에서 해당 버튼클릭 (frmRecursion 폼 참조) 하면 내용 확인이 가능하다.
1.실습내용.
1)최대공약수구하기
재귀호출을 사용하여 최대공약수를 구하는 루틴을 구현한다.
먼저 두수 u > v 인경우 u와 v의 최대공약수는 u와 u-v의 최대공약수라는 사실에 대해 이해해야한다.
2)Fibonacci 수열
예를들어 Fibonacci(5) = Fibonacci(4) + Fibonacci(3)
3)Tree그리기
2Way 재귀호출로 Fixed 2진트리, RandomColed 2진트리 그리기
pGraphics.DrawLine() 함수를 사용 두점 사이에 선을 긋는다.
왠삼각함수 ? :
(0, 0)를 기준으로 빗변의길이 r과 각도 Θ를 이용해서 다음점인 (x,y)를 구하기 위해서 sin, cos 함수를 사용한다.
혼돈을 피하기 위해 '빗변'의 길이과 '각도'에 유념하자.
clsAlg1.DrawFixTree(130, 200, 12, 40, 0.0, myGraphics)
시작점 (X0, Y0) = (픽처박스의 폭 /2 , 픽처박스의 높이) = (130 픽셀, 200픽셀)
빗변 L0는 40 (0.8%로 감소), 비틀림각 trun0 = 0 (0.5씩증감)
결과적으로 처음으로 비틀리는 (X2, Y2) = (130 - 40 * System.Math.Cos(0.5), 160 - 40 * System.Math.Cos(0.5)) 가 된다.
2.최대공약수 구하기
Public Function get_gcd_recur(ByVal u As Integer, ByVal v As Integer) As Integer
If v = 0 Then
Return u
Else
Return get_gcd_recur(v, u Mod v)
End If
End Function
3.Fibonacci 수열
'Interger형과 Short형 함수 중복정의 해서 호출시 명시적인 형변환 필요
'Short 형은 -32,768부터 32,767까지의 부호 있는 16비트(2바이트) 정수를 저장 [VB6에서의 Integer 형(%)]
'n=23까지 가능
'함수호출
Dim Sortresult As Short = clsAlg1.Fibonacci(CType(txtFop1.Text, Short))
lblFresult.Text = Format(Sortresult, "#,###")
Public Function Fibonacci(ByVal n As Short) As Short
'Short 형은 -32,768부터 32,767까지의 부호 있는 16비트(2바이트) 정수를 저장 [VB6에서의 Integer 형(%)]
Try
If n = 1 Or n = 2 Then
Return 1
Else
Return Fibonacci(n - 1) + Fibonacci(n - 2)
End If
Catch exp As System.OverflowException
MessageBox.Show("오버플로 Short 범위 Number : " & n, exp.Source, MessageBoxButtons.OK, MessageBoxIcon.Error)
Return 0
Catch exp As System.Exception
MessageBox.Show(exp.Message, exp.Source, MessageBoxButtons.OK, MessageBoxIcon.Error)
Return 0
End Try
End Function
4.FixedTree그리기
If optFixed.Checked = True Then '고정Tree
'시작x좌표, 시작y좌표, 하위가지수Level, 가지길이,꺽임각, 그릴타겟(픽처박스의 Graphics개체를 넘김)
clsAlg1.DrawFixTree(130, 200, 12, 40, 0.0, myGraphics)
Else 'RandomTree
clsAlg1.DrawRndTree(130, 200, 10, 40, 0.0, myGraphics)
End If
'반환값이 없는 Sub 프로시저로 선언해 보자.
Public Sub DrawFixTree(ByVal x As Integer, ByVal y As Integer, ByVal nOrder As Integer, _
ByVal nLength As Integer, ByVal dAngle As Double, ByVal pGraphics As Graphics)
Try
Dim dx As Integer = Convert.ToInt32(nLength * System.Math.Sin(dAngle))
Dim dy As Integer = Convert.ToInt32(nLength * System.Math.Cos(dAngle))
'파라미터로 넘어온 (x, y) 에서 다음좌표로 선을그림 130, 200 130, 200-40
pGraphics.DrawLine(Pens.Blue, x, y, x - dx, y - dy)
'다음에서 nOrder = 2 값을 변경해 보면서 트리레벨 및 오류가 발생 시 처리를 확인해 보자
'If nOrder = 2 Then Throw New ApplicationException("오류 만들어보기")
If nOrder > 0 Then '재귀호출의 종료조건
'2Way 재귀호출 (즉2진트리) 길이는 0.8로 감소, 0.5배수로 비틀기
DrawFixTree(x - dx, y - dy, nOrder - 1, Convert.ToInt32(nLength * 0.8), dAngle + 0.5, pGraphics)
DrawFixTree(x - dx, y - dy, nOrder - 1, Convert.ToInt32(nLength * 0.8), dAngle - 0.5, pGraphics)
End If
Catch exp As System.ApplicationException
Debug.Print("오류발생 : Level -" & nOrder & " 길이 -" & nLength & " 각도 : " & dAngle)
Exit Sub
Catch exp As System.Exception
MessageBox.Show(exp.Message, exp.Source, MessageBoxButtons.OK, MessageBoxIcon.Error)
Exit Sub
End Try
End Sub
^^ RandomTree는 소스에서 확인하시기 바랍니당.
오늘 실습해볼 내용은 노멀트리의 Level Order운행과 Pre Order운행을 Stack과 Queue를 이용해서 구현해 보는 내용입니다.
제목은 Stack, Queue Data Type 이라고 했지만 구현부분은 List만 계속하니까 지루해서 제외했습니다. 대신 책등에서 마르고 닳도록 나오는 이넘들의 특성에 대해서 몇줄 적고 실제사용은 System.Collections.Stack 과 System.Collections.Queue 를 사용 했습니다.
먼저함 돌려보시려면 [VB알고리즘]-[자료구조] 메뉴를 클릭하시고 다음과 같은 화면이 나오면
"폴더선택" -> "일반트리" 버튼클릭 -> "LevelOrder (Queue)" 버튼을 클릭해 보시면 됩니다.
@보통 반말로 글을 쓰는데 자신에게 말하는거지 글을 보시는 분들에게 말하는 것은 아니니 오해 없으시기 바랍니다.
1.Stack, Queue Data Type
Stack이란?
입구와 출구가 하나이고 한번에 한 아이템만 입출가능한 자료구조
배열이나 연결리스트로 손쉽게 구현가능
LIFO (Last In First Out) : 최종 입력된 자료가 가장먼저 인출됨
Push : 스택에 데이타를 추가함
Pop : 스택에서 가장 최근에 추가된 데이타를 인출
Peek : 스택에서 최상단 데이타를 인출하지 않고 조회
Top : 스택의 최상단 아이템 또는 아이템의 인덱스
Queue란?
입구와 출구가 따로 있고 한번에 한 아이템만 입출가능한 자료구조
FIFO (First In First Out) : 최초로 입력한 자료가 가정먼저 인출됨
Put : 큐에 데이타를 추가함
Get : 큐에서 가장 먼저 추가된 데이타를 인출
Front : 큐에서 가장먼저 추가된 선두 아이템 또는 아이템의 인덱스
Rear : 큐에서 가장나중에 추가된 꼬리 아이템 또는 인덱스
Peek : 큐에서 최선두 데이타를 인출하지 않고 조회
2.주제
Queue 기반 : Level-order 노멀트리운행 구현 : 위에서 아래로 좌에서 우로 트리운행 (직관적)
Stack 기반 : Pre-order 노멀트리 운행 / 포스트오더 노드삭제
2.1. 큐를 활용한 Normal트리의 LevelOrder 트리운행
Private Sub btnLevel_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnLevel.Click
lvwTree.Items.Clear()
Dim sysQueue As New System.Collections.Queue
Dim order As Integer
Dim tmpNode As NormalNode
'LevelOrderTraverse 시작
sysQueue.Enqueue(CType(tvwTree.Nodes(0), NormalNode))
Do While sysQueue.Count > 0
tmpNode = sysQueue.Dequeue '큐에서 자료인출
order = order + 1
tmpNode.NodeNum = order
AddToListView(tmpNode.Text, tmpNode.NodeNum, tmpNode.Level) ' 리스트뷰에 노드명, 운행순서, 레벨표시
For i As Integer = 0 To tmpNode.Nodes.Count - 1 ' 자식노드중 좌측에서 좌측노드 순으로 큐에 삽입
sysQueue.Enqueue(tmpNode.Nodes(i))
Next
Loop
End Sub
2.2. 스택을 사용한 Normal트리의 PreOrder 트리운행 (처음 노멀트리를 그린 순서와 동일)
Private Sub btnStackPre_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnStackPre.Click
lvwTree.Items.Clear()
Dim sysStack As New System.Collections.Stack
Dim order As Integer
Dim tmpNode As NormalNode
'PreOrderTraverse 시작
sysStack.Push(CType(tvwTree.Nodes(0), NormalNode))
Do While sysStack.Count > 0 ' 스택내에 자료가 있는동안
tmpNode = sysStack.Pop
order = order + 1
tmpNode.NodeNum = order
AddToListView(tmpNode.Text, tmpNode.NodeNum, tmpNode.Level) ' 리스트뷰에 노드명, 운행순서, 레벨표시
For i As Integer = tmpNode.Nodes.Count - 1 To 0 Step -1 ' 자식노드중 우측에서 좌측으로 푸시
sysStack.Push(tmpNode.Nodes(i))
Next
Loop
End Sub
2.3. Post Order 방식으로 운행 하면서 노드삭제
Private Sub btnNRemoveAll_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnNRemoveAll.Click
lvwTree.Items.Clear()
Dim sysStack As New System.Collections.Stack
Dim order As Integer
Dim tmpNode As NormalNode
'PreOrderTraverse 시작
sysStack.Push(CType(tvwTree.Nodes(0), NormalNode))
Do While sysStack.Count > 0
tmpNode = sysStack.Peek ' 스택에서 인출하지 않고 조회
If tmpNode.Nodes.Count = 0 Then
tmpNode = sysStack.Pop ' 자식노드가 없으면 인출
order = order + 1
tmpNode.NodeNum = order
AddToListView(tmpNode.Text, tmpNode.NodeNum, tmpNode.Level) ' 리스트뷰에 노드명, 운행순서, 레벨표시
tmpNode.Remove() ' 노드삭제
Else
For i As Integer = tmpNode.Nodes.Count - 1 To 0 Step -1 ' 자식노드중 우측에서 좌측으로 푸시
sysStack.Push(tmpNode.Nodes(i))
Next
End If
Loop
End Sub
2.3. Normal 트리 그리기 선택한 폴더를 기준으로 PreOrder방식으로 100여 개의 디랙토리 표시
Private Sub btnNormal_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnNormal.Click
If txtSelectDir.Text = "" Then Exit Sub
Dim strSelectedDirectory As String = txtSelectDir.Text
tvwTree.Nodes.Clear()
tvwTree.NodeCnt = 0
lvwTree.Items.Clear()
Try
Dim dnSelectedDirectory As NormalNode = New NormalNode(1)
' 선택한 디랙토리명을 루트로 한다.
dnSelectedDirectory.Text = strSelectedDirectory
' 트리뷰에 재정의된 TreeNode개체 추가
tvwTree.Nodes.Add(dnSelectedDirectory)
tvwTree.NodeCnt = 1 ' 루트노드를 추가했으므로 카운트 증가
dnSelectedDirectory.Text = dnSelectedDirectory.NodeNum & " " & dnSelectedDirectory.Text
dnSelectedDirectory.ContextMenuStrip = ContextMenuStrip1
' 하위트리를 추가시키고, 하위노드수를 계산함
SetSubNormalNode(strSelectedDirectory, dnSelectedDirectory)
chkBin.CheckState = CheckState.Unchecked ' 미채크상태로 : 채크박스의 TreeState = True
setMenu() ' 팝업메뉴와 다른버튼제어
dnSelectedDirectory.Expand()
Catch exc As Exception
End Try
End Sub
' 하위 디랙토리 노드를 표시한다.
Public Function SetSubNormalNode(ByVal strDirPath As String, ByRef mNode As NormalNode) As Boolean
' 현재 검색하고 있는 폴더를 상태바에 표시한다.
sbrScan.Text = "Scanning : " + strDirPath
Try
' 전달받은 문자열(폴더명)의 하위폴더를 문자열 배열에 세팅함
Dim astrSubDirectories As String() = Directory.GetDirectories(strDirPath)
Dim strSubDirectory As String
For Each strSubDirectory In astrSubDirectories
Dim dnSubNode As NormalNode = New NormalNode(tvwTree.NodeCnt + 1)
' \를 사용 풀패스에서 폴더명만 남김
dnSubNode.Text = strSubDirectory.Remove(0, strSubDirectory.LastIndexOf("\") + 1)
dnSubNode.Text = dnSubNode.NodeNum.ToString & " " & dnSubNode.Text
dnSubNode.ContextMenuStrip = ContextMenuStrip1
mNode.Nodes.Add(dnSubNode)
tvwTree.NodeCnt = tvwTree.NodeCnt + 1
If tvwTree.NodeCnt > 100 Then GoTo end_rtn
' 재귀호출로 하위폴더를 검색하여 하위노드를 추가한다.
SetSubNormalNode(strSubDirectory, dnSubNode)
Next
Catch exc As Exception
Return False
End Try
end_rtn:
sbrScan.Text = "Node Count > 100"
Return True
End Function
vbalgorithms_20061206-etruelove.zip
[출처] http://www.devpia.com/Maeul/Contents/Detail.aspx?BoardID=45&MAEULNO=18&no=253&page=2#
광고 클릭에서 발생하는 수익금은 모두 웹사이트 서버의 유지 및 관리, 그리고 기술 콘텐츠 향상을 위해 쓰여집니다.
