Razelo 기술노트

https://www.youtube.com/watch?v=IJDJ0kBx2LM

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

아래 두 코드는 같은 문제를 자바와 파이썬으로 각각 풀어낸 것이다. (오랜만에 풀어봤다.) 이분탐색문제였는데, 이 문제 뿐만 아니라 다른 문제들도 마찬가지로 작성해야할 코드의 양에 있어서 상당한 차이를 보였다. 자신이 가장 편한 언어를 선택하라고 해서 사실 c++과 파이썬, java중 어느 것을 선택하더라도 별 반 차이가 없는 상태에서 시작했었다. 당시에는 숙련도가 모두 비슷했었다. (c++ stl의 사용법을 100프로 알고있던 상태는 아니어서 c++의 경우 숙련도가 조금은 떨어지긴 했다.) 주로 사용하는 언어가 자바여서 자바로 주로 풀이하였는데, 한 문제를 풀면서 python으로도 똑같이 풀어보는 방식으로 진행했다. 한문제를 여러언어로 바꿔서 풀어본적이 대부분이었는데, 여지껏 문제를 풀면서 느낀 점이 ..

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

피보나치 구할때는 배열을 한칸 더 선언해줘야한다. 즉 [n+1] 이런식으로 하나 더 만들어놔야 한다. 왜냐면 n의 피보나치수를 구하고 싶다고 했을때 0부터 n-1까지 더한 수가 n에 기록되야 하기 때문이다. 즉 0~n-1은 n개인데 여기서 n칸인 1개까지 더해서 n+1이 필요한거다.

Recursive Call Algorithm (재귀 함수)Permalink Maximum value or Minimum value (최대값 또는 최소값 찾기) : 가장 큰 숫자를 기억해가며 진행함 Euclid (유클리드 알고리즘) : 두 정수의 최대공약수(GCD)를 빠르게 구하기 Factorial (팩토리얼) Fibonacci (피보나찌 수열) Sum (합계) Sorting Algorithm (정렬 알고리즘)Permalink Selection Sort (선택 정렬) https://www.daleseo.com/sort-selection/ Bubble Sort (버블 정렬) https://www.daleseo.com/sort-bubble/ Quick Sort (퀵 정렬) https://www.daleseo...

roka88.dev/98 기본 정렬 알고리즘의 종류와 정리 최종수정일자 : 2020-01-03 이 글은 이미 공부 했었으나, 정렬을 쉽게 정리하지 못하는 사람을 위해 정리하였다. 정렬의 종류도 많으며, 설명하기가 쉽지 않다. 동작은 다양하며, 머리속에 어렴풋이 roka88.dev ict-nroo.tistory.com/category/ICT%20Eng/Algorithm?page=5 'ICT Eng/Algorithm' 카테고리의 글 목록 (5 Page) 주니어 개발자가 성장하는 공간 ict-nroo.tistory.com

package list.doublylinkedlist.implementation; //양방향성이 있는 이중연결시스트. 더 많은 메모리를 사용하는 것이 단점임. public class DoublyLinkedList { private Node head; private Node tail; private int size = 0; private class Node{ private Object data; private Node next; private Node prev; public Node(Object input) { this.data = input; this.next = null; this.prev = null; } public String toString() { return String.valueOf(this..

package list.linkedlist.implementation; public class LinkedList { private Node head; private Node tail; private int size = 0; private class Node{ private Object data; private Node next; public Node(Object input) { this.data = input; this.next = null; } public String toString() { return String.valueOf(this.data); } } public void addFirst(Object input) { Node newNode = new Node(input); newNode.nex..

package algorithm; public class ArrayList { private int size = 0; private Object[] elementData = new Object[100]; public boolean addFirst(Object element) { return add(0,element); } public boolean addLast(Object element) { elementData[size] = element; size++; return true; } public boolean add(int index,Object element) { for(int i = size-1;i>=index;i--) { elementData[i+1] = elementData[i]; } eleme..

리스트와 배열의 차이 리스트에서 데이터를 삭제하면, 해당 데이터가 사라지면서 해당 데이터 뒤에 있던 데이터가 한칸 앞으로 전진하게 된다. 하지만 배열에서 요쇼를 삭제하면, 그냥 그 자리는 비어 있게 된다. (특정한 처리를 해주지 않는이상) 그러므로, 리스트는 데이터가 있는지 없는지를 체크하지 않아도 되는 장점이 있다. 하지만, 배열은 어딘가가 비어있을 수도 있으므로, 데이터가 있는지 없는지 확인해야 한다. 그만큼 리스트보다 더 많은 공간을 차지한다. 하지만 이게 오히려 장점이 될 수 있다. 요소의 자리 (즉 인덱스)값이 바뀌지 않으므로, 배열은 특정 값의 키 즉 인덱스를 유지할 수 있다. 하지만 리스트는 앞의 데이터가 삭제되면, 한칸씩 앞으로 자동으로 당기므로, 인덱스 값이 변한다. 그러므로, 배열에서만..

자료구조와 알고리즘 입문 - 자바편에 힙정렬이 나왔다. 하노이의 탑도 이해가 잘안갔고, 특히 재귀적 호출이 너무 복잡했다. 그래서 일부는 직접 그림판에 그림을 그려서 영상으로 찍어서 내가 하는말을 들어가면서 이해했는데, 글쎄,,, 힙정렬이 좀 이해가 잘안간다. 이해가 안가는건 일단 외우라고 했으니... 일단은 외워야 겠지... 이게 안좋은 방법인건 알고 있다. 근데 일단은 머릿속에 집어넣고 그 다음에 이해해야겠다. 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); } ..