꾸준히 삽질하기,,

📍 문제https://www.acmicpc.net/problem/1987 📍 문제 풀이같은 알파벳은 두 번이상 지날 수 없다는 조건으로 `visited` 배열을 선언했다. A부터 Z까지를 인덱스로 생각해 배열의 크기를 26두고 방문 처리를 해줬다. dfs를 좌표와 현재까지 방문한 칸수로 재귀호출을 진행했다. 상하좌우의 좌표를 `dx` 와 `dy`를 통해 이동하도록 하고, 해당 좌표의 값이 보드의 범위 내에 존재한다면 방문 처리해줬다.그리고 호출이 종료된다면 다시 방문값을 false로 바꿔주면서 매번 최대값을 갱신해줬다. 기본적인 dfs방식과 백트래킹이 합쳐진 문제였다.보통의 백트래킹 문제는 종료 조건이 존재하지만, 이 문제의 경우에는 종료하는 위치도, 조건도 없었다.그렇기 때문에 매번 최대값을 갱신해..

📍 문제https://www.acmicpc.net/problem/15686 📍 문제 풀이 풀이과정은 아래와 같다.1. 집과 치킨집의 좌표를 각각 리스트에 저장한다.2. 가능한 치킨집의 조합을 모두 구한다.3. 조합별 집과의 치킨 거리를 구한다. 이를 통해 도시 전체의 치킨 거리를 구한다.4. 도시 전체 치킨 거리가 더 작다면 값 갱신 이때 가능한 치킨집의 조합은 opened 배열로 확인했다. 값이 true라면 치킨집이 열려있고, false면 닫혀있다고 생각하고 풀이를 진행했다. 📍전체코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;im..

📍 문제https://www.acmicpc.net/problem/14889 📍 문제 풀이우선 두팀으로 나눠야한다. 아래의 경우에는 visited배열을 두고 true값은 스타트팀, false값은 링크팀으로 구분했다. 팀을 나누는 방식이 이 문제의 관건인 것 같다.https://www.acmicpc.net/problem/15650이 문제를 풀어본다면 팀 나누는 방식에 대한 이해가 조금 더 수월할 것 같다.. 팀을 나눈 후에는 각각 팀에 대한 능력치 값을 구한다. for문을 통해 능력치의 합을 구해주면 된다. 그리고 스타트팀과 링크팀의 차이의 절대값을 구해준다. 이때 차이가 0이라면 그게 최소값이기 때문에 바로 프로그램을 종료시켜주면 불필요한 연산을 줄일 수 있다.하지만,,처음에는 생각하지 못해서 아래의 ..

📍 문제https://www.acmicpc.net/problem/1251 📍 문제 풀이만들어진 모든 문자열을 추가할 리스트를 만들어둔다.그리고 입력받은 문자열을 3개로 나눌 인덱스 값을 지정한다.아래와 같은 경우로는 `(0, a)`, `(a, b-1)`, `(b, input.length()-1)` 세개로 문자열을 나눌 수 있다.for (int a = 1; a 각각의 문자열을 뒤집기 위한 `flipWord()` 메서드를 선언해줬다.여러 방법이 있겠지만, StringBuilder를 통해 새로운 문자열을 생성해 리턴해주는 방식을 사용했다.각각 문자열을 뒤집은 뒤 처음에 선언해 둔 리스트에 추가해주고 정렬하면 사전순으로 가장 앞서는 단어를 출력할 수 있다. 📍전체코드import java.io.Buffer..

📍 문제https://www.acmicpc.net/problem/21736 📍 문제 풀이우선 이동할 수 있는 방향은 문제에서 정해줬기 때문에 이를 `dx`, `dy` 배열에 담는다.그리고 캠퍼스의 정보를 담을 `maps` 배열과, 도연이가 해당 지점을 방문했는지 여부를 담을 `visited` 배열의 값을 초기화해준다.이때, 도연이는 `(0,0)`에서 탐색을 시작하는게 아니라 `I` 인 지점에서 시작하기 때문에 탐색 시작 값의 좌표를 따로 저장해준다. 도연이가 이동하면서 아래의 과정을 거치게된다.1. 현재 위치에 대해서 방문처리2. 현재 위치에 사람이 있는가? 있으면 결과값 + 13. 다음 갈 위치들에 대한 조건 확인캠퍼스 범위 내에 존재하는가?벽이 아닌가? 이미 방문한 곳이 아닌가?4. 위의 조건을 ..

