전체 글

[SW expert Academy] SWEA 2806번 N-Queen 자바(Java)

[D3] N-Queen - 2806 문제 링크 성능 요약 메모리: 20,684 KB, 시간: 170 ms, 코드길이: 1,103 Bytes 제출 일자 2023-10-24 16:19 출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do 문제 해결 방법 1. 놓을 수 있는 경우와 아닌 경우를 구분해야 함 2. 핵심은 대각선 확인하기.(행을 뺀 절대값과 열을 뺀 절대 값이 같으면 대각선 위치) import java.util.Scanner; class Solution { static int[] arr; static int n,result; public static void main(String args[]) thro..

[백준] 16987번 : 계란으로 계란치기 Gold5(골드5) - JAVA[자바]

[Gold V] 계란으로 계란치기 - 16987 문제 링크 성능 요약 메모리: 18356 KB, 시간: 280 ms 분류 백트래킹, 브루트포스 알고리즘 제출 일자 2023년 10월 24일 14:31:26 문제 설명 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱걸이를 5회 하는 기적의 운동 루틴을 통해 뇌와 근육을 동시에 단련한다. 근육을 단련할 때 식단이 정말로 중요하다는 것을 아는 인범이는 탄수화물이 많은 밥이나 빵 따위의 아침 식사를 대신해 단백질이 많은 계란찜을 해먹는다. 계란찜을 먹기 위해서는 계란을 깨야 하는데, 인범이는 힘이 너무 넘치는 나머지..

[백준] 10971번 : 외판원 순회2 Silver2(실버2) - JAVA[자바]

[Silver II] 외판원 순회 2 - 10971 문제 링크 성능 요약 메모리: 19624 KB, 시간: 524 ms 분류 백트래킹, 브루트포스 알고리즘, 외판원 순회 문제 제출 일자 2023년 10월 24일 11:32:56 문제 설명 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순..

[백준] 15666번 : N과 M(12) Silver2(실버2) - JAVA[자바]

[Silver II] N과 M (12) - 15666 문제 링크 성능 요약 메모리: 19900 KB, 시간: 268 ms 분류 백트래킹 제출 일자 2023년 10월 24일 11:02:20 문제 설명 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 ..

[백준] 15665번 : N과 M(11) Silver2(실버2) - JAVA[자바]

[Silver II] N과 M (11) - 15665 문제 링크 성능 요약 메모리: 90956 KB, 시간: 580 ms 분류 백트래킹 제출 일자 2023년 10월 24일 10:58:41 문제 설명 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은..

[백준] 15664번 :N과 M(10) Silver2(실버2) - JAVA[자바]

[Silver II] N과 M (10) - 15664 문제 링크 성능 요약 메모리: 18376 KB, 시간: 224 ms 분류 백트래킹 제출 일자 2023년 10월 24일 10:53:50 문제 설명 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열..

[백준] 15663번 : N과 M(9) Silver2(실버2) - JAVA[자바]

[Silver II] N과 M (9) - 15663 문제 링크 성능 요약 메모리: 31336 KB, 시간: 364 ms 분류 백트래킹 제출 일자 2023년 10월 24일 10:49:21 문제 설명 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해..

Backtracking

백트래킹이란? 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법. 최적화 문제와 결정 문제를 푸는 방법이다. 특징 - 해를 찾아가는 도중, 지금의 경로가 invalid 하다면 그 경로를 더이상 가지 않고 되돌아감. -> 즉 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것 가지치기를 얼마나 잘하느냐에 따라 프로그램의 효율이 달라짐 - DFS보다 효율적이다. 예시 1: BOJ 15649번: N과 M(1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한..