백준 알고리즘2

• 

  백준 알고리즘: 2579번 계단 오르기 문제 정보 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 핵심 DP(Dynamic Programming) 을 활용하여 풀이하여야 함 - Top-Down 풀이 (Recursive) - Bottom-Up 풀이 (반복) 먼저 풀이하기 전에, 문제의 특성을 분석해 보았다 1. 한번에 한 계단 혹은 두 계단을 오를 수 있음 2. 연속으로 한 계단을 세번 오를 수 없음 3. 마지막 계단을 반드시 밟아야 함 Specification dp[i]: 규칙을 지키며 i번째 계단을 밟았을 때의 최대값 scores[i]: i번째 계단을 밟았을.. 알고리즘/Java 2023. 10. 26.

• 

  백준 알고리즘 2667번: 단지번호붙이기 문제 정보 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 핵심 DFS, 백 트래킹 알고리즘을 사용하여 풀이하는 문제 5= 0 && col < size); } } NxN 배열에서 왼쪽 가장 위(0,0) 위치부터 오른쪽 가장 아래(N-1, N-1)까지 DFS를 통하여 인접한 위치로의 깊이 우선 탐색을 하여 지도의 값이 1이면 visited를 true로 만들어 주며, 해당 위치에서 다시 깊이 우선 탐색을 실시한다 한번 탐색할 때마다 count를 계속 올려주고, 계산이 끝났다면 이를 countList 리스트에 넣어 .. 알고리즘/Java 2023. 10. 23.