목록알고리즘/백트래킹 (11)

쉬운 프로그래밍

[알고리즘] 프로그래머스 - 소수찾기 - JAVA

https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7..
알고리즘/백트래킹 2021. 8. 16. 15:02
[알고리즘] 프로그래머스 - 여행경로 - JAVA

https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주..
알고리즘/백트래킹 2021. 8. 13. 10:48
[알고리즘] 프로그래머스 - 단어 변환 - JAVA

문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로..
알고리즘/백트래킹 2021. 8. 12. 17:26
[알고리즘] 백준 14889 스타트와 링크 - JAVA

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 총원 4명이 축구를 한다고 예를 들면 (1, 2), (3,4)와 같이 팀 순서쌍을 어떤 방식으로 만드냐가 문제를 푸는데 핵심문제이다. visited[] boolean 배열을 만들어서 true인 인덱스끼리 한 팀, false인 인덱스끼리 한 팀이라는 아이디어로 문제를 해결하였다. 백트래킹 방식을 적용하여 모든 경우에 대한 순서쌍을 만들었다. 코드 설명은 주석에 자세히 써놓았다. import java.io.BufferedReader; ..
알고리즘/백트래킹 2021. 2. 6. 21:29
[알고리즘] 백준 14888 연산자 끼워넣기 - JAVA

www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 해결 방법 자체는 떠올리기 쉬웠다. 아래 그림과 같이 연산자의 개수를 통해 유망한 노드인지 가지치며 깊이우선탐색을 진행하며 depth가 꽉 차면 최대값과 최소값을 판단하고 반환하는 방식을 떠올렸다. 자세한 설명은 코드에 주석을 적어놨다. import java.io.BufferedReader; import java.io.IOException; impor..
알고리즘/백트래킹 2021. 2. 5. 22:31
[알고리즘] 백준 2580 스도쿠 - JAVA

www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 이 문제에서 핵심은 '노드가 유망한지 검사'하는 것이다. 유망한지 판단이 완료되면 맞는 값을 스도쿠판에 집어넣고 다음 재귀함수를 호출한다. 백트래킹 문제를 풀 때에는 항상 노드가 유망한지 검사하는 것에 초점을 맞추어 가지치기를 해야할것. 자세한 설명은 주석으로 달아놨다. import java.io.BufferedReader; import java.io.IOException; import java.io.Input..
알고리즘/백트래킹 2021. 2. 4. 18:45
[알고리즘] 백준 9663 N-Queen

www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class BOJ_9663 { static int n; static int[] map; static int count = 0; public static void main(String[] args) throws IOException { BufferedR..
알고리즘/백트래킹 2021. 1. 10. 15:09
[알고리즘] 백준 6603 로또

www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_6603 { static int k; static int[] map; static boolean[] visited; static int[] arr..
알고리즘/백트래킹 2021. 1. 9. 15:28
Prev 1 2 Next