알고리즘 분석어떤 응용 프로그램에 어느 클래스가 더 좋을지 결정하는 한 가지 방법은 둘 다 시도해보고 각각 얼마나 걸리는지 알아보는 것인데, 이러한 접근법을 프로파일링(profiling)이라고 하는데 여기에는 몇 가지 문제점이 존재한다. 알고리즘을 비교하려면 사전에 그것을 모두 구현해봐야 한다. 결과는 사용하는 컴퓨터 성능에 의존한다. 결과는 문제 크기나 입력으로 사용하는 데이터에 의존하기도 한다. 알고리즘 분석(analysis of algorithm)을 사용하여 이러한 문제점을 해결할 수 있다. 알고리즘 분석은 그것을 구현하지 않고도 알고리즘을 비교할 수있도록 하는데 몇 가지 가정을 해야만 한다. 알고리즘을 이루는 더하기와 곱하기, 숫자 비교 등의 기본 연산을 식별한다. 그리고 각 알고리즘에 필요한 연..
프로그래밍 노트/알고리즘
LinkedList에서 빠른포인터와 느린포인터를 사용하여서 중간노드를 구하는 방법느린포인터가 한 칸 갈때, 빠른포인터는 두 칸 증가한다.빠른포인터가 마지막에 다달았을때, 느린포인터가 가르키는 위치가 중간 노드 우선, 테스트에 필요한 구현체 구현 - 간단한 Node 클래스12345678public class Node { int val; Node next; Node(int val){ this.val = val; }} cs- 1~7까지의 linkedList 생성123456789101112131415161718public static Node makeLinkedList(){ Node head = new Node(1); Node node1 = new Node(2); Node node2 = new Node(3); ..
#10String이 주어지면, 중복된 char가 없는 가장 긴 서브스트링 (substring)의 길이를 찾으시오. // Input : "aabccbc"// output : 3("abc") 문자 list를 만든 후, for문을 돌며 문자를 추가한다. 같은 문자가 포함되어 있을시 list length를 구하여 maxLength보다 크면 maxLength교체 크지 않으면 현 maxLength를 유지한다. 1234567891011121314public static int solution(String str) { int maxLength = 0; List list = new ArrayList(); for(int i=0; i list.size() ? maxLength : list.size(); list.clear(..
팩토리얼(Factorial) 구하기재귀적 방법을 사용하지 않는 팩토리얼 구현을 작성하라. Factorial(n) = 1 * Factorial(n-1);재귀 팩토리얼12345public long recursiveFactorial(int n) { if(n
면접 단골문제인 피보나치(fibonacci) 구현 1에서 n까지의 피보나치 수열을 반환하는 메서드를 작성하라. 123456789101112131415161718192021222324252627282930313233public static List fibonacci(int n){ if(n
FizzBuzz문제 구현하기 1에서 n까지의 숫자를 출력하되 3의 배수는 Fizz라는 문자열을 출력하고, 5의 배수는 Buzz라는 문자열을 출력하고 15의 배수는 FizzBuzz라는 문자열을 출력하는 알고리즘을 작성하라. 12345678910111213141516public static List fizzBuzz(final int n){ List result = new ArrayList(n); for(int i=0; i
이진탐색(Binary Search)효율적인 검색(탐색)기법인 이진탐색에 대해 알아보겠습니다.탐색시 리스트가 정렬되어 있지 않으면 리스트 검색 시 주어진 값을 찾기위해 모두를 찾아봐야한다는 단점이 있습니다. 하지만 정렬된 리스트가 있거나 검색전에 정렬을 수행한 경우 이진 탐색(binary Search)을 사용하면 매우 효과적으로 원하는 값을 얻을 수 있습니다. => 이진탐색은 원소를 일일이 비교하지 않고도 주어진 원소를 찾을 수 있으며, 백만 개의 원소가 있어도 20번 미만의 비교로 주어진 원소를 찾을 수 있습니다. O(logn) 12345678910111213141516171819202122package algorithm; import java.util.List; public class BinarySea..
병합정렬, 합병정렬(Merge Sort)분할정복(divide-and-conquer)의 한 종류인 합병정렬에 대해 알아보겠습니다.컨셉은 리스트를 두개로 나누고 각 하위 리스트를 정렬 후 하나로 합치는 방법입니다.설명보다 그림을 보는게 이해가 더 빠를 듯 싶어서 이해가 쉽게될 만한 그림을 가져왔습니다. (그림 출처 : http://blog.naver.com/k97b1114/140163896337) 병합 정렬의 성능은 O(nlogn)이고 각각의 병합시간은 O(n)이며 각 재귀 호출은 주어진 리스트 숫자의 절반만큼만 발생합니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647package sort; impo..
#9 정수 배열(int array)이 주어지면 0이 아닌 정수 순서를 유지하며 모든 0을 배열 오른쪽 끝으로 옮기시오. 단, 시간복잡도는 O(n), 공간복잡도는 O(1)여야 합니다. 예제)Input: [0, 5, 0, 3, -1]Output: [5, 3, -1, 0, 0] Input: [3, 0, 3]Output: [3, 3, 0] 0을 오른쪽으로 옮기는 문제이다. 일단, 0이 아닌 수가 들어갈 index를 저장해 둔다.(배열 첫번째인 0부터 시작) 그 후 for문을 돌면서 0이 아닌 숫자가 나오면 해당 index의 숫자와 0이 아닌 숫자와 교환 후 index를 증가시킨다.(숫자가 0일 때는 index를 증가시키지 않아, index가 0의 위치를 가리키게 한다.) 1234567891011121314151..
#8 정수 배열(int array)이 주어지면 두번째로 큰 값을 프린트하시오. 예제)Input: [10, 5, 4, 3, -1]Output: 5 Input: [3, 3, 3]Output: Does not exist. for문을 한번 사용해서 풀어야 한다. 2번 째로 큰 수가 존재하지 않는 경우는 2가지가 존재한다. 원소가 2개가 안될 경우와 모든 원소가 같을 경우이다. 이 부분만 잘 처리를 해주면 쉽게 풀어갈 수 있다. 1234567891011121314151617181920212223public static int solution(int[] array) { if(array.length
