'📜 코딩테스트' 카테고리의 글 목록 (2 Page)

백준 2579번(DP) : 계단 오르기 (JAVA) 문제 풀이

2021.08.12

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net ✏️ 문제 🔐 문제 해결 문제의 조건을 해석해보면 아래와 같습니다. 계단은 한번에 한칸 또는 두칸을 오를 수 있습니다. 연속된 세 개의 계단을 밟아서는 안됩니다. 1 칸씩 세번 연속 오르면 안된다는 뜻! 마지막 칸은 무조건 밟아야 합니다. 1. 테이블 정의하기 dp[i][j]의 i는 i 번째 계단에 올랐을 때의 최대 점수의 합이 되고, j는 현재까지 몇번을 연속해서 계단을 밟고 왔는지를 뜻합니다. 그렇다면, ..

📜 코딩테스트/BAEKJOON\다이나믹 프로그래밍

백준 9095번(DP) : 1, 2, 3 더하기 (JAVA) 문제 풀이

2021.08.10

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ✏️ 문제 🔐 문제 해결 1. 테이블 정의하기 테이블은 dp[i]를 1,2,3으로 표현할 수 있는 횟수로 설정하겠습니다. 2. 점화식 구하기 먼저 dp[4]는 본문에도 나와있듯이 아래와 같이 총 7가지가 있습니다. 이것을 1, 2, 3으로 나눠서 생각해보자면, 하나의 숫자를 3로 고정하고, 나머지 1을 1, 2, 3으로 조합하는 경우 1 + 3 하나의 숫자를 2로 고정하고, 나머지 2를 1, 2, 3으로 조합하는 경우 1 + 1 + 2 2 + 2 하나의 숫자를 1로 고정하고, 나머지 3을 1, ..

📜 코딩테스트/BAEKJOON\다이나믹 프로그래밍

백준 1463번(DP) : 1로 만들기 (JAVA) 문제 풀이

2021.08.10

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net ✏️ 문제 🔐 문제 해결 다이나믹 프로그래밍은 아래 세가지 순서를 따라서 문제를 풀이합니다. 테이블 정의하기 점화식 찾기 초기값 설정 1. 테이블 정의하기 테이블의 값은 당연히 i의 최소 연산 횟수가 되겠습니다. 2. 점화식 찾기 i를 계산하는 방법은 총 3가지가 있습니다. 2로 나눈 나머지가 0일 경우, 2로 나눈다. 3으로 나눈 나머지가 0일 경우, 3으로 나눈다. 1을 뺀다. i의 최소 연산 횟수를 저장하는 배열을 dp라고 정의할 때, dp[i]의 값은 아래와 같습니다. dp[i] = Math.min(dp..

📜 코딩테스트/BAEKJOON\재귀

백준 1074번 : Z (JAVA) 문제 풀이

2021.07.09

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net ✏️ 문제 🔐 문제 해결 주의! 이 문제는 하나 하나 탐색하여 DFS를 시도하면 시간초과되어 통과할 수 없게 된다. 아래는 시간 초과 받은 풀이..ㅠ 더보기 시간 초과 받은 풀이이다. import java.util.*; import java.io.*; public class Main { static int N, r, c; static int count; static int[][] arr; ..

📜 코딩테스트/BAEKJOON\BFS, DFS

백준 9466번 : 텀 프로젝트 (JAVA) 문제 풀이

2021.07.08

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net ✏️ 문제 🔐 문제 해결 이 문제는 생각보다 간단한데 어렵다. 위 예제 중 하나를 그림으로 표현해보았다. 그림을 보면, (1번, 5번) -> 3번 과 팀을 이루고 싶어한다. 하지만 3번은 혼자 팀을 하길 원한다. 이렇게 되면 1번 5번은 팀을 이룰 수 없게 된다. 또, 2번-> 1번 -> 3번(혼자 팀) 이므로 2번도 팀을 이룰 수 없게 된다. 4번, 6번, 7번은 서로를 가리키고 있으므로 팀이 완성이..

📜 코딩테스트/BAEKJOON\BFS, DFS

백준 2206번 : 벽 부수고 이동하기 (JAVA) 문제 풀이

2021.07.07

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net ✏️ 문제 🔐 문제 해결 예를들어 아래와 같은 5X5 배열이 있다고 해보자 0 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 0 0 0 1 0 그림으로 표시하면 아래와 같을 것이다. 화살표 방향과 같이 시작점(0,0) 에서는 두 가지 방향으로 갈 수 있을 것이다. 하지만 1번으로 벽을 뚫고 간다면, 아래의 문제점에 부딪히게 된다. 도착지점으로 가기 위..