알고리즘14

• [최단경로] 다익스트라 알고리즘 Dijkstra Algorithm http://devdasom.tistory.com/86 다익스트라 알고리즘은 음수 가중치를 갖지 않는 방향이 있는 그래프에서 출발점과 도착점 사이의 최단 경로를 알아내는 알고리즘.우선순위 큐를 사용하여 현재 가장 짧은 거리를 가진 정점을 찾아 다음 방문 정점으로 선택한다. package path.bj1753; import java.io.*; import java.util.PriorityQueue; import java.util.StringTokenizer; import java.util.Vector; /** * Created by dasom on 2016-10-18. */ public class DijkstraAlgorithm { public static final int INF = 10000000; p.. 알고리즘 2016. 12. 12.

• KMP : 문자열 검색 알고리즘 http://bowbowbow.tistory.com/6 문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 Ctrl+F 단축키를 눌러 검색할 수 있습니다. 아래 이미지는 브라우저에서 "테이프"를 검색했을 때 결과를 캡쳐한 것입니다. 본문에서 89개의 "테이프"를 찾았다고 순식간에 알려주네요. 이렇게 텍스트내(본문)에서 특정 문자열, 패턴("테이프")를 찾는 것을 문자열 검색이라고 부릅니다.이 문자열 검색은 어떤 방식으로 구현되는걸까요? 가장 단순한 문자열 검색 먼저 가장 단순한 방법의 문자열 검색을 생각해봅시다.텍스트 "ABCABABCDE"에서 패턴 "ABC"가 어디서 등장하는지 찾아봅시다. 패턴 "ABC"를 한자리씩 옮기면서 같은지 비교합니다. 같아? AB .. 알고리즘 2016. 12. 7.

• Counting Sort : 계수 정렬 http://bowbowbow.tistory.com/8 Counting SortCounting Sort소개정렬 과정애니메이션 예시구현정리끝소개Counting Sort는 정렬 알고리즘으로 의 시간복잡도를 갖습니다. 반면 일반적 상황에서 가장 빠른 정렬 알고리즘인 Quick Sort의 시간복잡도 입니다.Counting Sort는 어떻게 이렇게 빠를까요? 그럼 왜 대부분의 정렬이 필요한 상황에서 더 빠른 Counting Sort를 안 쓰고 Quick Sort를 쓸까요?Counting Sort가 어떻게 작동하는지 이해하고 나면 위 의문에 대한 답을 스스로 할 수 있을 겁니다!정렬 과정다음과 같은 수열 A를 정렬 해야하는 상황을 생각해봅시다.위 수열을 정렬하면 아래와 같은 수열 B를 얻습니다.Counting So.. 알고리즘 2016. 12. 7.

• 기본 정렬 알고리즘 ( 선택, 삽입, 버블, 머지, 퀵 소트) http://hsp1116.tistory.com/33 알고리즘 2016. 12. 7.

• 모르겠음..[JAVA_알고리즘] 비트마스크를 이용한 에라토스테네스의 체 구현 [JAVA_알고리즘] 비트마스크를 이용한 에라토스테네스의 체 구현[JAVA_알고리즘] 비트마스크를 이용한 에라토스테네스의 체 구현 에라토스테네스의 체 란 위 그림과 같이 자연수 n이하의 소수를 구하는 알고리즘 으로써, 소수가 아닌 수의 배수를 전부 지워나가는 방법이다. 자세히 설명해 보자면 1) 2는 소수이므로 2의 배수를 전부 지운다. 2) 다음으로 3또한 소수이므로 3의 배수를 전부 지운다. 3) 4는 이미 1번에 의해 지워졌으므로 5로 넘어간다. 4) 5는 남아있으므로 소수가 아니다. 그러므로 5의 배수를 지운다. 5) 이런방법으로 n이하의 자연수 중에 남아있는 수를 탐색한 다음에 그 수의 배수를 전부 지운다. 굉장히 쉬운 원리이고 굉장히 빠르게 동작하지만, n이 커지면 커질수록 메모리 사용량의 문.. 알고리즘 2016. 11. 21.

