본문 바로가기

Tech/Problem Solving

[백준 2661] 좋은 수열 (Java) https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 접근 방법 백트래킹 문제였지만 백트래킹 자체는 크게 어렵지 않았다. 만들어 낸 수열이 좋은 수열인지 나쁜 수열인지, 다시 말해 만들어 낸 수열 내에서 인접한 부분이 동일한 부분이 있는지 없는지 분별하는 코드를 구현해야 했다. 길이가 N인 수열에서 인접하면서 동일한 수열이 있는 경우는 동일한 수열의 길이가 최소 1 부터 최대 N/2인 경우 발생한다. 따라서 가장 마지막에 집어넣은 수 기준으로 마지막 1개와 그 ..
[백준 14889] 스타트와 링크 (Java) https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 접근 방법 백트래킹이라고 생각하고 풀었는데 풀고 보니까 DFS인 것 같다. 백트래킹은 DFS와 유사하게 깊이 우선으로 탐색을 하지만 모든 경우를 탐색하는 DFS와는 달리, 유망하지 않으면 탐색하기도 전에 가지치기를 한다는 차이가 있다. 먼저, 팀이 나누어지는 모든 경우의 수를 확인하기 위해 DFS를 사용하였다. N명이 있을 때 한 팀당 N/2명으로 동일함으로 한 팀에 N/2명이 채워질 때까지 DFS를 통해 멤버들 번호..
[백준 2609] 최대공약수와 최대공배수 (Java) https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 접근 방법 최대 공약수의 경우 유클리드 호제법을 적용하였다. a와 b의 최대 공약수를 구할 때, a와 b 나눠 나머지가 생기면 b와 그 나머지를 다시 나누고 그렇게 생긴 나머지를 처음 나머지와 그 다음 나머지를 다시 나누고.... 나머지가 없을 때까지 나누는데 이 때 나머지가 없을 때의 나눈 값이 최대공약수가 된다. (자세한 내용은 여기) 최소 공배수는 a와 b를 최대공약수로 나누고 그 값들을 곱한 값이 된다. 즉, 최소 공배수 = 최대 공약수 * (a / 최대 공..
[백준 1978] 소수 찾기 (Java) https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 접근 방법 소수 찾는 로직은 학교 수업 시간에 자주 다루는 내용이기 때문에 크게 어렵지 않았지만 에라토스테네스의 체라는 알고리즘을 이용하여 구현하였다. 에라토스테네스의 체는 가장 작은 수부터 차례로 탐색하여 소수를 찾되, 찾은 소수에 대한 배수를 미리 제거하는 방법이다. 자세한 내용은 이곳을 참고하였다. 최종 코드 import java.util.Scanner; public class Main { public static void main(String[] args) ..
[백준 9663] N-Queen (Java) https://www.acmicpc.net/problem/9663 접근 방법 1차원 배열을 만들어 행은 인덱스에 열은 해당 행의 번째에 배열의 값으로 들어가게 하였다. (예를 들어, 1행 3열이면 positoins[1] = 3) 백트래킹 알고리즘을 통해 1 -> N행으로 depth를 넘어가면서 조건을 통과하는 경우 다음 깊이로 재귀하도록 구현했다. 다음 깊이로 재귀하는 조건과 구현 방법은 다음과 같다 1. 이미 같은 열에 퀸이 놓여있지 않은 경우 -> 열을 나타내는 것은 1차 배열의 값이다. 따라서 이전까지의 배열 인덱스를 탐색하면서 값이 존재하지 않으면 조건에 부합하다. 즉, position[i] != number 2. 이미 놓여있는 퀸이 대각선에 있지 않은 경우 -> 대각선에 놓여있는 경우의 기울기는..
[백준 1182] 부분수열의 합 (Java) https://www.acmicpc.net/problem/1182 접근 방법 백트래킹 방법을 이용했다. dfs와 유사하게 깊이 우선으로 탐색을 하되, 조건에 충족하지 않으면 이전 깊이로 돌아가 이어서 진행하는 방식으로 구현하였다. 입력값으로 받은 수열을 배열로 만들고 순차적으로 탐색을 하는데 깊이 들어갈 때 마다 해당 깊이의 값을 포함하고 다음 깊이로 재귀 해당 깊이의 값을 포함하지 않고 다음 깊이로 재귀 를 나누어 탐색하였다. 이 문제에서 조건은 total == S 구현 시 주의해야 할 점은 다음과 같았다. 원소가 하나인 경우도 경우의 수++ (ex. S = 0인 경우, {0}도 해당됨) 마지막 depth까지 가지 않았는데 total == S가 되더라도 경우의 수++하고, 마지막까지 가봐야 함 (또 다..
[백준 5430] AC (Java) 생각보다 정답 비율이 너무 낮은 것으로 보아 메모리 관리가 필요한 문제라고 생각했다. 메모리를 적게 사용할 방안으로 고민한 첫 번째 시도는 error가 발생할 상황을 exception이 일어나기 전에 처리하는 방법이었다. 명령어 p에 "D"의 갯수가 입력으로 들어오는 배열의 수 보다 많으면 error가 난다고 생각하여 이를 체크하는 메소드를 구현했고, 배열을 뒤집는 기능은 Collections.reverse()를 이용 했다. 중간에, UnsupportedOperationException이라는 처음 보는 에러를 보게 되었다. 배열에 담긴 데이터를 조작하기 위해 Arrays.asList()를 이용해 리스트를 변환했는데, 이렇게 리스트로 변환된 데이터를 늘이거나 줄이는 동작을 수행하려고 하면 발생하는 에러라고..
[백준 1966] 프린터 큐 (Java) https://www.acmicpc.net/problem/1966 최종 코드 import java.util.Arrays; import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int trial = scanner.nextInt(); int[] results = new int[trial]; scanner.nextLine(); for (int i = 0; i < trial; i++) { // 입력 받은 시도 횟수만큼 코드 실행 String input = scanner.nextLine(..

티스토리툴바