전체 글

듣보잡 - 1764번

풀이 방법 contains의 시간복잡도가 list보다 set이 좋아서 먼저 hashset에 듣도 못한 사람을 넣어주고 보도 못한 사람을 contains으로 확인 후 있으면 list에 넣어주었다. 출력할 때는 sort를 이용해서 사전순으로 정렬 후 출력했다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringToken..

평범한 배낭 - 12865번

풀이 방법 이번 다이나믹 프로그래밍 문제에선 배낭안에 물건이 한번씩만 들어간다는 것이 중요한 조건이였다. 순서대로 넣어서 최댓값을 찾으려고 하니 중복으로 들어가게 되었다. 반복문을 반대로 돌려서 한번씩만 들어가도록 했다. 내 코드 package com.company; import java.io.*; import java.util.*; 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());..

징검다리 건너기 - 21317번

풀이 방법 다이나믹 프로그래밍을 사용해서 풀이했다. 중요한 게 매우 큰 점프를 한번만 사용할 수 있다는 것이다. 그래서 매우 큰 점프를 사용할 수 있는 모든 경우의 수에 넣어주었다. 나머지는 DP의 Bottom-Up 방식으로 풀이하면 된다. 내 코드 package com.company; import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String..

스티커 - 9465번

풀이 방법 DP의 Bottom-Up 방식을 이용해서 풀이했다. 맨앞의 스티커 두개를 먼저 넣어주고 다음 스티커부터 대각선방향으로 더한 값과 서로 변을 공유하는 스티커 중 더 큰값을 찾아주었다. 내 코드 package com.company; import java.io.*; import java.util.Arrays; 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 StringTo..

다이나믹 프로그래밍

다이나믹 프로그래밍(DP) 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메로리 영역에 저장 Top-down Bottom-up 다음 조건을 만족할 때 사용가능 최적 부분 구조 큰문제를작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 중복되는 부분 문제 동일한 작은 문제를 반복적으로 해결해야 한다. 예) 피보나치 수열 Top-down으로 구현한 피보나치 (재귀) import java.util.*; public class Main { // 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 배열 초기화 public static long[] d = new long[100]; // 피보나치 함수(Fib..

좋은 수열 - 2661번

풀이 방법 DFS에서 조건을 걸어 백트래킹으로 풀이했다. 먼저 좋은 수열인지 아닌지 판단하는 check 함수를 작성해주었다. 가장 작은 수를 나타내는 수열을 찾기 위해 DFS에서 1,2,3 순서대로 확인해 주었다. 길이가 N과 같게 되면 find 를 true 로 해줘서 return 하는 것으로 구현했다. 내 코드 package com.company; import java.io.*; public class Main { static int N; static Boolean find = false; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader..

말이 되고픈 원숭이 - 1600번

풀이 방법 BFS를 이용해서 최단경로를 구하는 방법을 이용했다. 이동할 수 있는 동작마다 if문을 이용해서 우선순위 큐에 넣어주었다. 여기서 방문을 체크하는 visited를 조심해야 했다. 그냥 테이블과 동일하게 visited를 구현하게 되면 말처럼 움직이는 동작과 그냥 인접한 칸으로 움직이는 동작을 구분하지 않게 된다. 그래서 말처럼 움직이는 동작을 한 횟수별로 따로 visited 테이블을 만들어주어야 한다. 나머지는 기본 BFS 동일하게 풀이하면 된다. 내 코드 package com.company; import java.io.*; import java.util.*; class Node implements Comparable { private int x; private int y; private int..

뒤집기 II - 1455번

풀이 방법 a, b칸을 뒤집으면 하위 모든 칸들이 뒤집히기 때문에 맨 위에서부터 확인해서 뒤집어 주었다. 세로와 가로 둘다 줄여 나가는것이 아닌 한쪽만 기준으로 잡고 줄여나가도 된다. 내 코드 package com.company; import java.io.*; import java.util.*; 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.pars..

알바생 강호 - 1758번

풀이 방법 최대로 팁을 받기 위해서는 내림차순으로 정렬해서 더해주면 된다. tip의 타입을 int가 아닌 long으로 선언해주는 것만 주의하면 된다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); Integer array[] = new Integer[N]; Long tip = 0L; for (i..

그리디 알고리즘

그리디 알고리즘 현재 상황에서 지긤 당장 좋은 것만 고르는 방법 최소한의 아디디어를 떠올릴수 있는 능력을 요구한다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 해야한다. 거스름돈 문제 일반적인 상황에서는 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 코딩테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제된다. 거스름돈 문제 코드 public class Main { public static void main(String[] args) { int n = 1260; int cnt = 0; int[] coinTypes = {500, 100, 50, 10}; for (int i = 0; i ..