📍 문제https://www.acmicpc.net/problem/1051📍 문제 풀이이중 for문을 통해서 배열을 돌면서 size를 줄이는 식으로 진행했다. 우선 정사각형의 최대 길이는 `n,m`값 중 더 작은 값일 것이다. 이 값을 `size`로 두고 시작한다. 이 문제에서 주의해야하는 점은 `size`에 따라서 확인해야하는 배열의 값이었다. 예를 들어, 아래의 경우와 같이 `i,j,size`가 각각 0,0,3인 경우를 생각해보자.`size`가 3이라고 maps[0][3], maps[3][0], maps[3][3]을 확인하는게 아니라maps[0][2], maps[2][0], maps[2][2]를 확인해야 `size`가 3인 정사각형을 만들 수 있다.이 점을 주의하면서 확인하는 인덱스의 범위와 값들을..

📍 문제https://www.acmicpc.net/problem/9625 📍 문제 풀이버튼을 눌렀을 때의 문자열과 A의 갯수 B의 갯수를 표로 나타내면 아래와 같다.버튼 누른 횟수문자열A의 갯수B의 갯수0A101B012BA113BAB124BABBA235BABBABAB35 이렇게 경우에 따라서 작성해보면 피보나치 수열을 이용해 푸는 문제라는걸 알 수 있다.2차원 배열을 두어 `dp[버튼 누른 횟수][0]`은 A의 갯수, `dp[버튼 누른 횟수][1]`은 B의 갯수로 저장했다.dp[1]과 dp[2]는 초기값으로 셋팅해두고 for문을 통해서 3부터 입력받은 k까지 회문을 돌리면 원하는 값을 얻을 수 있다. ** dp는 앞의 경우의 수들은 모두 적어봐야 규칙을 찾을 수 있는 것 같다.이 문제의 경우도 5번..

📍 문제 https://www.acmicpc.net/problem/1380 📍 문제 풀이이 문제에서 A냐 B는 크게 중요하지 않았다.A,B와 함께 주어지는 여학생 번호가 한 번이냐 두번이냐가 중요한 문제였다. 이를 확인하기 위해서 학생들 이름을 저장한 리스트 `names`, 압수당한 학생들의 인덱스를 저장하는 `earingGirls`를 만들었다.리스트에 입력받은 여학생 번호가 존재하지 않는다면, 압수당하는 상황이고 존재한다면 돌려받는 상황이다.때문에 번호가 한번만 주어진 학생은 압수당하고 돌려받지 못한 상황이다. `earingGirls`에 존재하지 않는다면 압수당하는 상황이니 추가해주고, 이미 존재한다면 돌려받는 상황이니 삭제해줬다. 모든 입력값에 대해서 위의 과정을 거치고나면 리스트에는 돌려받..

📍 문제 https://www.acmicpc.net/problem/1010 📍 문제 풀이서쪽에서 동쪽으로 다리를 연결한다가 아니라 반대로 생각해보면 어떨까M개 사이트에서 N개 만큼의 사이트를 선택해서 서쪽과 연결해 다리를 짓는다면? 이때 다리끼리 겹치면 안된다고 했기 때문에 순서는 고려하지않는 조합을 이용해야한다. 💭 조합이란?n개의 값 중에서 순서를 고려하지 않고 r개의 숫자를 선택하는 경우의 수 예를 들어, 주머니에 공 5개가 있는데 3개를 뽑는다고 생각해보자.5개 뽑는 경우의 수 = 1을 뽑은 경우 + 1을 뽑지 않은 경우 로 표현할 수 있다.1을 뽑은 경우라면 이제 1을 제외한 n-1개 중에 r-1개를 뽑으면 된다.1을 뽑지 않은 경우라면 1을 제외한 n-1개 중 r개를 뽑아야한다. 왜..

📍 문제 https://www.acmicpc.net/problem/2805 📍 문제 풀이이분탐색을 이용하는 문제다. 이분탐색에서 가장 중요한 점은 내가 구해야하는 값이 무엇인지를 정확히 알고있는 것이다.이 경우는 절단기에 설정할 수 있는 높이의 최대값이다. 그렇다면 이 값들을 아래와 같이 초기화해줄 수 있다.절단기에 설정할 수 있는 높이 start의 최소값은 0절단기에 설정할 수 있는 높이의 최대값 end는 나무들의 높이 중 최대값 배열의 원소들을 순회하면서 해당 나무들에서 높이 mid를 빼주어 합을 구해야한다. 이때 설정한 높이 mid가 실제 나무의 높이보다 클 수 있기 때문에 이 경우에는 가져갈 수 있는 나무가 0이다. 반대의 경우에는 배열의 값 - mid 값이기 때문에 두 값 중 더 큰 값을 구..