쫑쫑이의 블로그

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 가운데 값을 기준으로 왼쪽에 최대 힙, 오른쪽에 최소 힙을 만들어주고 두 힙의 사이즈가 같거나 왼쪽이 1 더 크게 만들어서 왼쪽의 peek 값을 출력값에 넣어준다 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { Buffe..

https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 자신보다 작은 수들의 모든 약수들의 합을 구해야하므로 누적합으로 계산한다 약수 계산은 에라토스테네의 체를 사용하여 작은 수부터 시작하여 배수들을 찾아서 값을 더해준다 에라토스테네스의 체.gif 간단한 예시로 1부터 시작해서 일반화를 하면 배열[1]에 배열[0] 더하기, 1의 배수에 모두 1추가 배열[2]에 배열[1] 더하기, 2의 배수에 모두..

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 바이트를 확보하라는 문제라서 바이트를 가지고 dp를 만들어볼까 했는데 범위가 10,000,000까지라서 100 x 10,000,000 시간복잡도도 문제인데 공간복잡도도 문제가 생길 정도로 크다 (int 기준 약 4GB) 그래서 비용을 이용하여 dp로 풀기로했다 범위가 100까지라서 100 x 100 1만이면 여유있게 풀 수 있다 바이트와 비용을 입력 받은 후 반복문으로 비용이 0이면 무조건 종료시키고 확..

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 입력값이 오름차순으로 정렬된 배열이므로, 왼쪽 끝과 오른쪽 끝값을 조건에 따라 하나씩 늘리거나 줄여가면서 0과 가장 가까운 값을 저장하고 출력한다 음수도 나올 수 있으니까 더했을 때 음수면 왼쪽값을 늘리고, 양수면 오른쪽 값을 줄인다 import java.awt.*; import java.io.*; import java.util.*; public class Main { public stati..

https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 구현 문제이므로, 시키는대로 하면 된다!!! 문자를 전부 숫자로 바꿔서 배열을 만들었고, 마지막에 키를 받을 때 97씩 빼서 0 부터 26 사이의 가진 키들의 배열을 만들어줬다 42는 벽, 46은 빈 공간이다 모서리 순회하면서 조건에 만족하면 bfs로 탐색한다 42이거나 방문 했으면 리턴 1) 46이면 bfs 큐에 추가 (코드 내부에는 판별하는 조건문 없음) 2) 97보다 크면 키 추가하고 bfs 큐에 추가하..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 입력을 받고 B는 가중치를 주면서 A의 다음에 나올 수 있는 배열에 추가한다 학생들 중에서 가중치가 0인 인덱스를 큐에 넣고 큐에서 하나씩 빼면서 다음에 나올 수 있는 배열 반복문으로 돌면서 가중치 빼주고 가중치 0인 인덱스를 큐에 넣는 것을 반복한다 import java.io.*; import java.util.*; public class Main { ..