수학

알고리즘 문제) BOJ 14923. 미로탈출 링크 : https://www.acmicpc.net/problem/14923문제 요약N*M 미로가 존재출발위치는 (Hx,Hy)이며, 미로 탈출 위치는 (Ex, Ey)이다미로에는 벽이 존재하며, 통과가 불가능하다그러나, 한번 마법을 부리면 벽을 허물 수 있다미로를 탈출 할 수 있는지 알아보고, 가능하다면 최단 경로 D를 출력해라시간 제한1초입력미로 크기 N * M2 ≤ N ≤ 10002 ≤ M ≤ 10001 ≤ Hx, Hy, Ex, Ey ≤ 1000출발위치랑 탈출위치는 다름행렬 정보가 주어짐다0 : 빈공간1 : 벽출력최단 경로 D 출력해라탈출 할 수 없다면 -1출력접근법최단 경로 알고리즘 BFS를 사용해 접근BFS를 돌리며 방문체크 할 때, 현재 마법을 썼는냐,..

알고리즘 문제) BOJ 16197. 두 동전 링크 : https://www.acmicpc.net/problem/16197문제 요약N*N 보드와 4개의 버튼이 존재보드 위에는 동전이 하나씩 놓여져 있으며, 두 위치는 다르다버튼은 왼쪽, 오른쪽, 위, 아래 4가지가 존재이때, 버튼을 누르면 해당 방향으로 두 동전이 동시에 이동한다동전이 이동하려는 칸이벽 → 이동 X경계 밖 → 바깥으로 떨어짐그 외에는 해당 위치로 이동(이미 동전이 있는 경우에도 이동)두 동전 중 하나만 보드에서 떨어뜨리려면 최소 몇 번 클릭??시간 제한2초입력보드 세로 크기 N, 가로 크기 M1 ≤ N, M ≤ 20N개의 줄에 보드 상태가 주어짐o : 동전. : 빈칸# : 벽동전의 개수는 항상 2개출력두 동전 중 하나만 보드에서 떨어뜨리기 ..

알고리즘 문제) BOJ 1940. 주몽 링크 : https://www.acmicpc.net/problem/1940문제 요약갑옷을 만드는 재료들은 각각 고유 번호를 갖고 있음두 개의 재료의 고유 번호를 합쳐서 M이 되면 갑옷이 만들어짐N개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지 구해라시간 제한2초입력재료 개수 N1≤N≤15000갑옷을 만드는데 필요한 수 M1≤M≤1000만N개의 재료들의 고유 번호가 주어짐고유 번호 : 10만 이하 자연수출력갑옷을 만들 수 있는 개수접근법완전 탐색으로 생각하기2중 for문으로 재료 두 개 선택해서 M이 되는 개수를 고른다어차피 다 다른 고유 번호가 주어지기 때문에 특정 숫자가 무언가와 더해서 M이 될 수 있는 경우는 단 한가지 뿐이다.투포인터 적용하기먼저..

알고리즘 문제) BOJ 18111. 마인크래프트 링크 : https://www.acmicpc.net/problem/18111문제 요약세로 N, 가로 M 크기의 집터가 있을 때, 땅의 높이를 모두 일정하게 바꾸려고 함이를 위해 다음 두 종류의 작업을 할 수 있음좌표 (i,j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.인벤토리에서 블록하나를 꺼내 좌표 (i,j)의 가장 위에 있는 블록 위에 놓는다.1번 작업은 2초, 2번 작업은 1초가 걸림땅 고르기 작업에 걸리는 최소 시간과 그 때 땅의 높이를 출력인벤토리에는 B개의 블록이 들어 있음땅의 높이는 음수가 될 수 없음시간 제한1초입력N M B1≤M,N≤5000≤B≤6.4*1000만N개의 줄에 각각 M개의 정수로 땅의 높이가 주어짐땅의 높이는 256보..

알고리즘 문제) BOJ 1018. 체스판 다시 칠하기 링크 : https://www.acmicpc.net/problem/1018문제 요약M*N 크기 보드검정색 또는 흰색 칸으로 칠해져 있다이 보드를 잘라서 8*8 크기의 체스판을 만들려고 함체스판은 검,흰이 번갈아 칠해져야 함즉, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져야 함체스판을 칠하는 경우는 총 두 종류 → 맨 왼쪽 위가 흰 또는 검8*8크기의 체스판으로 잘라낸 후 몇 개의 정사각형을 다시 칠해서 체스판을 만들려고 할 때 칠해야할 정사각형 최소 개수 구하라시간 제한1초입력N M8≤N,M≤50N개의 줄에는 보드의 각 행의 상태가 주어진다B: 검은색W: 흰색출력다시 칠해야 하는 정사각형 개수 최솟값?접근법완전 탐색으로 생각하기(0,0)부터 8..

