알고리즘
-
[Codility] FrogJmp 100점알고리즘 2019. 3. 23. 23:29
문제출처 : https://app.codility.com/programmers/lessons/3-time_complexity/frog_jmp/ 문제요약 : 개구리가 몇번을 뛰어야 해당지역으로 갈수있냐! 라는 문제다X : 개구리의 위치Y : 도착위치D : 개구리의 점프력(?) 이다 예를들어 개구리의 위치가 10이고, 도착해야 할 거리는 85, 개구리의 점프력은 30이면현재 위치(10)에서 도착지까지(85) 부족한 거리는 75다개구리가 1번 점프(30)하면 현재위치(10) + (30) = 40이다2번 점프하면? 40+30=70인 것이다. [100점]12행 Y-X/D를 통해서 점프해서 갈 수 있는 값을 구했다.그리고 13행에서는 Y-X%D의 몫이 있다면 1을 증가시켰다.else는 딱 나눴을때 몫이 없다면 점프..
-
[Codility] BinaryGap 100점알고리즘 2019. 3. 14. 22:28
문제출처 : https://app.codility.com/programmers/lessons/1-iterations/binary_gap/ 문제 요약 : 입력받은 숫자를 이진수로 변환후, 1에 1까지의 0의 개수를 각각 구한뒤 가장 큰 0의 개수를 반환해라.ex) 입력: 1001 출력: 2 입력: 1010001 출력: 3 [100점] 입력받은 숫자를 Integer클래스로 이진수 문자열로 바꾼뒤, 숫자로된 문자열을 배열에 넣었다. 배열에 넣은 후 반복문을 돌면서 0일때 마다 임시 변수에 카운트값을 증가시켰다. 그다음 1을 만나면 lit에 카운트값을 담았다. 그리고 임시변수값을 초기화해버림. 마지막에는 list에서 가장 큰 값을 반환해버렸다. 1234567891011121314151617181920212223..
-
[Codility] CyclicRotation 87점→100점알고리즘 2019. 3. 3. 16:56
문제출처 : https://app.codility.com/programmers/lessons/2-arrays/cyclic_rotation/ 문제요약 : 입력받은 횟수(K)만큼 배열을 순환시키는 것. 맨뒤의 요소를 뽑아서 앞으로 넣은후 한칸씩 인덱스를 밀어주는 형식 [100점] 문제를 보면 배열의 맨뒤의 요소를 뽑아서 앞으로 넣은 후 그뒤에 요소들을 하나씩 밀어가고있다. ex) 2회전 주어진배열 {1, 2, 3}1회전 {3, 1, 2}2회전 {2, 3, 1} 자료구조를 공부를했다면 쉽게 풀 수 있는 문제다. 바로 선입선출(FIFO)성질을 가진 Que를 선택했다. 조금 아쉬운 점은 Que를 Array로 변환하는 과정이 조금 지저분하다는 생각이 들었다. 충분히 리팩토링 할 코드라고 생각한다. 123456789..
-
[Codility] OddOccurrencesInArray 55점→100점알고리즘 2019. 2. 16. 18:41
문제 출처 : https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/ 문제요약 : 배열요소중에서 짝이 없는 요소의 값을 출력해라 [55점] O(n**2) 처음 접근 방식은 모든배열의 요소를 돌면서 같은 숫자가 있으면 count라는 변수값을 증가 시키고.최종적으로 1개만 있는 경우를 return해주게했다. 결과는 10만건이상의 데이터가 들어왔을때 TimeOut이 발생했다.. ㅎㅎㅎ 심지어 코드도 지저분.. 1234567891011121314151617181920212223242526272829303132package test_java2; import java.util.*; public class Main { public..
-
[알고리즘] 삽입정렬알고리즘 2018. 8. 20. 12:54
12345678910111213141516171819202122232425262728293031323334353637package test_java; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { int[] arr= {4,2,5,6,1,3}; insertSort(arr); for(int result : arr) { System.out.println(result); } } public static int[] insertSort(int[] arr) { for (int i = 1; i = 0 && standard O(n^2)
-
[알고리즘] 선택정렬알고리즘 2018. 8. 20. 12:01
1234567891011121314151617181920212223242526272829303132package test_java; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { int[] arr= {4,2,5,6,1,3}; selectSort(arr); for(int result : arr) { System.out.println(result); } } public static int[] selectSort(int[] arr) { for(int i=0 ; i
-
[알고리즘] 백준알고리즘 - 피보나치수열 2747알고리즘 2018. 8. 12. 19:02
문제 출처: https://www.acmicpc.net/problem/2747 문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 n이 주어진다. n은 45보다 작거나 같은 자연수이다. 출력첫째 줄에 n번째 피보나치 수를 출력한다. 123456789101112131415..