문제풀이

백준 19947. 투자의 귀재 배주형 (JAVA) (DP)

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[] dp ; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int H = Integer.parseInt(st.nextToken()); ..

백준 11047. 동전 0 (JAVA)

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int K = Integer.pa..

백준 15649. N과 M(1)(JAVA)

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[] arr; static boolean[] visit; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new Str..

백준 9461. 파도반 수열(JAVA)

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static Long[] dp = new Long[101]; public static void main(String[] arge) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int test_case = Integer.parseInt(br.readLine()); dp[1] = 1L; dp[2] = 1L; dp[3..

백준 1003. 피보나치 함수(JAVA)

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static Integer[][] dp = new Integer[41][2]; public static void main(String[] arge) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int test_case = Integer.parseInt(br.readLine()); dp[0][0] = 1; dp[0][1] = 0; dp[1][0] = 0; dp[1][1] = 1; fo..

시간 복잡도(Time Complexity)

최근에 정보처리기사 필기를 준비하면서 정렬에 관한 문제가 나올 때마다 빠짐 없이 나오는 것이 있는데 바로 '시간 복잡도'이다. 필기 준비할 때는 답을 외우는 게 빠르기 때문에 지나쳤지만 최근에 정렬에 관한 알고리즘을 공부하면서 시간 복잡도에 대해 알아보고 싶어서 정리를 시작하게 됐다. 시간 복잡도란? -> 문제를 해결하는데 걸리는 시간과 입력함수의 관계를 나타내는 것이다. 이름에서부터 그 의미가 느껴지지만 면접에서 물어볼 날이 생기지 않을까라는 기대를 가지고 사전적 정의를 써봤다. 좀 더 쉽게 말하면 문제 해결을 하는데 시간이 얼마나 걸려?를 나타난 것이라고 보면 된다. 시간이 오래걸리면 복잡하다는 것을 다 알다시피 시간 복잡도가 크면 느린 알고리즘이고 시간 복잡도가 작으면 빠른 알고리즘이다. 그리고 시..

백준 2231. 분해합 (JAVA)

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] arge) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int result = 0; for(int i = 0 ; i < N ;i++) { int num = find(i); // 분해합 구함.... if(num == N) { // 분해합이 N과 같으면 r..

Counting Sort (계수 정렬)

정렬에는 계수 정렬뿐 아니라 다른 정렬도 많지만 최근에 백준에서 정렬에 대한 문제를 풀다가 'Counting Sort'를 알게 되어 계수 정렬에 대해 정리를 하고 싶어서 이 글을 쓰게 되었다. Counting Sort이란 ? 카운팅 정렬은 숫자끼리 비교하는 것이 아닌 각 항목의 개수를 세어 저장해두고 그에 따라서 적절한 위치에 정렬하는 효율적인 알고리즘이다. 시간 복잡도는 𝚶(𝑛)이며 매우 좋은 성능을 보여준다.( 시간 복잡도​에 대해서 따로 공부해서 포스팅 하겠다.) 하지만 좋은 성능을 가진 만큼 제한 사항이 존재한다. 정수나 정수로 표현할 수 있는 자료에 한해서 적용 가능. 각 항목을 카운트하기 위한 충분한 공간을 할당하려면 배열 내에서 가장 큰 정수를 알아야 함. 정렬 방법 arr 배열에 들어있는 ..

백준 2941. 크로아티아 알파벳 (JAVA)

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] arge) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = br.readLine(); int cnt = 0; char ch ; for(int i = 0 ; i < str.length(); i++) { ch = str.charAt(i); if(ch == 'c') { if(i < str.length() -1)..

백준 10989. 수 정렬하기 3(JAVA)

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] arge) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int num = Integer.parseInt(br.readLine()); int[] arr = new int[num]; // 입력받을 배열 int[] counting = new int[10001]..