java52

• 

  백준 알고리즘 1912번: 연속합 문제 정보 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 핵심 요즘 많이 풀고 있는 Dynamic Programming, DP 알고리즘으로 문제를 풀이한다 정수 n의 개수가 최대 100,000이기 때문에 연속되는 수들의 합의 최대값을 구할 때 모든 경우의 수를 확인하는 것은 매우 비효율적인 방법이고, 심지어 수가 한개일 수도 있으며 연속되기만 한다면 모든 경우를 고려해야 하기 때문에 더더욱 사용하지 말아야 할 것이다 여기서 사용한 방법은 DP(동적 프로그래밍) 방법인데, 각각의 상태에서의 최대 합을 기록하며 풀이를 진.. 알고리즘/Java 2023. 12. 21.

• 

  백준 알고리즘 2583번: 영역 구하기 문제 정보 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 핵심 그래프 탐색 알고리즘을 사용하여 문제를 풀이하자! 다만, 처음에 고민되었던 부분은 각 영역의 오른쪽 위 꼭짓점의 좌표값을 어떻게 처리하느냐.. 였는데 꼭짓점을 좌표라고 생각하지 말고, 해당 영역을 좌표라고 생각해 보는 것이 도움이 되었던 것 같다 예를 들어 (0, 0)은 왼쪽 아래 꼭짓점이라고 생각하기보다는 첫번째 (왼쪽 아래) 영역이라고 생각하면 map[0][0]은 해당 영역을 나타내는 값이 되는 것이다 간단하게 그림으로 나.. 알고리즘/Java 2023. 12. 14.

• 

  백준 알고리즘: 2636번 치즈 문제 정보 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 핵심 BFS(너비 우선 탐색)을 사용하여 문제를 풀이한다! 이를 사용하는 근거는, 치즈 조각은 한 시간이 지날때 마다 점차 녹아가며 우리가 구해야 하는 것은 모든 경로를 탐색하는 것이 아닌 각자의 위치(공기)에서 녹일 수 있는 치즈를 천천히 녹여가며 모든 치즈가 녹는 데에 걸린 시간과 한 시간 전에 남아있는 치즈 조각을 구하는 것이기 때문이다 사실상 이를 떠올리는 것은 어렵지는 않고, 좀 까다로웠던 것은 (0,0) 부터 맵을 탐색하기 시작하여 0(공기)이면 큐에 추가하고.. 알고리즘/Java 2023. 11. 22.

• 

  백준 알고리즘: 9466번 텀 프로젝트 문제 정보 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 핵심 DFS(깊이 우선 탐색)으로 순환을 이루는 학생들을 찾아야 한다 visited 배열을 사용하여 방문한 학생들을 재방문하지 않도록 처리해 주어야 하며 재귀적으로 노드들을 탐색할 때, 해당 부분집합에 순환되는 부분이 존재할 수 있으므로 이를 골라내어 카운팅해주는 방식이 요구되는 것 같다 처음에는, 재귀 호출로 구한 여러명의 학생들 중 일부만 순환 관계에 놓여있다고 했을 때 순환을 이루는 학생들에 대해서만 방문 표시를 해주고, 나머지 학생들에 대해서는 방문.. 알고리즘/Java 2023. 11. 15.

• 

  백준 알고리즘: 7576번 토마토 문제 정보 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 핵심 역시 이전 문제와 비슷한 BFS(너비 우선 탐색)을 활용하여 풀이하는 문제이다 이 문제에서 하루가 지나면 익은 토마토의 상하좌우의 익지 않은 토마토들은 익은 토마토로 변하게 되는데, 모든 익지 않은 토마토가 익은 토마토가 될 때까지의 최소 날짜를 출력하는 것이다 하지만, 1. 익지 않은 토마토(0)가 모두 익은 토마토(1)로 변했음을 어떻게 파악할지 2. 익은 토마토로 변했을때 최소 날짜는 어떻게 카운팅하는 것이 좋을지 이 두가지.. 알고리즘/Java 2023. 11. 14.