JAVA - 백준 [BAEK JOON]/백트래킹
[백준] 14889번 : 스타트와 링크 - JAVA [자바]
[백준] 14889번 : 스타트와 링크 - JAVA [자바]
2020.07.15www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 저번 연산자 끼워넣기에 이어 이번 문제도 백준에서 제공하는 삼성 SW 역량 테스트 기출문제 중 하나다. 이 문제의 포인트는 두 팀으로 나누는데, 각 팀의 능력치 차이를 최소화 한다는 것이다. 한마디로 팀의 전력차가 적게 나도록 팀을 짜면 된다. 그렇게 어려운 문제는 아니니 천천히 풀어보자. 알고리즘 [접근 방법] 앞서 말했듯 두 팀으로 나누면 된다. 위 문제의 예시로 보자. 위와 같이 4명의 사람이 있을 때 두 팀으로 나눌 수..
[백준] 14888번 : 연산자 끼워넣기 - JAVA [자바]
[백준] 14888번 : 연산자 끼워넣기 - JAVA [자바]
2020.07.14www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 문제 백준에서 제공한느 삼성 SW 역량 테스트 기출 문제 중 하나다. (참고로 덧붙이자면 삼성 SW 역량 테스트의 경우 dp와 탐색 정도의 기본적인 알고리즘 풀이 능력은 갖추는 것을 추천한다. 자료구조는 뭐.. 당연 기초 중의 기초다.) 알고리즘 [접근 방법] 이번 문제 또한 그동안 백트래킹을 통해 문제를 풀어보고 정확하게 이해했다면 정말 쉽게 접근 ..
[백준] 2580번 : 스도쿠 - JAVA [자바]
[백준] 2580번 : 스도쿠 - JAVA [자바]
2020.07.09www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 N-Queen 문제를 풀었다면 이 문제 또한 접근 방법만 잘 이해한다면 매우 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 스도쿠를 한 번쯤은 모두 접해보셨을 것이라 생각한다. 같은 행과 열에 겹치지 않으면서 3×3 행렬 안에서도 겹치면 안된다. 즉, 이 규칙을 토대로 조건문을 만들어야 한다는 것은 누구나 알 것이다. 이전 문제처럼 재귀호출부와 조건 검사 함수, 이렇게 두 개를 구성하도록 하자. 최대한..
[백준] 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)에 대해 먼저 간단하게 이해하고 가자. 위 단어를 그대로 해석하고 이해하면 된다. 말 그대로 되추적인데, 좀더 알고리즘적으로 설명하자면, 어떤 노드의 '유망성'을 판단한 뒤, 해당 노드가 유망하지..