개발 정리 모음집

이진 탐색이진 탐색은 정렬된 상태의 데이터에서 원하는 값을 찾아내는 알고리즘이다. 데이터의 중앙값과 찾고자 하는 값을 비교한다.이진 탐색은 탐색 대상이 매번 절반으로 줄어들기 때문에 시간 복잡도는 O(logN)이다. 이진 탐색의 동작 원리는 다음과 같다.배열이나 리스트를 정렬한다.배열이나 리스트의 중간 값을 선택한다.중간 값이 목표 값보다 크면 왼쪽 절반을 탐색하고, 중간 값이 목표 값보다 크면 오른쪽 절반을 탐색한다.중간 값과 목표 값이 같을 때까지 탐색한다.예를 들어보자정렬된 배열(arr) : [1, 3, 5, 7, 9, 11, 13]목표 값 : 9먼저 left는 0, right는 6로 시작한다.(시작 인덱스0, 가장 끝 인덱스 6)public class BinarySearchMain { pub..

SWEA 0/1 Knapsack (D 3)// 0/1 Knapsackimport java.util.*;public class Swea3282 { public static void main(String args[]) throws Exception { Scanner sc = new Scanner(System.in); int T; T=sc.nextInt(); for(int test_case = 1; test_case = v) { dp[i][j] = Math.max(dp[i - 1][j - v] + c, dp[i - 1][j]); } // 내가 못 들어감 else { dp[i][j] = dp[i - 1][j]; } } } System.out.pr..

SWEA 햄버거 다이어트 (D 3)package test;import java.util.*;import java.io.FileInputStream;public class Swea5215 { static int[] score; static int[] calory; static int n; static int max; public static void main(String args[]) throws Exception { //System.setIn(new FileInputStream("res/input.txt")); /* 표준입력 System.in 으로부터 스캐너를 만들어 데이터를 읽어옵니다. */ Scanner sc = new Scanner(System.in); int T; T=sc.ne..

백준 가장 긴 증가하는 부분 수열 4 (골드 IV)import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Scanner;// 가장 긴 증가하는 부분 수열 4(골드 4)public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i > list = new ArrayList(); for (int i = 0; i ()); } int[] dp = new int[n];..

0-1 BFS 가중치가 0, 1로 주어진 그래프에서 최단경로를 찾아낼 수 있는 알고리즘 O(V+E)의 시간 복잡도를 가진다.(V : 정점 개수, E : 간선 개수) 1. 시간복잡도 O(V+E)의 시간복잡도를 가지는 이유는 무엇일까? 1️⃣ Queue 대신 Deque 사용 0-1 BFS는 Deque(덱) 자료구조를 사용해서 구현한다. Deque은 Double Ended Queue로 양 방향에서 offer, poll이 가능하다. 가중치가 0인 간선으로 이동할 경우, 해당 정점을 덱의 앞부분에 추가한다. 이는 그 정점을 가능한 한 빨리 다시 탐색하기 위해서이다. 가중치가 1인 간선으로 이동할 경우, 해당 정점을 덱의 뒷부분에 추가한다. 이는 그 정점을 나중에 탐색하도록 한다. 2️⃣ 한 번씩만 처리되는 정점과..

백준 녹색 옷 입은 애가 젤다지? (골드 IV ) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; // 녹색 옷 입은 애가 젤다지?(골드 4) // 다익스트라 public class Main { static int[][] zelda; static boolean[][] visited; static int N; static int cnt = 0; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReade..

백준 N과 M(3) (실버 Ⅲ) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class N과M_3 { static int n; static int m; static StringBuilder sb = new StringBuilder(); static int[] path; public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); Stri..

백준 N과 M(2) (실버 Ⅲ) 1. 가지치기 import java.util.Scanner; public class Main { static int n; static int m; static int[] path = new int[9]; static boolean[] used = new boolean[9]; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); run(0, 0); System.out.println(sb); } private stati..