728x90 알고리즘42 [백준10816] 숫자 카드 2[java] 이 문제는 단순한 이분탐색으로는 풀 수 없는 문제였다. 여러가지로 시도해봤지만 결국 시간초과 오류.... 거기다가 println을 사용해도 시간초과가 떴다. 결국 모든 데이터를 배열에 넣고 찾고 싶은 값 num의 범위를 찾아냈다. lower와 upper메소드를 만들어 마지막에 upper의 값과 lower의 값을 빼는 것이다. 그리고 출력은 BufferedWriter를 이용하여 마무리 했다. 코드 package baekjoon; import java.io.*; import java.util.*; public class num_card2 { static int[] arr1; public static void main(String[] args) throws IOException { BufferedReader .. 2021. 5. 4. 순환의 개념과 기본예제 3 순환 알고리즘의 설계 - 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함 - 모든 case는 결국 base case로 수렴해야 함 * 가능하다면 암시적 매개변수를 명시적 매개변수로 바꾸어라. -> 순환 알고리즘을 만들때 중요 - data배열을 0~n-1까지 n개를 탐색함 -> n-1은 n을 통해 명시적으로 표현되어있다고 할 수 있지만, 0은 암시적으로 표현되어 있다고 할 수 있다. - 배열의 시작점과 끝을 begin과 end로 명시적으로 표현함 2021. 5. 1. 순환의 개념과 기본예제 2 순환 - 수학함수 뿐만 아니라 다른 문제들도 해결가능 *문자열의 길이 계산 - 첫글자를 제거한 나머지 문자열의 길이를 잰다 *문자열을 뒤집어 프린트 - 첫글자를 자르고 순환함수를 호출한다. - 돌아올때 출력하면 문자열의 끝부터 출력한다. *배열의 합 구하기 - 배열 data에서 하나씩 꺼내서 더해준다. *순환과 반복문 - 모든 순환함수는 반복문으로 변경 가능 - 반대도 가능함 -> 반복문은 순환으로 표현 가능 - 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것이 가능함 - 하지만 함수 호출에 따른 오버헤드가 있음 2021. 5. 1. 순환의 개념과 기본 예제 1 순환이란 - 자기 자신을 호출하는 함수 순환함수를 잘못 만들게 되면 무한루프에 빠지게 되는 경우가 생긴다. 이런 경우를 방지하기 위해서 조건을 추가해줘야 한다. 1~n까지의 합을 순환함수를 이용해 구하는 원리 순환의 대표적인 예시1 : n! 0! = 1 n! = n*(n-1)! n>0 순환의 대표적인 예시2 : 피보나치 f0 = 0 f1 = 1 fn = f(n-1) + f(n-2) n>1 2021. 5. 1. [백준 1504] 특정한 최단 경로[java] dijkstra알고리즘을 조금만 응용한다면 쉽게 풀수 있는 문제였다. 하지만 그 조금의 응용이 어려워 다른 사람이 푼 방법을 찾아봤다... 우선 무조건 거쳐서 가야하는 노드들을 v1,v2라고 한다면 1 -> v1 -> v2 -> N 1 -> v2 -> v1 -> N 이렇게 거쳐가면 된다. 따라서 결과 1 += dijkstra(1,v1) 결과 1 += dijkstra(v1,v2) 결과 1 += dijkstra(v2,N) ------------------------------ 결과 2 += dijkstra(1,v2) 결과 2 += dijkstra(v2,v1) 결과 2 += dijkstra(v1,N) 후에 결과 1과 결과 2중 더 작은 값을 출력해주면 된다. 코드 package baekjoon; import .. 2021. 4. 8. [백준1753] 최단경로[java] dijkstra알고리즘을 이용하여 문제를 풀었다. 처음에는 시작점을 기준으로 가중치를 모두 -1로 만든다. 이후 연결된 값들을 큐에 넣고 가중치를 바꿔준다. 이러는 과정에서 직접 연결된 가중치보다 돌아서 가는 가중치가 더 낮다면 돌아가는 것으로 바꿔준다. 코드 package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.StringTokenizer; public class shortest.. 2021. 4. 7. 이전 1 2 3 4 5 ··· 7 다음 728x90
