자바

[JAVA] 백준 1245 - 농장 관리

문제 1245번: 농장 관리 [ 문제 조건 ] 인접한 격자 8개를 모두 비교할 dx, dy 배열 산봉우리 높이 > 산봉우리 인접한 격자의 높이 산봉우리 총 갯수 = count 해당 값이 산봉우리 인지 아닌지 여부 = top [ 해결순서 ] 문제에서의 '인접하다' 정의를 먼저 이해해야한다. X, Y 좌표 차이가 1이하인 값인 인접한 값. 대각선 4군데 상하좌우 총 8개의 값을 비교하여 깊이우선탐색을 진행해야한다. 모든 farm 배열을 확인하여 방문하지 않은 값 중 0이 아닌 산봉우리가 될 수 있는 값들을 기준으로 dfs() 를 실행하는데 그 전에, 해당 값이 산봉우리라고 임의로 지정해두고 깊이우선탐색 실행 후에도 해당 값이 제일 높으면 그 때 총 값을 증가시킨다. 기존의 깊이우선탐색을 진행하..

[JAVA] 백준 11057 - 오르막 수

문제 11057번: 오르막 수 [ 문제 조건 ] N의 범위는 1~10000 오르막 수의 개수를 % 10007 [ 해결순서 ] 직접 노트에 적어보면서 규칙을 찾으려고 했다.이를 보면 점화식을 구할 수 있다. 이를 보면 점화식을 구할 수 있다. 각 자릿수별로 끝자리 0~9에 따라 들어갈 수 있는 경우의 수를 구해 해당 n의 경우의 수를 모두 더하면 총 오르막 수 의 개수를 구할 수 있다. 점화식 : dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) ✏️한줄평 쉽다고 생각했지만, 조금 생각을 해봐야하는 신박한 문제였다. 코드

[JAVA] 백준 7569번 - 토마토

문제 7569번: 토마토 [ 문제 조건 ] 입력 1 = 익은 토마토 0 = 익지않은 토마토 -1 = 토마토 없음 출력 0 = 저장될 때 모든 토마토 익음 1 = 모든 토마토 익지 못함 n = 모두 익을 때 까지 최소 며칠이 걸리는지 보관 후 하루가 지나면 익은 토마토와 인접한 건 익음 [ 해결순서 ] 여태까지 풀던 문제는 상하좌우만 비교해서 해결하면 됐으나, 위 아래도 비교해서 6가지 경우를 비교해야한다. 3차원 배열로 가로,세로,높이의 값을 입력받고 너비우선탐색의 대상은 익은 값만 이므로 입력받을 때, 토마토가 익은 것들만 큐에 넣는다. 큐에 넣은 것들을 하나씩 꺼내며 너비우선탐색 한다. 기존 유사한 BFS 문제의 조건 비교에서 (가로, 세로 비교했던 것) 추가로 높이만 비교하고 토마토가 익었으면 (값..

[JAVA] 백준 1991번 - 트리순회

문제 1991번: 트리 순회 [ 해결순서 ] 한줄에 띄어서 입력받으므로 띄어쓰기를 붙여 문자열을 배열로 전환하여 노드에 저장하였다. 문제를 해결하기 위해 노드, 트리 클래스가 있어야 한다. 노드 클래스 : 루트, 왼쪽 자식, 오른쪽 자식이 있고, 노드의 값을 입력받아 지정 가능하다. 트리 클래스 : 여러개의 노드가 모여 트리를 구성하므로, 노드가 있어야 함 add() : 트리에 노드를 추가하는 메소드이며 처음을 제외하고는 search()를 사용하여 추가. search() : 어떤 노드밑에 서브트리가 생기는지 재귀호출하며 찾음. 전위순회 preorder : 루트 → 왼쪽 서브트리 → 오른쪽 서브트리 방문 중위순회 inorder : 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 방문 후위순회 postorder ..

[JAVA] 백준 2667번 - 단지번호붙이기

문제 2667번: 단지번호붙이기 [ 해결순서 ] 깊이우선탐색, 너비우선탐색 어떤 방식으로도 풀 수 있는 문제지만, 나는 문제를 보자마자 깊이우선탐색로 풀어야 겠다고 떠올라 이 방식으로 해결하였다. 총 단지수는 하나의 깊이우선탐색이 끝날때 변수 값을 하나씩 추가하면 되며, 모든 값들을 하나씩 살펴보며 방문하지 않은 것 중 집이 있는 곳을 깊이우선탐색 한다. dfs 메소드는 사실 다른 유사한 깊이우선탐색의 메소드와 비슷하다. 그래도 설명하자면, 입력한 x, y값을 기준으로 상하좌우의 값을 비교하여 조건에 맞는 (방문하지 않고, 집이있으면) 그 값을 기준으로 재귀처리 함. 총 단지수를 출력하고, 각 단지내의 수를 오름차순으로 정렬하여 출력 (까먹고 오름차순 정렬하지 않았다가 틀렸었다) ✏️ 한줄 평 이젠 어떤..

[JAVA] 백준 1697번 - 숨바꼭질

문제 1697번: 숨바꼭질 [ 해결순서 ] 문제의 조건을 파악한 후 이동을 할 때 3가지 경우에 따라 조건문을 작성하면 되겠다고 파악했다. 큐를 이용하여 시작 값을 먼저 큐에 넣고 큐가 비어있을 때까지 반복해서 큐의 값을 꺼내어 3가지 조건을 너비우선탐색을 이용한다. 값이 조건에 벗어나지 않고, 방문을 하지 않았으면 그 값을 큐에 넣어 재귀호출을 통해 그 값을 기준으로 또 너비우선탐색을 한다. 결과의 위치를 찾으면 그 위치가 몇 초후에 찾았는지 visited 배열의 값에 넣어 출력한다. ✏️ 한줄 평 이런 종류의 문제를 너비우선탐색을 이용하여 풀 수 있구나를 제대로 알게 된 문제였다. 코드

[JAVA] 백준 1149번 - RGB거리

문제 1149번: RGB거리 [ 해결순서 ] 처음엔 첫 줄의 최소 값을 구하고 다음 줄에는 그 줄의 색깔을 제외한 색깔 중 최소 값을 구하려 했다. 그러면 전체에서의 최소 값을 구하지 못함. 결국 전체 경우의 수를 구해야 함 해당 값을 구하려면 현재의 색깔을 제외한 색깔의 행과, 직전의 열을 값들을 비교해서 작은 값에 + 현재의 비용을 더함. (비용을 더하지 않는 실수를 함) 마지막 줄의 색깔 중 가장 작은 값이 정답 점화식 dp[i][red]=Math.min(dp[i-1][blue],dp[i-1][green])+cost[i][red] //빨간 색 이라면, 그 전줄의 빨간 색이 아닌 파랑, 초록 중 작은 값 + 해당 값의 가격 ✏️한줄평 DP 문제를 더 자주 풀어 익숙하게 해야겠다. 코드