• [C++] 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체 http://marobiana.tistory.com/91 소수 구하기 최적의 알고리즘 1편에서 (http://marobiana.tistory.com/89) 주어진 수보다 작은 수의 소수들로 나누는게 성능이 좋다고 했었는데,그것보다 더 좋은 알고리즘을 찾아냈다.ㅋㅋ이것보다 더 좋은 방법은 아마도 없을 것이라 자신함 !! 만약 있다면 댓글 달아주시기 바람. 요번에는 c++로 구현해보았음. 1. 알고리즘 에라토스테네스의 체 (Sieve of Eratosthenes)라는 알고리즘이다.아래 그림을 보면 무엇인지 알 수 있다. 120까지의 모든 소수를 구한다고 해보자. 2부터 120까지 배열에 모두 넣은 후소수가 아닌 것들을 모두 체크해버리는 것이다. 2를 제외한 모든 2의 배수를 체크한다.3을 제외한 모든 3의 .. 알고리즘 2016. 11. 1.

• [JAVA] 소수 구하기 최적의 알고리즘 (1) http://marobiana.tistory.com/89 한달 전에 면접에서 소수를 손코딩하라는 명을 받았다. (인성면접이라는 훼이크에 당해버렸음 @_@) 소수에 대해서는 깊이 생각해본적이 없었는데..이번일을 계기로 더더욱 최적의 방법을 생각하는 버릇을 들이겠다는 다짐을 하게되었다. 1. 소수(Prime Number)란 무엇인가? 2, 3, 5, 7, 11, 13, 17.... 약수가 1과 자기 자신 뿐인 수이다. 2. 소수를 어떻게 구할까? (알고리즘) 약수가 1과 자신뿐인 것을 확인해야한다. 그러려면??? 즉, 자기 자신보다 작은 수들을 나누어봐서, 하나라도 나누어지면 소수가 아닌 것이다.(어떤 수의 배수이면 안된다는 것) 보통은 여기까지만 생각하고 코딩을 시작할 것이다.그런데 조금만 더 생각해보면 .. 알고리즘 2016. 11. 1.

• [java] 순열 C++ 같은 경우에는 표준 라이브러리인 STL에 포함된 next_permutation()함수에서 모든 순열을 생성해준다.가능한 순열의 수는 N!인데, N이 10을 넘어간다면 시간 안에 모든 순열을 생성하기 어려우므로 전체를 생성하는방법 외에 다른 방법을 찾아본다. 12345678910111213141516171819202122232425// n : 전체 원소의 개수// picked : 지금까지 고른 원소의 개수// isPick : 이전에 선택된 원소인지 저장하고있는 변수// n개의 원소의 모든 순열을 구하는 방법int n;void permutation( ArrayList picked, boolean isPick[] ){ // 기저사례 : 모든 개수를 뽑아냈다. if( picked.size() == n ).. 알고리즘 2016. 10. 21.

• [ java ] 중요~! List , Map , Set 의 정렬기능 ( 펌 ) http://promc.tistory.com/entry/List-Map-Set-%EC%9D%98-%EC%A0%95%EB%A0%AC%EA%B8%B0%EB%8A%A5-%ED%8E%8C List , Map , Set 의 정렬기능 ( 펌 )[Programming/JAVA]객체들을 조작하기 위한 자료구조로 자바는 배열이나 Collection Framework 내의 여러클래스를 제공하고 있습니다. Collection Framework는 크게 3가지 형태로 분류할 수 있는데 간단하게 살펴 보자면 - Map : key와 Value를 가지는 자료구조입니다. HashMap, Hashtable, TreeMap과 같은 클래스들을 자주 쓰죠. - List : 순서가 있고 중복이 허용되는 자료구조입니다. ArrayList, Li.. 알고리즘 2016. 10. 14.

• [java] 이진탐색 알고리즘 2016. 10. 11.

• [java] system.in 버퍼리더 표준 입출력 ArrayList numberList = new ArrayList(); try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) { String input = br.readLine(); String[] numStrList = input.split(" "); for (String numStr : numStrList) { numberList.add(Integer.parseInt(numStr)); } } catch (IOException e) { e.printStackTrace(); } String[] words = null; try (BufferedReader br = new BufferedReader(new InputStr.. 알고리즘 2016. 10. 11.

• 알고리즘 하나씩.. 정리 어떤걸 정리하냐면 .. c++ , java 를 기준으로 프림알고리즘, 다익스트라 등등 탐색, 정렬, 이진탐색 등등 두 언어에 대해서 사용할 수 있는.. 템플릿을 만들어두자. 기본변수, 클래스용도로 바로 사용가능하게 그러면 이론도 알고있어야 되겟지 간단한 사용법도 적어두고 도구를 만든다고 생각하자 알고리즘 2016. 10. 7.