알고리즘 (7) 썸네일형 리스트형 유클리드호제법 유클리드호제법을 사용하여 최대공약수를 찾는 알고리즘은 다음과 같다. pubic int getCommon(int a, intb){ int n=0; while(b!=0){ n = a%b; a = b; b = n; } return a; } 이 알고리즘은 a>b일 때 둘을 나누면서 최대 공약수를 찾는 방식이다. 이렇게 직접 알고리즘을 구현해도 되고 BigInteger의 메소드를 사용하는 방법도 있으며 그 방식은 아래와 같다. public int getCommon(int a, int b){ BigInteger num1 = BigInteger.valueOf(a); BigInteger num2 = BigInteger.valueOf(b); BigInteger gcd = num1.gcd(num2); return gcd... 최소신장트리 최소신장트리(Minimum Spanning Tree, MST) 신장트리(Spanning Tree)란 그래프의 모든 노드를 포함하고, 모든 노드가 서로 연결되어 있고, 트리의 속성을 만족하는 그래프를 뜻합니다. 최소신장트리(MST)란 신장트리 가운데 노드 가중치의 합이 최소인 신장트리를 뜻합니다. 노드 사이를 잇는 거리/비용 등을 최소로 하는 그래프를 의미합니다. MST 를 찾아내는 기법에는 크루스칼 알고리즘, 프림 알고리즘이 있습니다. String, StringBuilder, StringBuffer String과 StringBuffer, StringBuilder의 차이점은 String은 immutable(불변), StringBuffer는 mutable(변함)하다는 점입니다. String String 객체는 생성시 할당된 할당된 메모리 공간이 변하지 않습니다. 문자열 연산 -> "a" + "b" 새로운 String 객체를 만들고 새 String 객체에 연결된 문자열을 저장 후 그 객체 참조하도록 합니다. 즉, String 클래스 객체는 Heap 메모리 영역에 생성되며 생성된 객체 내부 내용을 변화시킬 수 없습니다. String 객체는 이러한 이유로 문자열 연산이 많은 경우, 그 성능이 좋지 않습니다. 하지만, Immutable 객체는 동기화에 신경쓰지 않아도 되기때문에(Thread-safe) 내부 데.. Hash Table 해싱이란 해시함수를 사용하여 고정된 크기의 값으로 변환하는 작업입니다. 해싱을 이용해 데이터를 저장하는 자료구조를 Hash Table이라합니다. 이는 기존 자료구조인 이진 탐색트리나 배열에 비해 빠른 속도로 탐색, 삽입, 삭제를 할 수 있습니다. Collection Data Structure Add Contains Remove Next HashSet Hash Table O(1) O(1) O(h/n) ArrayList Array O(1) O(n) O(n) Hash Table이란 해시함수를 사용해 변환한 값을 index로 삼아 key, value를 저장하는 자료구조입니다. 기본 연산으로는 탐색,삽입 삭제가 있습니다.' 해시테이블을 이해하기 위해선 '충돌(Collision)'에 대해 이해해야합니다. 적재율 적.. 스택과 큐 1. Stack 스택은 LIFO(Last In First Out) 구조입니다. top으로 정한곳을 통해서만 접근 가능하며, top을 통해 삽입하는 연산은 push, 삭제하는 연산은 pop이라 합니다. 스택은 시간 순서에 따라 자료가 쌓이고 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조적 특징을 가지고 있습니다. 비어있는 스택에서 자료를 추출하려고하는 경우 stack underflow라고 합니다. 스택이 넘치는 경우 stack overflow 라고 합니다. 스택으로 사용하기 좋은 분야는 아래와 같습니다. -웹 브라우저 방문기록: 가장 나중에 열린 페이지를 다시 보여줘야합니다. -실행 취소: 가장 나중에 실행된 것부터 실행 취소합니다. 2. Queue 큐는 FIFO(First In First Out).. console에서 값 읽을 때 백준 알고리즘 사이트에서 알고리즘 문제를 꾸준히 풀어보고 있습니다. 저는 주로 Java 언어를 사용하여 진행하고 있는데, 그 과정에서 컴파일에러, 시간초과 등 많은 에러를 보았습니다. 그 중 콘솔에서 입력 값을 받을 때 문제가 발생하는 경우가 있어 이 글을 작성합니다. Scanner 대신 BufferedReader를 ! BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String 을 int로 바꿀때 ! 1. charAt() br.readLine 을 하면 String 으로 그 값을 받아오는데, int 로 변경할 떄 Integer.parseInt를 주로 사용하였습니다. 그러나 최근 charAt을 응용하여 변경하는 법을 알게되.. 이차원 배열 정렬 이차원배열에서 2번째 인자, 즉 인덱스1에 대해 정렬하고자 할 때의 방법입니다. int[][] conference = {{10,1000},{5,2000}} Arrays.sort(conference, new Comparator() { @Override public int compare(final int[] entry1, final int[] entry2) { final Integer time1 = entry1[1]; final Integer time2 = entry2[1]; return Integer.compare(time1,time2); } }); Compartor를 이용하여서 1번째 인덱스를 이용하여 비교할 것임을 선언해주면 됩니다. 이전 1 다음