개발 무지렁이

분할정복 알고리즘인 병합(Merge) 정렬 일단 반으로 계속 나누고 나중에 합치면서 정렬하자 이미 정렬이 되어있는 상태에서 새롭게 정렬된 상태를 만드는 것이다. 🕑 시간복잡도: O(N * log(2)N) [ 반절씩 나누니까 너비가 N이면 높이는 log(2)N이다. ] [ 높이만큼 내려가면 전체 너비만큼의 숫자를 정렬할 수 있다. ] 병합(Merge) 정렬 코드 구현 import java.util.*; import java.io.*; class Main { static int[] A; static int[] sorted; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new I..

선택(Select) 정렬 가장 작은(큰) 것을 선택해서 맨 앞으로 보내자 🕑 시간복잡도: O(N^2) [ 비교연산횟수: N + N-1 + N-2 + ... + 1 = (N+1)N/2번 ] 선택(Select) 정렬 코드 구현 import java.util.*; class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String str = scanner.next(); int[] A = new int[str.length()]; for(int i = 0; i < str.length(); i++) { A[i] = Integer.parseInt(str.substring(i, i+1)); } for(i..

삽입(Insert) 정렬 각 숫자를 적절한 위치에 삽입해보자 적절한 위치의 왼쪽원소들은 이미 정렬되어있다고 가정 자신이 왼쪽원소보다 크다면 그 곳이 적절한 위치이다.(오름차순일 때) 🕑 시간복잡도: O(N^2) [ 비교연산횟수: N-1 + N-2 + N-3 + ... + 1 = (N^2)/2번 ] [ 도중에 왼쪽원소보다 크면 멈출 수 있어서 버블정렬보다 빠르다 ] 삽입(Insert) 정렬 코드 구현 1. 앞쪽부터 범위를 늘려간다. 2. 범위내 뒤에서부터 왼쪽보다 큰 지를 검사한다. - 크면 멈춘다. - 작으면 swap 🎯 인출시간이 짧은 사람이 먼저 인출할 수 있도록 하면 기다리는 시간이 짧아진다. import java.util.*; class Main { public static void main(St..

버블(Bubble) 정렬 이웃한 값을 비교해서 더 작은값을 앞으로 보내자 (한번 돌면 가장 큰값이 가장 뒤로 오게 된다, 뒤부터 정렬) 🕑 시간복잡도: O(N^2) [비교연산 횟수: N-1 + N-2 + N-3 + ... + 1 = (N^2)/2번] 버블(Bubble) 정렬 코드 구현 1. 루프loop를 돌면서 이웃한 값 간의 swap연산으로 정렬한다. 🎯 N이 1000보다 작음으로 시간복잡도가 O(N^2)인 알고리즘을 써도 풀 수 있다. (1억번의 연산 = 1초) import java.util.*; class Main { public static void main(String[] args) { Scanner scannner = new Scanner(System.in); int N = scanner.ne..

그래프의 모든 노드를 탐색하는 BFS(Breadth First Search) 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 시작노드에서 출발하여 레벨 기준으로 자기 레벨을 다 탐색하고 내려가는 과정을 반복하는 것을 &#39; 넓이우선탐색(BFS) &#39;라고 한다. ** (시작노드 기준으로 가까운 노드를 먼저, 최단경로를 보장) ** 🕑 시간복잡도: O(V+E) (V:정점수, E:간선수) [모든 정점을 한 번씩 방문하고, 그러기 위해 모든 간선을 한 번씩 검사했으니] BFS와 큐 BFS는 큐(Queue)로 구현하며, 큐(Queue)란 먼저 들어온게 먼저 빠지는 형태의 자료구조(FIFO)를 말한다 Queue queue = new ArrayDeque(); BFS 코드 구현 ⚠️ 한번 방문한 노드..

그래프의 모든 노드를 탐색하는 DFS(Depth First Search) 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 시작노드에서 출발하여 리프노드까지 내려가고 부모에게 올라가, 다시 리프노드까지 내려가는 것을 반복하는 과정을 ' 깊이우선탐색(DFS) '라고 한다. 🕑 시간복잡도: O(V + E) (V: 노드 수, E: 간선 수) [모든 정점을 한 번씩 방문하고, 그러기 위해 모든 간선을 한 번씩 검사했으니] DFS와 재귀함수 DFS는 재귀함수로 구현하며, 재귀함수란 &#39;자기 자신&#39;을 Function call(함수 호출)하여 동작하는 방식을 말한다. (종료조건과 재귀적확장이 있어야 한다.)DFS 코드 구현, 백준 1260 DFS 🪅 에지리스트를 인접리스트로 구현할 수 있는가 🪅 ..