backtracking9 [백준] 1941번: 소문난 칠공주 (Java) 1. 문제설명총 25명의 여학생들이 5x5의 정사각형 격자 형태로 자리가 배치되어 있다. S(이다솜파)와 Y(임도연파)를 값으로 갖는 5*5 행렬이 주어졌을 때 아래 규칙을 만족하는 모든 경우의 수를 구한다.7명의 학생들로 구성되어야 하고, 7명의 자리는 서로 가로나 세로로 인접해야 한다.7명의 학생 중 S 학생이 적어도 4명 이상은 반드시 포함되어야 한다.시간 제한: 2초메모리 제한: 256MB 2. 접근 방식25자리 중 7자리를 선택하는데, ‘S’ 학생이 4명 이상 포함되도록 한다. (조합, 백트래킹)BFS를 사용해 해당 7개의 자리가 모두 상하좌우로 연결되어 있는지 확인한다.선택된 7명의 자리가 서로 인접한디 BFS로 확인한다. 인접할 경우 count 증가시킨다. 3. 틀린 이유2차원 배열로 백트래.. 2024. 9. 13. [백준] 14888번: 연산자 끼워넣기 (Java) 1. 문제설명N개의 수로 이루어진 수열에서, 수와 수 사이에 연산자를 하나씩 넣어 수식을 만들 수 있다. 식의 계산은 연산자 우선순위를 무시하고 앞에서부터 진행한다. 나눗셈의 경우 몫만 취하며, 음수를 나눌 때는 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼다.N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구한다. (주어진 수의 순서를 바꿀 수 없고, 어떤 식이더라도 -10억보다 크거나 같고, 10억보다 작거나 같은 INT 범위의 결과가 나오는 입력만 주어진다.)시간 제한: 2초메모리 제한: 512MB 2. 접근 방식수와 연산자를 배열에 저장한다.모든 경우의 식을 계산해야 한다. ⇒ 완전탐색, 백트래킹메서드에서 “다음 계산할 수의 인덱스(`numI.. 2024. 9. 13. [백준] 16987번: 계란으로 계란치기 (Java) 1. 문제설명계란은 내구도와 무게에 대한 정보가 주어지고, 왼쪽부터 차례로 들어 한 번씩만 다른 계란 쳐 최대한 많은 계란을 깨는 문제이다. 계란의 내구도는 상대 계란으 무게만큼 깎이게 되고, 내구도가 0 이하가 되면 깨진다.계란을 치는 과정:가장 왼쪽 계란을 든다.들고 있는 계란으로 다른 계란 중 하나를 친다. 만약 손에 든 계란이 깨졌거나 다른 모든 계란이 깨진 경우 넘어간다.최근에 든 계란의 오른쪽 계란을 들고 2번 과정을 반복한다. 가장 오른쪽 계란을 들게 되면 종료한다.시간 제한: 2초메모리 제한: 512MB 2. 접근 방식참고: https://buly.kr/4bgWSet계란의 내구도와 무게를 각각 다른 배열에 저장한다.백트래킹을 사용하여 계란을 깨뜨리는 모든 경우의 수를 구한다.마지막 계란을 .. 2024. 9. 13. [백준] 2661번: 좋은 수열 (Java) 💡문제 분석 요약1,2,3 으로만 이루어져 있는 길이가 N인 좋은 수열 중 가장 작은 수를 구하는 문제이다.좋은 수열은 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 없는 수열이다.시간 제한: 1초메모리 제한: 128MB 💡알고리즘 설계백트래킹 메서드 (`backTrack`)1, 2, 3 을 순차적으로 현재 수열(`seq`)에 추가한다.`seq` 에 숫자를 추가했을 때 좋은 수열인지 검사한다. (`isGoodSeq`)좋은 수열이면 숫자를 추가하여 메서드를 재귀 호출한다.`seq`의 길이가 N이 되면 출력하고 프로그램을 종료한다.좋은 수열인지 검사 (`isGoodSeq`)길이가 1인 부분 수열부터 시작해서 수열의 길이 절반까지 늘려가며 검사한다. (1부터 seq.length() / 2 까지)각.. 2024. 7. 27. [백준] 1759번: 암호 만들기 (Java) 💡문제 분석 요약암호의 알파벳 개수 L과 사용한 문자의 종류 C를 입력받아서, 가능성 있는 암호들을 모두 구하는 문제이다.시간 제한: 2초메모리 제한; 128MB 💡알고리즘 설계C개의 문자열을 오름차순으로 `alpha` 배열에 저장하고, 자음&모음의 여부를 `check` 배열에 저장한다.start를 0부터 백트래킹을 시도한다.백트래킹 메서드매개 변수로 `start` (시작위치), `length` (암호 길이)를 받는다.`length` 가 L이면암호의 모음, 자음 최소 개수 조건을 확인하고, `result` 에 추가한다. (중복 방지를 위해 `LinkedHastSet` 타입으로 `result` 를 정의함)start부터 C-1까지 작업을 수행한다.`password[length]` 에 현재 위치의 알파벳을.. 2024. 7. 26. [백준] 1182번: 부분수열의 합 (Java) 💡문제 분석 요약N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열에서 그 수열의 원소를 모두 더한 값이 S가 되는 경우의 수를 구하는 문제이다.시간 제한: 2초메모리 제한: 256MB 💡알고리즘 설계`numbers` 배열에 N개의 정수를 입력받는다.부분 수열의 길이(`depth`)는 1~N까지 가능하다. 각 길이에 대해 백트래킹을 수행한다.백트래킹 메서드현재 깊이가 목표 깊이와 같으면, (`curDepth == depth`)부분수열의 합(`sum`)이 S인지 확인하고 `result`를 갱신한다.그렇지 않으면, 현재 위치(`start`)부터 N까지의 숫자에 대해해당 숫자를 `sum`에 더한다.다음 위치로 이동하여 메서드를 재귀 호출한다.백트래킹 후 `sum` 에서 해당 숫자를 뺀다. (원.. 2024. 7. 25. [백준] 6987번: 월드컵 (Java) 💡문제 분석 요약월드컵 조별 리그의 결과를 입력받아, 입력받은 결과가 가능한지 아닌지 판별하는 문제이다.시간 제한: 1초메모리 제한: 128MB 💡알고리즘 설계문제 조건한 팀의 경기 수는 5회각 팀은 다른 모든 팀과 한 번씩 경기 ⇒ 총 15경기각 경기 결과는 승-패, 무-무, 패-승 중 하나 ⇒ 총 3가지자료구조int[] team1, int[] team2: 각 라운드별 경기를 진행하는 팀int[][] gameInputResult: 입력받은 각 팀의 경기 결과(승,무,패) 횟수int[][] gameResult: 백트래킹 과정에서 계산하는 각 팀의 경기 결과 횟수int[] result: 각 테스트 케이스의 결과를 저장하는 배열백트래킹라운드 0부터 시작해서 각 경기 결과를 가정하며 탐색각 라운드에서 3가.. 2024. 7. 24. 이전 1 2 다음 반응형
