알고리즘/백준 검색 결과

해당 글 67건

[백준] 1039번 교환 (자바)

https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 교환 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 16687 3698 2760 22.549% 문제 0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다. 1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다. 위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작..
알고리즘/백준 2023. 8. 18. 15:37

[백준] 17837번 새로운 게임 2 (Java)

https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 단순 구현 문제 흰색, 빨간색은 문제가 안되는데 파란색일 경우, 체스말이 멈춰있는 경우와 반대로 방향을 틀었을 때 막혀있는 경우 등등.. 을 생각해 주고 구현해야한다. 그리고 체스말이 움직일 때 위에있는 모든 체스말의 위치 갱신을 하지 않아서 조금 헤맸었다. 그 외에는 step을 따라가면서 천천히 구현하면 어렵지 않은 문제인거 같다. 혹시나 1000번 이전에 시간초과가 날까 걱정했지만 체스말이..
알고리즘/백준 2023. 8. 7. 21:20

[백준] 7579번. 앱

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 다이나믹 프로그래밍 / 배낭 문제 제한된 비용이 주어졌을 때 최대로 얻을 수 있는 메모리 를 DP 로 해결하면 된다. 배낭 문제와 거의 동일하다. dp[i][j] = i 번째 앱 까지 포함했을 때, j 의 비용으로 얻을 수 있는 메모리 dp[i][j] = Max ( dp[i-1][j] , dp[i-1][j-cost[i]] + m[i] ) i 번째 앱을 끄지 않았을 때 / i 번째 앱을 껐을 때 를 ..
알고리즘/백준 2023. 6. 8. 19:06

[백준] 11066번. 파일 합치기 (Java)

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 문제 N 개의 파일이 주어졌을 때, 파일을 어떠한 순서로 조합했을 때 가장 최소의 값으로 합칠 수 있는지 구하는 문제 풀이 다이나믹 프로그래밍 점화식 dp[i][j] = i 번째 파일부터 j 번째 파일 까지를 합쳤을 때의 최소값 dp[i][j] = dp[i][k] + dp[k+1][j] + sum[i][j] ( 마지막에 모든 파일 값을 더하기 때문에 sum 은 항상 들어감 ) 3중 루프를..
알고리즘/백준 2023. 6. 8. 18:03

[백준] 2749번. 피보나치 수 3 (Java)

https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 / 풀이 n 번째 피보나치 수열을 출력하는 문제다 다만 n이 자료형으로 처리할 수 없을정도로 크기 때문에 숫자를 줄여야 하는데 여기서 사용되는 것이 '피사노 주기' 이다 ( 참고 : https://chamggae.tistory.com/207 ) 여기서 m 값은 1,000,000 이 되고 피사노 주기를 풀었던 코드에 입력해도 되고 n > 2라면, k(10n) = 15×10(n-1) 을 사용해도 된다. 피보나치 수열이 1,500,000 마다 주기를 이루기에 입력된 n 을 나눠..
알고리즘/백준 2023. 6. 7. 22:11

[백준] 9471번 피사노 주기

https://www.acmicpc.net/problem/9471 9471번: 피사노 주기 첫째 줄에 테스트 케이스의 개수 P가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다. www.acmicpc.net 문제 : m 이라는 숫자가 주어졌을 때 피보나치 수열에서 m 으로 나누었을 때의 나머지 값이 수열을 이룬다고 한다. 이 때 이루는 수열의 크기를 구하는 문제 수열 시작이 1, 1, ... 으로 시작하므로 다음 나머지 값이 1, 1이 되는 시점을 찾으면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; publ..
알고리즘/백준 2023. 6. 7. 21:51

[백준] 1655번. 가운데를 말해요 (Java)

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 입력 값이 계속 주어질 때 해당 숫자의 가운데 값을 출력하는 문제 우선순위 큐를 2개 사용해서 하나는 내림차순(max heap), 하나는 오름차순 (min heap) 으로 사용해서 해결했다. 풀이 1. 우선 주어진 입력 값을 숫자에 상관없이 큐에 번갈아가면서 추가한다. 2. 출력은 max heap 의 루트 값을 출력하기에 max heap 에 있는 값은 min heap 에 있는 값보..
알고리즘/백준 2023. 6. 7. 20:06

[백준] 1303번 전쟁 - 전투 (Java)

https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 풀이 > 그래프 탐색에서 큐를 사용해서 BFS 로 해결 가능하다. W, B 각각 병사에 대해 탐색하고 방문 표시를 해주면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.uti..
알고리즘/백준 2023. 3. 9. 16:29