백트래킹
-
BOJ 1107 리모콘 자바(java) 풀이 랭크 : 골드5 백준 1107 리모컨 문제 정리 리모컨의 일부 숫자 버튼이 고장났다. 리모컨에는 0~9까지의 숫자 버튼과ㅏ +, - 버튼이 있다 '+' 버튼은 +1된 채널, '-' 버튼은 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 이동하려고 하는 채널은 N이고, 고장난 버튼이 주어질 때, 채널 N으로 이동하기 위해 최소 몇번 버튼을 눌러야 하는지 구하시오 이동하려는 채널 최대 500,000 수빈이가 지금 보고 있는 채널은 100번 문제 접근 이 문제는 다음과 같은 사항을 고려하여야 합니다 고장난 버튼 수가 없는 경우 -> 입력 받지 않음 원하는 번호가 100번인 경우 -> 0 출력하고..
[완전탐색, 백트래킹] 백준 1107번 리모컨 자바 풀이BOJ 1107 리모콘 자바(java) 풀이 랭크 : 골드5 백준 1107 리모컨 문제 정리 리모컨의 일부 숫자 버튼이 고장났다. 리모컨에는 0~9까지의 숫자 버튼과ㅏ +, - 버튼이 있다 '+' 버튼은 +1된 채널, '-' 버튼은 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 이동하려고 하는 채널은 N이고, 고장난 버튼이 주어질 때, 채널 N으로 이동하기 위해 최소 몇번 버튼을 눌러야 하는지 구하시오 이동하려는 채널 최대 500,000 수빈이가 지금 보고 있는 채널은 100번 문제 접근 이 문제는 다음과 같은 사항을 고려하여야 합니다 고장난 버튼 수가 없는 경우 -> 입력 받지 않음 원하는 번호가 100번인 경우 -> 0 출력하고..
2020.06.10 -
sw expert academy 2112번 보호 필름 자바(java) 풀이 모의 SW 역량 테스트 sw expert academy 2112번 보호 필름 문제 정리 보호 필름은 얇은 막 D개를 쌓아서 만든다 얇은 막은 동일한 크기를 가진 바 모양의 셀들이 가로방향으로 W개 붙여서 만든다 (두께 D 가로크기 W의 보호필름 완성!) 각 셀들은 특성 A 또는 B를 가진다. 충격은 보호 필름 단면의 세로 방향으로 가해지므로 세로방향의 특성이 중요하다 단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만 성능검사를 통과할 수 있다. 약품을 투입해서 가로 방향의 셀들을 모두 하나의 특성으로 변경할 수 있다. (약품 A -> 모두 A로 변경 / 약품 B -> 모두 B로 변경) 약품을 ..
[dfs, 백트래킹] sw expert academy 2112번 보호 필름 자바 풀이sw expert academy 2112번 보호 필름 자바(java) 풀이 모의 SW 역량 테스트 sw expert academy 2112번 보호 필름 문제 정리 보호 필름은 얇은 막 D개를 쌓아서 만든다 얇은 막은 동일한 크기를 가진 바 모양의 셀들이 가로방향으로 W개 붙여서 만든다 (두께 D 가로크기 W의 보호필름 완성!) 각 셀들은 특성 A 또는 B를 가진다. 충격은 보호 필름 단면의 세로 방향으로 가해지므로 세로방향의 특성이 중요하다 단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만 성능검사를 통과할 수 있다. 약품을 투입해서 가로 방향의 셀들을 모두 하나의 특성으로 변경할 수 있다. (약품 A -> 모두 A로 변경 / 약품 B -> 모두 B로 변경) 약품을 ..
2020.05.22 -
BOJ 16987번 계란으로 계란치기 문제 자바(java) 풀이 랭크 : 실버3 백준 16987번 계란으로 계란치기 문제 정리 계란으로 계란을 치는 경우 다음과 같은 점들을 고려한다. 1.1 계란에는 내구도와 무게가 정해져 있다. 1.2 계란으로 서로를 치면 계란의 내구도는 상대 계란의 무게 만큼 깎이게 된다. 1.3 내구도가 0이 되는 순간 계란이 깨진다. 계란을 왼쪽 부터 차례로 들어 한 번씩만 다른 계란을 쳐서 최대한 많은 계란을 깨려고 한다. 계란을 치는 과정은 다음과 같다. 3.1 가장 왼쪽 계란을 든다. 3.2 손에 든 계란으로 깨지지 않은 계란중 하나를 친다. 만약 손에 든 계란이 깨졌거나 깨지지 않은 계란이 없다면 아무일도 하지 않는다. 3.3 최근에 든 계란의 바로 오른쪽 계란을 들고 반..
[DFS] 백준 16987번 계란으로 계란치기 자바(java) 풀이BOJ 16987번 계란으로 계란치기 문제 자바(java) 풀이 랭크 : 실버3 백준 16987번 계란으로 계란치기 문제 정리 계란으로 계란을 치는 경우 다음과 같은 점들을 고려한다. 1.1 계란에는 내구도와 무게가 정해져 있다. 1.2 계란으로 서로를 치면 계란의 내구도는 상대 계란의 무게 만큼 깎이게 된다. 1.3 내구도가 0이 되는 순간 계란이 깨진다. 계란을 왼쪽 부터 차례로 들어 한 번씩만 다른 계란을 쳐서 최대한 많은 계란을 깨려고 한다. 계란을 치는 과정은 다음과 같다. 3.1 가장 왼쪽 계란을 든다. 3.2 손에 든 계란으로 깨지지 않은 계란중 하나를 친다. 만약 손에 든 계란이 깨졌거나 깨지지 않은 계란이 없다면 아무일도 하지 않는다. 3.3 최근에 든 계란의 바로 오른쪽 계란을 들고 반..
2020.04.01 -
BOJ 2580번 스도쿠 자바(java) 풀이 백트래킹의 대표적인 문제중 하나라고 할 수 있습니다. 백트래킹 문제에 익숙하지 않다면 N-Queen 문제와 이 문제를 꼭 풀어보시기 바랍니다. 난이도: 골드4 BOJ 2580번 스도쿠 문제 정리 9x9 판으로 이루어진 판에 1~9 까지의 숫자들이 써있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1~9까지의 숫자가 한 번씩만 나타난다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1~9 까지의 숫자가 한 번씩만 나타난다. 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오. 스도쿠 판을 채우는 방법이 여럿인 경우 그 중 하나만을 출력한다. 문제 풀이 n-queen 문제와 유사한 방식으로 백트래킹을 이용하여 문제..
[백트래킹] 백준 2580번 스도쿠 자바(java) 풀이BOJ 2580번 스도쿠 자바(java) 풀이 백트래킹의 대표적인 문제중 하나라고 할 수 있습니다. 백트래킹 문제에 익숙하지 않다면 N-Queen 문제와 이 문제를 꼭 풀어보시기 바랍니다. 난이도: 골드4 BOJ 2580번 스도쿠 문제 정리 9x9 판으로 이루어진 판에 1~9 까지의 숫자들이 써있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1~9까지의 숫자가 한 번씩만 나타난다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1~9 까지의 숫자가 한 번씩만 나타난다. 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오. 스도쿠 판을 채우는 방법이 여럿인 경우 그 중 하나만을 출력한다. 문제 풀이 n-queen 문제와 유사한 방식으로 백트래킹을 이용하여 문제..
2020.03.31 -
sw expert academy 4008번 숫자 만들기 자바(java) 풀이 모의 SW 역량테스트 숫자 만들기 sw expert academy 4008번 숫자 만들기 문제정리 연산자와 숫자가 주어질때 가능한 수식을 계산하여 최대와 최소값을 구해라. 연산자의 우선순위는 고려하지 않고 왼쪽에서 오른쪽으로 차례대로 계산한다. 연산자의 개수는 숫자의 개수보다 항상 1개 작다. 숫자의 순서는 바꿀 수 없다. 나눗셈에서 소수점 이하는 버린다. 수식을 완성할때 주어진 카드를 모두 사용해야 한다. 문제풀이 숫자는 순서가 바뀌지 않으므로 연산자의 순서만 조정해주면 됩니다. 그러기 위해서 백트래킹을 통해서 모든 가능한 순서를 찾아주어야 합니다. 그리고 계산을 하면 됩니다. 계산할 때 첫번째 연산자는 2번째 숫자와 3번째 ..
[SWEA] 4008번 숫자 만들기 자바(java) 풀이 (dfs, 백트래킹)sw expert academy 4008번 숫자 만들기 자바(java) 풀이 모의 SW 역량테스트 숫자 만들기 sw expert academy 4008번 숫자 만들기 문제정리 연산자와 숫자가 주어질때 가능한 수식을 계산하여 최대와 최소값을 구해라. 연산자의 우선순위는 고려하지 않고 왼쪽에서 오른쪽으로 차례대로 계산한다. 연산자의 개수는 숫자의 개수보다 항상 1개 작다. 숫자의 순서는 바꿀 수 없다. 나눗셈에서 소수점 이하는 버린다. 수식을 완성할때 주어진 카드를 모두 사용해야 한다. 문제풀이 숫자는 순서가 바뀌지 않으므로 연산자의 순서만 조정해주면 됩니다. 그러기 위해서 백트래킹을 통해서 모든 가능한 순서를 찾아주어야 합니다. 그리고 계산을 하면 됩니다. 계산할 때 첫번째 연산자는 2번째 숫자와 3번째 ..
2020.03.07 -
sw expert academy 2105번 디저트 카페 자바(java) 풀이 모의 SW 역량 테스트 sw expert academy 2105번 디저트 카페 문제 정리 한 변의 길이가 N인 정사각형 모양을 가진 지역이 있다. 숫자는 디저트 카페에서 팔고 있는 디저트의 종류 수를 의미한다. 카페들 사이를 대각선 방향으로 움직일 수 있으며 사각형 모양으로 움직이고 출발지로 되돌아와야 한다. 이동 중에 같은 숫자의 디저트 종류를 가지는 카페에 가면 안된다. 하나의 카페에만 방문해서는 안된다. 왔던 길을 다시 돌아가도 안된다. 가장 많은 카페를 경우하는 케이스를 찾고, 그때 경유 가능한 카페 수를 출력한다. 먹을 수 없는 경우는 -1을 출력한다. 디저트 번호는 1~100까지 이다. 문제풀이 이동 가능한 경우는 다..
[SWEA] 모의 SW 역량 테스트 :: 2105번 디저트 카페 자바 풀이(백트래킹)sw expert academy 2105번 디저트 카페 자바(java) 풀이 모의 SW 역량 테스트 sw expert academy 2105번 디저트 카페 문제 정리 한 변의 길이가 N인 정사각형 모양을 가진 지역이 있다. 숫자는 디저트 카페에서 팔고 있는 디저트의 종류 수를 의미한다. 카페들 사이를 대각선 방향으로 움직일 수 있으며 사각형 모양으로 움직이고 출발지로 되돌아와야 한다. 이동 중에 같은 숫자의 디저트 종류를 가지는 카페에 가면 안된다. 하나의 카페에만 방문해서는 안된다. 왔던 길을 다시 돌아가도 안된다. 가장 많은 카페를 경우하는 케이스를 찾고, 그때 경유 가능한 카페 수를 출력한다. 먹을 수 없는 경우는 -1을 출력한다. 디저트 번호는 1~100까지 이다. 문제풀이 이동 가능한 경우는 다..
2020.03.05