본문 바로가기

알고리즘 문제87

[백준] 1929번: 소수 구하기 (Java) 1. 문제설명M이상 N이하의 소수를 모두 출력하는 문제이다.시간 제한: 2초메모리 제한: 256MB 2. 접근 방식소수: 1과 자기 자신만을 약수로 가지는 수에라토스테네스의 체 알고리즘을 사용한다. (https://propercoding.tistory.com/182)2부터 $\sqrt{N}$까지의 소수의 배수를 제거하여 소수를 판별한다.boolean 배열을 사용하여 N까지 수의 소수 여부 저장한다. (false: 소수, true: 합성수)M부터 N까지 소수인 수를 출력한다. 3. 틀린 이유for(int i=M; i 약수: 1,2,3,4,6 cnt++; if(i / j != j) { // j가 약수이면 i/j도 약수 .. 2024. 10. 3.
[백준] 7579번: 앱 (Java) 1. 문제설명스마트폰의 메모리는 메모리 부족 상태를 방지하기 위해 활성화 되어 있는 앱들 중 몇 개를 선택하여 메모리로부터 삭제하는 과정을 수행한다.(비활성화)현재 N개의 앱이 활성화 되어 있을 때, 앱 $A_i$는 각각 $m_i$ 바이트만큼 메모리를 사용한다. 앱 $A_i$를 비활성화한 후 다시 실행시키면, 추가적으로 드는 비용은 $c_i$ 이다. 새로운 앱을 실행시키면 추가로 $M$ 바이트의 메모리가 필요하고, 현재 활성화 되어 있는 앱 중 몇 개를 비활성화하여 M 바이트 이상의 메모리를 추가로 확보해야 한다.비활성화 했을 경우의 메모리 $M$ 바이트를 확보하는 비용 $c_i$ 의 최소 비용을 구하는 문제이다.시간 제한: 1초메모리 제한: 128MB 2. 접근 방식DP 방법을 사용한다. (Knapsa.. 2024. 10. 1.
[백준] 2138번: 전구와 스위치 (Java) 1. 문제설명N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져있거나 꺼져있는 상태이다. i번 스위치를 누르면 i-1, i, i+1 의 세 개의 전구 상태가 바뀐다. 현재 상태와 반대로 바뀐다.N개의 전구들을 만들고자 하는 상태로 만들기 위해 스위치를 최소 몇 번 누르면 되는지 구하는 문제이다.시간 제한: 2초메모리 제한: 128MB 2. 접근 방식그리디 알고리즘을 사용한다.첫 번째 전구부터 순차적으로 처리한다.각 단계에서 현재 전구의 왼쪽 전구가 목표 상태와 다르면 현재 스위치를 누른다.첫 번째 스위치를 누르는 경우(curA)와 누르지 않는 경우(curB)를 고려한다.첫 번째 스위치의 상태가 이후의 모든 결정에 영향을 미치기 때문.두 번째 전구부터 현재 상태와 목표 상태를 비교하며 진행한다.i-1.. 2024. 10. 1.
[백준] 21941번: 문자열 제거 (Java) 1. 문제설명지우고 싶은 문자열 S와 지울 수 있는 문자열 A1, A2, …, AM이 주어진다. 문자열 Ai 들은 각자 Xi라는 점수를 가진다. 문자열 S를 삭제 연산을 이용하여 모두 제거하려고 한다.삭제 연산 두 가지문자열 S의 부분 문자열 중에 문자열 Ai 가 존재한다면 해당하는 부분을 지우고, Xi 만큼의 점수를 얻는다. (여러 부분 존재해도 한 번만 지운다.)문자열 S에서 문자 하나를 지우고 점수를 1점을 얻을 수 있다.삭제 연산을 이용하여 문자열 S를 지우려고 할 때 얻을 수 있는 최대 점수를 구하는 문제이다.시간 제한: 1초메모리 제한: 512MB 2. 접근 방식DP 방법을 사용한다.문자열 S의 각 위치에 대해 그 위치까지의 최대 점수를 저장하는 1차원 dp 배열을 사용한다.각 위치에서 고려하.. 2024. 10. 1.
[백준] 17836번: 공주님을 구해라! (Java) 1. 문제설명용사는 (N, M) 크기의 성 입구 (1, 1)로 들어왔다. 성의 여러 군데는 마법 벽이 세워져있고, 용사는 마법 벽을 통과할 수 없다. 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야 한다.저주에 걸린 공주는 T시간 이내에 용사를 만나지 못하면 돌로 변하게 된다. 용사는 한 칸을 이동하는 데 한 시간이 걸리고, 상하좌우로 이동할 수 있다.성에는 전설의 명검 "그람"이 숨겨져 있고, 그람을 구하면 마법의 벽이 있는 칸일지라도, 벽을 부수고 그 공간으로 갈 수 있다. "그람"은 성의 어딘가에 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있다.용사가 공주님을 안전하게 구출할 수 있는지, 얼마나 빨리 구할 수 있는지 구하는 문제이다.시간 제한: 1초메모리 .. 2024. 9. 30.
[백준] 11048번: 이동하기 (Java) 1. 문제설명NxM 크기의 미로가 있고, 가장 왼쪽 윗 방은 (1, 1), 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 방문하는 방의 사탕을 모두 가져갈 수 있다. 준규가 가져올 수 있는 사탕의 최댓값을 구하는 문제이다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식DP 방법을 사용한다.dp 배열(2차원 배열)에 해당 칸까지 이동했을 때 얻을 수 있는 사탕의 최댓값을 저장한다.DP 점화식: 현재 칸에 도달할 수 있는 세 가지 경로(윗칸, 왼쪽칸, 왼쪽 위 칸)에서 가장 많은 사탕을 얻는 경로를 찾는다.도착점(n-1, m-1)에서.. 2024. 9. 24.
[백준] 17779번: 게리맨더링 2 (Java) 1. 문제설명재현시는 NxN 크기의 격자로 나타낸다. 각 칸은 구역(r, c)을 의미한다. 구역을 다섯 개의 선거구로 나눠야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다.시간 제한: 1초메모리 제한: 512MB 2. 접근 방식가능한 모든 (x, y, d1, d2) 조합을 탐색하여 각 구역을 나누기 위한 조건을 만족하는지 확인한다.경계선에 따라 5개의 구역을 나눈다. 경계선(5구역)을 먼저 설정한 뒤, 각 구역(1~4구역)의 인구를 계산한다.각 구역별 인구 차이를 계산한 뒤, 그 차이의 최소값을 갱신한다. 3. 최종 코드import java.io.*;import java.util.*;public class Main { static int n; static boolean[].. 2024. 9. 20.
반응형