공부공간

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 당연히 푼문제인줄 알았었는데 C++로 풀었던문제여서 자바로 다시풀었다. 전체 먹을수있는 상어 후보(?)의 관리는 우선순위큐에관리하여 logN에 찾자. 한스텝마다, 우선순위큐에 먹을수있는 상어들을 뽑고, 그 상어까지의 최단거리 (BFS) 를통하여 처리한후, 그 상어가 있던 자리를 기준으로 다시 힙을 정렬한다. 이 과정을 더이상 먹을수 있는 상어가 없을때까지 진행한다. import java..

https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길 www.acmicpc.net 역시 이어서 투포인터 유형1번문제이다. https://algorithmstudy-mju.tistory.com/120 BOJ - 2003 )..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 www.acmicpc.net 투포인터를 이용해 연속한 소수의 합으로 목표숫자를 만들수 있는지? 없는지 확인하는 문제이다. 만들어야하는 숫자를 N이라고 할때에, N..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다. www.acmicpc.net 두 용액은 이전 포스트 https://algorithmstudy-mju.tistory.com/120 BOJ - 2003 ) 수들의 합 2 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 위상정렬과 다이나믹프로그래밍(약간?)이 결합된 문제이다. 빌드와 시간이라는 개념이 등장하여 1 ->2 ->3 , 11->10->3 의 노드 연결정보에서 3의 진입차수가 0 이될때 1->2 / 11->10의 비용중 큰것을 골라야지 다른 빌드에서 걸리는 시간을 커버하면서 진행 할 수 있다. 중간중간 첫 건물이 목표건물인 경우와같이 예외사항을 처리해주면서 진행하면 풀리는 문제.. 위상정렬을 DF..

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 투포인터 알고리즘 (Two-Pointer Algorithm)은 배열에 특정 구간에 대해 접근하여 처리할 경우, 시간복잡도를 O(n^2) 에서 O(n) 까지 단축하는 알고리즘이다. 사실 알고리즘 자체는 어렵지 않다. 문제에서 원하는 특정 값을 m이라할때 배열의 인덱스를 가리키는 두개의 포인터변수를 선언한다. 그리고 특정 값보다 크면 첫번째 포인터변수를 증가시키고, 작으면 ..

https://www.acmicpc.net/problem/2234 2234번: 성곽 문제 대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로� www.acmicpc.net 주어진 맵에서 성곽의 크기를 구하면서 벽하나를 제거해서 합친 면적중 가장 큰 값을 찾는 문제이다. 성곽의 크기를 구할때 이미 각 면적의 합을 구하고 인접여부만 CHECK배열로 확인해 준다음 인접해있다면, 두 면적을 합친값 중 가장 큰 값을 답으로 선택한다. 다음 BFS진행시에 비트연산을 해주어야하는 신박한 문제 :) import java.io.BufferedReader; import java.io.Inpu..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 외판원순회(TSP)문제는 한지점에서 출발해 모든 노드를 거치고 다시 시작위치로 돌아오는 문제를 말한다. 그 중 최소 비용을 출력하는 것이 이번 외판원문제2이다. 백트래킹을 이용하여 미리구한값보다 크다면 더이상진행하지않는다. 문제에서도 알수 있듯이, MAP[I][J]값이 0이면..