목록알고리즘 (30)
처음부터 차근차근
문제 : https://www.acmicpc.net/problem/1929해당문제는 변수는 1000000까지 될 수 있으나 제한 시간이 2초여서 알고리즘을 사용해야한다. 문제 풀 때 필요한 개념 에라토스테네스의 체고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법.임의의 수 N 까지의 소수를 구하고자 할 때, 2부터 √N (제곱근) 까지 돌며 모든 배수들을 소수에서 제외시키는 방식이다. 2 * 4 = 4 * 2 처럼 모든 약수를 구하기에는 겹치는 부분이 많아 비효율적이다.그래서 주어진 수의 제곱근 까지만 약수를 구하면 효율적으로 소수를 구할 수 있다. 1. 2부터 √N 까지의 배수를 제외시킨다.2. 배수를 구할 때는 자기 자신을 뺀다.3. 제외된 수는 배수를 구하지 않고 넘어간다. 풀이im..
문제 : https://www.acmicpc.net/problem/1978 전체적으로 쉽게 풀 수 있는 문제였다. 문제 분석 : 소수 = 1과 자신만의 숫자를 약수로 가지는 수그러므로 1과 자기자신이 아닐 경우에 나눠서 0이 되면 count를 하지 않는다. 소스package backjoon;import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.StringTokenizer;public class q_1978 { public static void main(St..
문제 : https://www.acmicpc.net/problem/1259 이 문제에서 쓰인 개념StringBuffer, StringBulilder자주 가변하는 문자열 생성할 때 사용하는 클래스.둘의 차이점 : StringBuffer : 멀티스레드 환경에서 성능이 좋음.StringBuilder : 싱글스레드 환경에서 성능이 좋음. StringBuffer 클래스 함수.reverse() : 문자열 순서 거꾸로 나열 소스import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import jav..
문제 : https://www.acmicpc.net/problem/1181 Array.sort(배열)https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html배열 오름차순 정렬 함수Arrays.sort(배열,Comparator.reverseOrder()); // 내림차순 Integer[] intArr = new Integer[] {1,3,2,5,4};Arrays.sort(intArr,new Comparator() { @Override public int compare(Integer a, Integer b) { // a는 앞의 수 b는 뒤의 수 System.out.println(a.compareTo(b)); return a.compare..
Scanner 사용 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); sc.nextInt(); // 한 줄 int로 받음 sc.next(); // 한 단어 string으로 받음(공백 기준 , 개행 무시하고 받음) sc.nextLine(); // 한 줄 string으로 받음(엔터 기준, 개행 까지 받음) } } Buffer 사용 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputS..
시간 복잡도 유형 빅 오메가 : 최선일 때 연산 횟수 빅 세타 : 보통 빅 오 : 최악 --> 코딩 테스트에서의 시간 복잡도는 보통 빅 오를 사용한다. 연산 횟수 계산하는 법 * 제한 시간이 2초라면, 보통 2억번 이하의 연산 횟수로 문제를 해결해야 함 * 버블 정렬 시간 복잡도로 예를 들음 O(n^2) == 최대 연산 횟수^2 이런식으로 계산 했을때 제한 시간이 2초니까 최대 연산 횟수^2가 2억 번 이하면 됨 시간 복잡도 계산 * 상수는 시간복잡도 계산에서 제외 * 가장 많이 중첩된 반복문의 수행 횟수가 시간복잡도임 --> 그래서 2중 for문이 30개여도 시간 복잡도는 2중 for문 1개일 때랑 똑같음
문제 https://www.acmicpc.net/problem/15596 15596번: 정수 N개의 합 C++17, Java 8, Python 3, C11, PyPy3, C99, C++98, C++11, C++14, Go, C99 (Clang), C++98 (Clang), C++11 (Clang), C++14 (Clang), C11 (Clang), C++17 (Clang) www.acmicpc.net 정수 배열의 합을 구하는 문제이다. 함수만 작성하는건데 모르고 입력부터 출력까지 모두 작성해버렸다. 백준 제출 답 public class Test { long sum(int[] a) { long ans = 0; for(int i = 0; i < a.length; i++) { ans += a[i]; } ret..
문제 https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 걷는걸 참 싫어하는 손님이다...ㅋㅋ 계획 테스트 케이스 개수 : test_num 호텔 층 수 : h 호텔 방 수 : w 몇 번째 손님 : n 호텔 방 -> boolean형 2차원 배열 boolean[][] rooms = new boolean[h][w]; ** int형 2차원 배열을 이용해서 만드려고 했으나 int형은 4바이트, boolean형은 1바이트이므로 boolean형을 ..