자두의 데브로그

https://www.acmicpc.net/problem/15649 백트래킹 문제였는데, dfs로 풀면 됐다. 사실 dfs 구현하는 것도 까먹어서 다른 사람들 코드를 참고해야했지만.. n은 방문할 노드의 개수, m은 방문하는 깊이에 대한 값이라고 생각하면 됐다.visit 배열을 통해 방문 여부를 체크하여 중복 방문하지 않도록 했다. 내일은.. 다른 사람 코드의 도움 없이 백트래킹 혼자 풀어보자!!! import java.io.*;import java.util.StringTokenizer;public class Main { public static int[] arr; public static boolean[] visit; public static StringBuilder sb = new S..

https://www.acmicpc.net/problem/2164 [문제 이해]문제 그대로 카드가 순서대로 있을 때 하나의 카드가 남을 때까지 가장 위의 카드는 버리고, 두 번째 카드는 가장 아래에 있는 카드 밑으로 옮기면서 마지막으로 남은 카드의 숫자를 출력하면 되는 문제였다. [문제 풀이]deque를 사용해서 문제를 풀어봤다면 어렵지 않게 풀 수 있는 문제였다. 먼저 입력 받은 숫자까지의 카드를 deque에 저장하기 위해 offerLast()함수를 사용한다. 이후로는 규칙에 맞게 반복문을 돌리되, deque 내의 원소의 개수가 1개보다 많을 때까지만 돌리면 된다. 가장 앞의 카드를 버리기 위해서 removeFirst()함수를 사용하고 한 번 더 두 번째 카드를 뒤로 보내기 위해 앞에서 removeFi..

https://www.acmicpc.net/problem/1003 [문제 이해]피보나치는 어떻게 구현하는지 알고 있어서 쉽게 재귀로 구현하고 끝내려고 했으나 실버 3인 이유가 있었구나.. 그냥 재귀 함수로 0과 1의 개수를 구하는 전역 변수를 사용하는 것이 아니라 dp를 사용하여 시간초과가 나지 않도록 구현하는 것이 중요한 문제였다.  [문제 풀이]처음 풀었을 때는import java.io.*;import java.sql.Array;import java.util.*;public class Main { public static int sum_zero = 0; public static int sum_one = 0; public static void main(String[] args) thro..

https://www.acmicpc.net/problem/1764 [문제 이해]듣도 못한 사람의 수 N, 보도 못한 사람의 수 M을 각각 입력 받고 String 배열 N과 M에 모두 속하는 사람의 수와 이름을 찾아서 출력하면 되는 문제였다.  [문제 풀이]N만큼의 크기를 갖는 ArrayList와 M만큼의 크기를 갖는 ArrayList를 각각 만들어서 ArrayList에 있는 contains() 함수를 사용해서 함수 내에 있는 원소를 비교하면 될 줄 알았는데 시간 초과가 났다.. 찾아보니 HashSet의 contains() 함수를 사용해야 시간초과가 안난다고 해서 HashSet을 사용해서 문제를 풀었다. HashSet의 contains() = 시간복잡도 : O(1)ArrayList의 contains() =..

https://www.acmicpc.net/problem/2798 [문제 이해]브루트포스 문제임을 알면 쉽게 풀 수 있는데 브루트포스인지 아닌지 스스로 판별을 하기도 전에 문제 유형을 봐버려서 금방 해결 방법을 생각해냈다. 3장의 카드만 뽑는데 모든 경우에 대해서 다 탐색해서 가장 목표한 수에는 가깝지만 넘지는 않는 수를 만드는 방법을 찾으면 되는 문제였다. [문제 풀이]문제를 풀면서 굳이 3중 for문을 탈출하는 부분을 구현하겠다고 break 걸었다가 한 번 틀렸는데 이 부분을 제외하니까 바로 정답 처리가 됐다. 가장 첫 번째로 탐색하는 건(i) 처음부터 마지막에서 2번째까지만 탐색해도 되므로 for문에서 n-3까지만 돌면 됐고(0~n-3) 같은 원리로 두 번째 카드(j)는 n-1(i+1~n-2), 마..

https://www.acmicpc.net/problem/1010 [문제 이해]동적 프로그래밍 문제였다. nCr 을 생각해내면 풀 수 있는 문제였는데 완전 잊고 있었다,, 재귀로도 풀 수 있고 반복문으로도 풀 수 있는데 재귀보다는 반복문을 사용해서 푸는 방식을 선택했다. [문제 풀이]이차원 배열로 나타내면1C0 1C12C0 2C1 2C23C0 3C1 3C2 3C3...이런 느낌이니까 가장 앞줄 즉, arr[i][0]과 가장 마지막 즉, arr[i][i]의 값은 1로 넣어주고 나머지 값은 [i-1][j] + [i-1][j-1] 값을 저장해주면 된다. 이를 통해 입력된 값 중 큰 값을 행의 인덱스로 지정해서 출력하면 된다.import java.io.*;import java.util.*;public class..

1. 10870번 피보나치 수 5 https://www.acmicpc.net/problem/10870 [문제 이해]피보나치 수를 어떻게 동적 프로그래밍으로 구현하는지 알고만 있다면 어렵지 않은 문제였다. 배열을 N보다 하나 크게 만들어서 0은 무시하고 인덱스 1번부터 원하는 값을 넣을 수 있도록 구현하였다. [문제 풀이]1 이나 2 면 1을 넣고 다른 값이면 i-1과 i-2번째 인덱스의 값을 더해서 넣을 수 있도록 구현했다. import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buffered..

체력 이슈로 3일차는 매우 난이도가 낮은 문제들로 ,, 한 번에 풀이해보겠습니다~ 1. [자바] 10807번 개수 세기 (https://www.acmicpc.net/problem/10807) [문제 이해]배열에 입력 받은 값을 저장하고 가장 마지막에 입력 받은 정수가 배열 안에 몇 개나 있는지 찾는 문제였다. [문제 풀이]arr에 차례로 저장하고 비교해서 출력만 하면 되는 간단한 문제였다!  import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStr..

https://www.acmicpc.net/problem/28278 [문제 이해]덱,,,을 사용해서 쉽게 풀어보려고 했더니 또또 시간초과나고 난리남.. 흠 이유는 모르겠으나 intelliJ에서 돌리면 숫자 명령어에 대해서 출력이 바로 나오지 않는데 도대체 왜 맞은 건지 모르겠다며,, 무튼 문제 자체는 어렵지 않았으나 내일은 BufferedWriter를 진짜 마스터해야겠다고 느꼈다. 문제를 이해하지 못해서 못 푼 게 아니라 입출력에서 시간초과 뜨는 건 너무 하잖아~ [문제 풀이]1이 들어올 때만 약간 다른데 StringTokenizer 이용해서 한 줄에 들어오는 다음 숫자 가져다가 stack에 넣으면 되는 부분이라 크게 어려운 건 없었다. import java.io.*;import java.util.*;p..