JAVA - 백준 [BAEK JOON]
[백준] 9663번 : N-Queen - JAVA [자바]
[백준] 9663번 : N-Queen - JAVA [자바]
2020.07.08www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 백트래킹의 대표적인 문제인 N Queen 문제다. 몇 가지 규칙만 알면 쉽게 풀 수 있으니 차근차근 알아보도록 하자. 알고리즘 [접근 방법] 문제에서 일단 체스판 크기가 주어지면 해당 체스판 안에서 퀸이 서로 공격할 수 없도록 배치하는 경우의 수를 찾으면 된다. 퀸이 이동할 수 있는 위치는 대부분 알겠지만 상하좌우 및 대각선으로 거리 제한 없이 한 방향으로 이동이 가능하다. 즉, 다음 그림과 같이 움직일 수 있다. 이 이..
[백준] 15652번 : N과 M (4) - JAVA [자바]
[백준] 15652번 : N과 M (4) - JAVA [자바]
2020.07.03www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 N과 M (2) 문제를 기억하신다면 아마 금방 풀 수 있을 것이다. 다만 이 번 문제는 약간 다른 점이라 한다면 '비내림차순'인 수열을 출력해야한다는 점이다. (오름차순과 비내림차순은 다르다) 즉, 중복 여부를 고려하지 않는다. (중복허용) 알고리즘 [접근 방법] 그동안 필자의 포스팅에서 N과 M 시리즈들을 모두 보셨다면 이 번 문제 또한 그리 어렵지 않게 풀 수 있을 것이다. 그래도 혹시 모르니 참고 ..
[백준] 15651번 : N과 M (3) - JAVA [자바]
[백준] 15651번 : N과 M (3) - JAVA [자바]
2020.06.29www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 N과 M (1) 문제와 매우 비슷하다. 아니 오히려 쉽게 풀 수 있다. N과 M (1) 과 달라진 점이라면 중복여부를 고려하지 않아도 된다는 점이다. 알고리즘 [접근 방법] 사실 이 문제는 어렵지 않다. (어쩌면 이 문제가 N과 M (1) 이여야 하는게 더 맞지 않을까...) 1 부터 N까지 M의 길이로 조합할 수 있는 조합을 오름차순으로 나열만 하면 되는 문제기에 사실 매우 간단하게 짤 수 있다. 그래..
[백준] 15650번 : N과 M (2) - JAVA [자바]
[백준] 15650번 : N과 M (2) - JAVA [자바]
2020.06.26www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 저번 백트래킹 N과 M (1) 에 이은 매우 간단한 문제다! 알고리즘 [접근 방법] 이 문제 또한 그리 어렵지 않다! 만약 백트래킹 문제로 이 문제를 처음 접하신다면 먼저 아래 글을 꼭 참고하시길 바란다. st-lab.tistory.com/114#알고리즘 [백준] 15649번 : N과 M (1) - JAVA [자바] www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 ..
[백준] 15649번 : N과 M (1) - JAVA [자바]
[백준] 15649번 : N과 M (1) - JAVA [자바]
2020.06.24www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 백트래킹 카테고리의 첫 문제다. 이러한 문제를 처음 접하는 분들은 약간은 난해할 수는 있지만, 원리만 이해하면 매우 쉬운 문제이니 차근차근 알아보도록하자. 알고리즘 [풀이 방법] 백트래킹(Backtracking)에 대해 먼저 간단하게 이해하고 가자. 위 단어를 그대로 해석하고 이해하면 된다. 말 그대로 되추적인데, 좀더 알고리즘적으로 설명하자면, 어떤 노드의 '유망성'을 판단한 뒤, 해당 노드가 유망하지..
[백준] 10814번 : 나이순 정렬 - JAVA [자바]
[백준] 10814번 : 나이순 정렬 - JAVA [자바]
2020.06.20www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 � www.acmicpc.net 문제 ※ 주의할 점 나이순 정렬을 기준으로 하되, 나이가 같을경우 주어진 입력순으로 정렬한다. 알고리즘 [접근 방법] 이 문제의 경우 정말 다양한 방법이 있다. 1. 먼저 가장 간단한 방법은 String[][] 2차원 배열을 통해 각 배열에 나이와 이름을 저장한 뒤, 나이 순으로 정렬하는 방법이다. 이때 정렬방법은 Arrays.sort()에 Comparator 의 compare 메소드를 구현하여 사용자 정렬을 사..
[백준] 1181번 : 단어 정렬 - JAVA [자바]
[백준] 1181번 : 단어 정렬 - JAVA [자바]
2020.06.19www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 이전 좌표정렬하기 문제를 풀어보았다면 이 문제 또한 매우 간단한 문제다! ※ 주의할 점 단어 길이순으로 정렬한 뒤, 길이가 같을 경우 사전순으로 정렬해야한다. 중복되는 단어가 있을경우 한 번만 출력한다. 알고리즘 [접근 방법] 이전 포스팅에서도 말했지만 배열을 특정한 규칙에 의해 정렬하고 싶은 경우 Arrays.sort 메소드에 Comparator 을 구현하면 된다고 했다. (만약 보지 못한 분들을 위..
[백준] 11651번 : 좌표 정렬하기 2 - JAVA [자바]
[백준] 11651번 : 좌표 정렬하기 2 - JAVA [자바]
2020.06.17www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 문제 좌표 정렬하기 (11650번) 문제를 풀었다면 매우 쉬운 문제다. 알고리즘은 따로 설명 안할테니 아래 링크를 참고해주시면 된다. st-lab.tistory.com/110#알고리즘 [백준] 11650번 : 좌표 정렬하기 - JAVA [자바] www.acmicpc.net/problem/11650 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주..
[백준] 11650번 : 좌표 정렬하기 - JAVA [자바]
[백준] 11650번 : 좌표 정렬하기 - JAVA [자바]
2020.06.10www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 문제 이번 문제는 람다식(lambda)만 쓸 줄 알면 그리 어렵지 않게 풀 수 있다. (오랜만입니다..) 알고리즘 [접근 방법] 보통 문제를 보면 가장 먼저 생각하는 것이, 아! 2차원 배열을 사용해야겠다! 일 것이다. 아쉽게도 Arrays.sort() 자체는 2차원 배열의 정렬을 할 수가 없다. 그렇기 때문에 람다식을 사용하여 Arrays.sort() 확장..
[백준] 1427번 : 소트인사이드 - JAVA [자바]
[백준] 1427번 : 소트인사이드 - JAVA [자바]
2020.06.03www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 오랜만에 매우 쉬운 문제가 나왔다. 알고리즘 [접근 방법] 이 문제의 경우 접근 방법이 정말 무궁무진하다. 먼저 정렬 알고리즘으로 배열을 이용하여 Arrays.sort 를 사용하는 방법부터 카운팅정렬을 사용하는 방법, 이렇게 크게 두 가지가 있을 것이다. 또한 각 자릿수의 값을 정렬하는 것이다보니 입력방법도 다양하게 할 수 있다. Scanner 을 사용하여 입력받는 방법, BufferedReader 로 입력받는 방법, InputStream 으로 입력받는 방법 등 매우 많다. 각 자릿수를 값으로..