알고리즘 문제) BOJ 14476. 최대공약수 하나 빼기  14476번: 최대공약수 하나 빼기첫째 줄에 정수의 개수 N (4 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. 각각의 수는 20억을 넘지 않는 자연수이다.www.acmicpc.net문제 요약N개의 정수 중 임의의 수 K를 뺐을 때, 나머지 N-1의 최대공약수가 가장 커지는 것을 찾는 프로그램 찾기이때 최대공약수는 K의 약수면 X시간 제한2입력정수의 개수 N(4≤N≤1,000,000)N개의 수가 주어짐(20억 이하 자연수)출력정수 하나를 빼서 만들 수 있는 가장 큰 최대공약수와 수 출력정답이 없다면 -1 출력접근법8 12 24 36 488 = 1 2 4 88 12 20 32 36숫자 K 하나하나 빼가..

알고리즘 문제) BOJ 15711. 환상의 짝꿍   15711번: 환상의 짝꿍환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이www.acmicpc.net문제 요약끈을 이어붙이고 소수인 끈으로 정확히 나눌 수 있다면 환상의 짝꿍환상의 짝꿍인지 판단하기시간 제한1초입력테스트 케이스 T(1≤T≤500)끈의 길이 A, B (1≤A,B≤2조..)출력YES 또는 NO 출력접근법골드바흐의 추측 : 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.3 4 ⇒ 7 : 1 6 / 2 5 / 3 43 5 ⇒ 8 : 1 7 / 2 6 / 3 5 / 4 4약수 구하기 : $\sqrt{10..

알고리즘 문제) BOJ 2004. 조합 0의 개수  2004번: 조합 0의 개수첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다.www.acmicpc.net문제 요약nCr 끝짜리 0의 개수 출력시간 제한2초입력n, m(0≤m≤n≤2*10^9, n≠0)출력nCr 끝짜리 0의 개수 출력접근법0의 개수를 구한다…1000000000의 약수 생각해보기..10의 소인수는 2와 5이다.즉 끝자리 0이 되려면 nCr을 소인수했을때 2, 5가 최소 하나씩 존재해야함0의 갯수가 1개→최대 9개까지 등장할때2와 5의 개수가 각 1개에서 → 9개로 증가…!!!!즉, 이 쌍의 개수가 몇 개인지 찾아야함~!2, 2*2….. 으로 나누면서 2의 개수 구하..

알고리즘 문제) BOJ 6219. 소수의 자격  6219번: 소수의 자격세 정수 A, B, D가 주어진다.www.acmicpc.net문제 요약A..B에서 숫자 D를 포함하는 소수의 개수자릿값에 D가 몇 개 등장????시간 제한2초입력A B D1 ≤ A ≤ B ≤ 4백만B ≤ A + 2백만출력범위 내에서 숫자 D를 포함하는 소수의 개수?접근법그냥 1부터,,,4백만까지 에라토스테네스체 사용해서 소수 판별 미리 기록 하고범위 내에서 자릿값 체크하면서 D가 등장하는 횟수 카운트 하기…!!!!D가 등장하는 소수 개수 카운트 하는거야,,, 문제 잘 읽기,,,코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamRead..

알고리즘 문제) BOJ9417. 최대 GCD  9417번: 최대 GCD첫째 줄에 테스트 케이스의 개수 N (1 www.acmicpc.net문제 요약정수 M개가 주어질 때 모든 두 수의 쌍 중 가장 큰 최대공약수 찾기시간 제한1초입력테스트 케이스 N(1테스트 케이스별 양의 정수 M개 주어짐) (1-2^31 ~ 2^31-1출력케이스별 입력으로 주어진 모든 두 수의 쌍의 최대공약수 중 가장 큰 값?접근법7 5 → 5 2 → 3 2 → 2 1125 15 → 110 15 → 95 15 → 80 15 → 65 15 → 50 15 → 35 15 → 20 15 → 15 5 → 10 5125 25 → 100 25 → 75 25 → 50 252개의 쌍을 구하며 모듈려 연산으로 공약수 구하고 최댓값 갱코드import jav..