[더블릿] 줄세우기 알고리즘(Koi_Align)
줄세우기 알고리즘 해결방법은 다음과 같다. 줄을 세울때 맨 앞과 맨뒤로만 보낼수 있기 때문에, 순서대로 읽어 가면서 정렬이 되어 있는 상태의 숫자는 옮기지 않아도 된다. 정렬이 되어 있지 않은 데이터중 1은 맨앞으로 옮기고, 나머지는 순서대로 맨뒤로 옮기면 자동으로 정렬이 되게 된다. 5, 2, 4, 1, 3의 경우 2, 3은 순서대로 정렬이 되기 때문에 이를 제외한 나머지 값을 옮기게 되므로 5-2 = 3으로 3번 움직여야 한다. 5, 2, 3, 4, 7, 1, 6의 경우 2, 3, 4는 순서대로 정렬 되기 때문에 이를 제외한 나머지 값을 옮기게 되므로 7-3 = 4로 4번 움직여야 한다. 이를 처리하는 코드는 다음과 같다.
2016. 6. 27.
[스크랩] 최대 연속 부분 구간 합 문제를 푸는 알고리즘
아래의 예제는 '프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략' 이라는 책의 미리보기에서 확인할 수 있는 내용이다. 이를 통해 효율적인 알고리즘을 구성하면 수행시간이 얼마나 짧아 질 수 있는 가를 확인할 수 있다. { -7, 4, -3, 6, 3, -8, 3, 4 } 에서 최대의 합을 갖는 구간을 찾아서, 최대의 합을 출력하는 문제이다. 책의 예제를 Java 로 수정하면 아래와 같다. 알고리즘 구성에 따라 for 문을 한번만 사용하고서 답을 찾을 수도 있다. 이렇게 효율적인 알고리즘을 구성하는 것은 무엇보다 중요하다. package algorithm; public class EfficientMaxSum { static int[] array = { -7, 4, -3, 6, 3, -8, 3, 4 }; ..
2016. 6. 27.
[JAVA] 순열(Permutation) 만들기
순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산을 말한다. 1, 2, 3 이라는 숫자의 집합이 있을 때, 다음과 같이 뒤섞는 연산이다. 1,2,3 1,3,2 2,1,3 2,3,1 3,2,1 3,1,2 자바에서는 재귀연산을 이용해 해결할 수 있다. 기준점(pivot)이 되는 배열의 인덱스를 제공하면, 해당 인덱스의 뒤쪽에 있는 값들과 위치를 변경후 기준점을 다음의 위치로 옮겨 다시 호출하는 순서로 진행한다. 아래와 같이 배열을 이용하는 방법과 문자열을 이용하는 방법이 있다. * 순열은 문자열의 길이이 따라 n! 로 시간이 걸리게 된다. 문자열의 길이가 20, 30 개가 된다면 시간이 굉장히 오래 걸리게 된다. http://gorakgarak.tistory.com/522 http://stacko..
2016. 6. 13.
[알고리즘] 시간 복잡도
- 프로그램을 실행시켜 완료하는데 걸리는 시간 - 알고리즘의 일반적인 시간 복잡도는 명령어의 실행 횟수를 고려한다. n for 문을 반복한 횟수, 일반 연산을 처리한 횟수 등의 합에서 상수는 제외하고 최고차항만 생각 시간 이름 bit 별 처리 시간 1 상수형 1, 1, 1, 1, 1, 1 log n 로그형 0, 1, 2, 3, 4, 5 n 선형 1, 2, 4, 8, 16, 32 n log n 선형 로그형 0, 2, 8, 24, 64, 160 n^2 평방형 1, 4, 16, 64, 256, 1024 2^n 지수형 2, 4, 16, 256 n! 계승형 1, 2, 24, 40326 - 로그형 < 선형 < 선형 로그형 < 평방형 순으로 갈수록 복잡해진다. - 빅오[O(N)]: 알고리즘 실행시간의 상한을 나타내는..
2015. 5. 26.