Razelo 기술노트

위상 정렬을 공부하는 와중에 이해가 가지 않는 부분이 있는데, 긴가민가해서 정확히 눈으로 확인해보고 싶어 직접 그림으로 풀어보았다. 이해가 가지 않는 부분은 다음과 같다. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있습니다. -> 사이클에 포함된 원소 중에서 어떠한 원소도 큐에 들어가지 못합니다. 왜 사이클에 포함된 원소는 어떤 것도 큐에 들어가지 못할까? 라는 생각이 들었는데, 머릿속으로 큐에 집어넣었다가 빼면서 하려니 중간에 실수를 할 수도 있을 것 같아서 바로 그림으로 그려보았다. 다음과 같이 사전에 준비된 그래프가 존재한다. 그리고 보면 알겠지만 (B -> D -> C -> B) 로의 사이클이 존재한다. 그럼 이제 A를 큐에 집어넣고, 간선을 삭제하면 다음과 같이 진행된..

제목과 동일한 질문을 교수님께 여쭤본 적이 있다. 답변은 아주 간단했는데, " MSD부터 정렬하게 되면 정렬이 되지 않습니다. " 였다. 사실 직접 해봤어야 했는데, 그 간단한 과정을 해보지 않고 질문을 해서 지금 생각해보니 조금 멍청한 질문이 아니었나 생각이 든다. 질문할 당시에는 왜 굳이 낮은 자리수부터 비교해야하는가에 대해 생각해보면서 낮은 자리수부터 비교한다면 A, B가 있다고 가정할때 A의 MSD가 B의 MSD보다 큼에도 불구하고 낮은 자리수부터 비교하면서 자리수를 거슬러 올라가는 과정에서는 그 사실을 알지 못함으로 A가 B보다 큼에도 계속해서 낮은 자리수를 비교함으로써 그것이 낭비라고 생각했다. 반면에 MSD부터 비교한다면 처음 비교할때부터 이미 A가 B보다 큼이 기정사실이 되어버리니 그 밑의..

자료구조와 알고리즘 입문 - 자바편에 힙정렬이 나왔다. 하노이의 탑도 이해가 잘안갔고, 특히 재귀적 호출이 너무 복잡했다. 그래서 일부는 직접 그림판에 그림을 그려서 영상으로 찍어서 내가 하는말을 들어가면서 이해했는데, 글쎄,,, 힙정렬이 좀 이해가 잘안간다. 이해가 안가는건 일단 외우라고 했으니... 일단은 외워야 겠지... 이게 안좋은 방법인건 알고 있다. 근데 일단은 머릿속에 집어넣고 그 다음에 이해해야겠다. package algorithm; public class heap { private void solve() { int[] array = {230,10,60,550,40,220,20}; heapSort(array); for(int v:array) { System.out.println(v); } ..