Algorithm/알고리즘 이론 12

위상 정렬 (Topological Sort)의 사이클 존재 판별

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

Java vs Python3 vs C++ for coding test

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

RadixSort(기수정렬) 에서는 왜 낮은 자리수부터 비교해야 하는걸까

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

알고리즘 스터디

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

DoublyLinkedList 코드

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..

반응형