백트랙킹
-
[백준]3980: 선발 명단 - JAVA문제풀이/백준 2021. 6. 18. 11:20
[백준]3980: 선발 명단 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 풀이 모든 포지션으로 선수를 채웠을때, 능력치의 최댓값을 출력하는 문제로 백트랙킹 유형을 활용하여 문제를 풀었다. 헤당 선수를 뽑았는지 아직 뽑지 않았는지 확인해기 위해 visited 배열을 구현해 주었고, 선수를 뽑을 때마다 능력치의 합을 누적시켜 주었다. 선수를 뽑을때 문제의 조건에 따라 능력치가 0인 선수는 뽑지 않도록 한다. 모든 선수에게 포지션을 지정하는데 성공했다면 pos값이 11이 되었을 것이고, 이때 max값을 현재 total값과 비교하여 지정한 다음 되돌아가 다..
-
[백준]13908: 비밀번호 - JAVA문제풀이/백준 2021. 5. 28. 13:03
[백준]13908: 비밀번호 https://www.acmicpc.net/problem/13908 13908번: 비밀번호 첫 번째 예제의 경우 가능한 비밀번호의 조합은 07, 17, 27, 37, 47, 57, 67, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 87, 97이다. 두 번째 예제의 경우 가능한 비밀번호의 조합은 34, 43이다. www.acmicpc.net 풀이 이 문제의 입력 조건에서 n의 범위를 보면 1
-
[백준]9662: N-Queen - JAVA문제풀이/백준 2021. 5. 2. 15:32
[백준]9662: N-Queen www.acmicpc.net/problem/96639663번: N-QueenN-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.www.acmicpc.net풀이프로그래머스에 있는 N-QUEEN문제와 동일한 문제이다. DP문제의 대표가 하노이의 탑이 있다면 순열 문제의 대표라고 할 수 있는 문제이다. 이전에 풀었던 적이 있지만 오래되어 다시 한번 풀어보았다. 다시 풀자니 역시 조금 헤메이는 부분이 있었다. 게다가 백준의 문제 설명이 부족한 것도 있다. 프로그래머스에는 문제 설명이 자세히 잘 되어 있으니 N-QUEEN문제는 프로그래머스에 푸는 것을 추천한다...
-
[백준]15686: 치킨 배달 - JAVA문제풀이/백준 2021. 4. 25. 20:54
[백준]15686: 치킨 배달 www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 백트랙킹 + 조합을 사용하여 문제를 풀었다. 자주 보이는 유형 중에 하나이당. 먼저 연산을 편리하게 하기 위해 집의 위치와 치킨집의 위치를 arraylist로 따로 저장해주었다. m개의 뽑은 치킨집은 boolean타입으로 체크하여 이미 뽑았는지 여부와 함께 도시의 치킨 거리를 구할때도 사용할 수 있도록 하였다. 치킨집 m개를 모두 뽑고난 후 각각의 집 위..
-
[백준]1062: 가르침 - JAVA문제풀이/백준 2021. 4. 24. 15:08
[백준]1062: 가르침 www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 백트래킹과 조합을 사용하여 풀었다. 이 문제는 앞 뒤 'anta'와 'tica'에 속한 a,c,n,t,i 5개의 알파벳을 제외하고 k개의 알파벳을 추가로 학습하여 읽을 수 있는 단어의 최대 개수를 구하는 문제이다. 알파벳을 뽑았는지 확인하기 위해 boolean타입의 visited배열을 선언해 주었고 이미 알고있는 a,c,n,t,i를 true로 설정해 주었다. 그리고 뽑은 알..
-
[백준]1339: 단어 수학 - JAVA문제풀이/백준 2021. 4. 24. 13:54
[백준]1339: 단어 수학 www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 백트랙킹을 사용하여 풀었다. 먼저 알파벳을 리스트에 중복 없이 저장한 다음, 0부터 숫자를 하나씩 올리며 알파벳에 숫자를 할당(?)해 주었다. 리스트의 길이만큼 숫자를 다 뽑았다면 원래의 문자열과 비교하여 자리수에 맞게 숫자 연산을 하여 MAX값을 찾아주었다. 풀이 코드의 구조를 보면 전형적인 백트랙킹 순열 문제와 같다. 이번 문제에서 어려웠던 부분은 문자열을 자리수에 맞..
-
[백준]1405: 미친 로봇 - JAVA문제풀이/백준 2021. 3. 12. 14:27
[백준]1405: 미친 로봇 www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 풀이 DFS + 백트래킹을 사용하여 풀었다. 결국엔 문제에서 구하는 값은 같은 곳을 방문하지 않고 N번동안 이동할 때의 확률을 구하는 것이다. 즉 DFS를 사용하여 N번만큼 이동하되 visited 함수를 사용하여 같은 공간은 방문하지 않도록 처리하면 된다. 이때 이동할 확률을 구하는 방법은 같은 공간을 방문하지 않고 이동하며, 이동할 때매다 이동할 방향의 확률을 곱해서 그 값을 ..
-
[백준]2580: 스도쿠 - JAVA문제풀이/백준 2021. 3. 1. 14:59
[백준]2580: 스도쿠 www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 백트레킹 문제이다. ArrayList를 사용해 0이 입력된 좌표의 위치를 저장하고, list에 담긴 좌표를 하나씩 꺼내 해당 위치에 들어갈 수 있는 숫자를 찾아주었다. 없으면 다음 좌표를 탐색하도록 구현했다. list의 저장된 좌표를 모두 탐색하였다면 더 이상 탐색하지 않아도 되므로 출력을 해주고 아예 프로그램을 종료해 버린다. 여기서 종료해 주지 않고 return을 해주면 틀렸다..