알고리즘4 코테 시간 복잡도 계산방법 n으로 구성된 시간복잡도 O( )를 계산했을 때의 값이 1억 정도면 1초 정도의 시간이 걸린다고 한다. 1억에 1초 물론 이 값이 완전 정확한 것은 아니기에, 문제와 알고리즘에 따라서 달라질 수 있는 것이지만 보통 자신의 알고리즘이 몇 초안에 끝날지를 계산하기 위해서는 1억 정도의 값이 1초라는 것을 알면 계산이 쉽다! 예를 들어 N의 최대 값이 10만일 때,(10만 ,100만, 1000만, 억) 1. O(N)의 시간복잡도일 경우에 값이 10만 정도이니, 1/1000초 정도가 걸릴 것이라 예상 2. O(N^2)의 시간복잡도의 경우에 값은 100억이므로, 100초 정도가 걸릴 것이라고 예상 이 경우 문제 제한 시간이 1초라면 O(N^2)의 시간복잡도를 갖는 알고리즘으로 문제를 풀 수 없다는 것을 미리 파악.. 2023. 9. 8. 백준 11724 [Java] DFS 활용 다음 문제는 DFS를 활용한 문제이다. 문제[제한시간3초] 방향 없는 그래프가 주어졌을 때 연결 요소의 개수를 구하는 프로그램을 작성하시오. 입력 1번째 줄에 노드의 개수 N(1 2023. 9. 8. BFS 완전탐색 알고리즘 [java] 완전탐색 알고리즘? 모든 경우의 수를 다 체크해서 정답을 찾는 방법이다. Brute Force라고도 한다. 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실한 기초적인 방법이다. 예시 4자리 암호로 구성된 자물쇠를 풀려고 한다. 이 자물쇠가 고장난 것이 아니라면 가장 확실한 암호 찾는 방법은? 0000부터 9999까지 모두 시도해 보는 것이다. (최대 10,000번의 시도로 해결가능) 하지만 문제해결 알고리즘으로 BFS를 사용할 때는 2가지 규칙을 적용한다. 1. 사용된 알고리즘이 적절한가? (알고리즘 통해 문제 해결할 수 있는지) 2. 효율적으로 동작하는가? 1번은 대부분 통과하지만, 2번 통과가 어렵다... 완전 탐색 기법 활용 방법 고려해야할 사항 3가지 1. 해결하고자 .. 2023. 9. 8. [JAVA] 버블정렬 버블 정렬은 시간 복잡도 O(n^2)를 갖는다. 논리 구조상 시간이 오래걸리지만 구현 하는데 있어서 쉽다는 장점을 갖는다 백준 2750 난이도 브론즈 문제 N개의 수가 주어졌을 때 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 슈도 코드. N 정렬할 수 개수 A 정렬할 배열 선언 for(i: 0~N-1) { for(j: 0~N-1-i){ 현재 A배열의 값보다 1칸 오른쪽 배열의 값이 더 작으면 두 수 바꾸기(swap)이용 } } A 배열 출력 구현 코드. import java.util.Scanner; public class P2750{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextI.. 2023. 8. 16. 이전 1 다음