Bull

문제1019: 책 페이지N이 36이라면 1~36페이지까지 즉 1,2,3,...35,36에 나오는 모든 숫자를 다 세는 것이다.설명각 자리 수 마다 검사하여 모든 경우의 수를 구한다. 1234라는 N이 주어졌을 때 1,2,3,4 모두 검사하는 것이다.1의 자리 수를 검사할 때 1의 자리를 0~9까지 모두 바꿔보는 것이다. 그리고 일의 자리를 제외한 나머지 부분을 보는 것이다.주석을 보고 숫자 디버깅으로 이해하는 게 편할 것이니 포괄적인 설명은 포기한다. (포괄적으로 말하기가 어려워서)1204일 때 0104~1204 (0004는 불가, 다른 숫자 과정에서 겹침.)1214일 때 0014~12141224일 때 0024~12241234일 때 0034~1134 | 1230,1231,1232,1233,12341244..

Baekjoon 2143문제숫자 T가 주어지고 배열 A와 B가 주어진다. 여기서 부 배열이라는 개념이 있는데 A[i], A[i+1], ..., A[j] 와 같이 연속된 배열을 부배열이라고 한다. A[13]까지라고 한다면 A[7], A[8], A[9], ... A[13] 도 가능하고 A[2], A[3]도 부 배열이라고 할 수 있다. 문제는 A의 부 배열과 B의 부 배열이 합해서 T가 되는 경우의 수를 구하는 것이다.예를 들어 본문의 내용과 같이 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.T(=5) = A[1] + B[1] + B[2] = A[1] + A[2] + B[1] = A[2] + B[3] = ..

Baekjoon 1806문제제목처럼 부분합을 구하는 문제이다.1,2,3,4 배열이 있을 때, 1 2 3 4 1 2 1 3 1 4 2 3 2 4 3 4 1 2 3 1 2 4 2 3 4 1 2 3 4와 같이 모든 조합이 가능 한 원소의 합이다.이 집합의 원소들의 합이 S 이상이 되는 것 중 원소가 연속되어 있고 짧은 것을 찾는 것이다.입력첫 번째 줄에 수열의 길이 N과 부분합 S가 주어진다. (10 ≤ N , 0 )두 번째 줄에 길이 N인 수열이 주어집니다. 수열의 각 원소는 10,000 이하의 자연수이다.출력합이 S 이상이 되는 가장 짧은 부분 수열의 길이를 출력합니다. 만약 그러한 부분 수열이 없다면 0을 출력한다.아이디어이 문제를 해결하기 위해 슬라이딩 윈도우(Sliding Window) 기법을 사용한..

https://www.acmicpc.net/problem/13913문제0 1 2 3 ... 100000 으로 이루어진 일자형 길에 x+1, x-1 2*x로 움직일 수 있다고 했을 때 목적까지 가는 최단 경로를 구하는 문제이다.아이디어단순 BFS문제이다. 하지만 visit으로 최단 경로보다 이후에 간 인덱스는 방문처리하여 다시 방문하지 않도록 한다. 여기까지는 스스로 짰지만 이후에도 메모리 초과가 걸렸다.왜냐하면 최단 경로를 vector를 사용하여 리스트처럼 저장을했는데이는 상당히 많은 배열을 큐에 저장하기 때문이다.단순하게 생각해보면 벡터의 크기가 1에서 100000까지인데 방문한 인덱스를 제외하면 최대 1에서 33333까지 3개씩 저장해 나갈 것이다.(1,2,2,2,3,3,3,4,4,4....) 그러면..

https://www.acmicpc.net/problem/9019문제원문에 나오는 D, S, L, R 연산을 구현하여 A, B입력 시 A→B가 될 때 까지 어떤 연산을 해야하는 지 출력해야 하는 문제이다.아이디어BFS를 통해 D, S, L, R, DD, DS, DL, DR, SD, SS, SL, SR, ...처럼 레벨 단위로 숫자를 확인한다. 여기까진 OK. 하지만 문자열의 제한이 없기 때문에 DSLDLSDRRSRSDSL... 같이 긴 숫자는 Queue에 메모리초과가 발생한다.숫자는 0~10000미만이다. 이것을 활용하여 10000까지 visit을 확인하여 이미 확인한 숫자는 확인하지 않는다. 또한 자료형에 대해서도 short로 바꿔줄 수 있다. int를 쓰면 틀리는 지는 확인해보지 않았지만 일단 sho..

https://www.acmicpc.net/problem/14502문제문제의 연구소에 벽(1)을 최대 3개 설치가 가능하고 바이러스(2)는 벽이 막혀있는 곳 까지 퍼질 수 있다. 이러한 조건에서 바이러스가 퍼졌을 때, 안전한 장소(0)를 얼만큼 확보할 수 있는 지 출력하는 문제이다.아이디어BFS를 통해 바이러스를 퍼뜨린다. 벽을 최대 3개 설치할 수 있는 로직은 행열 순으로 벽을 하나씩 설치했다가 해제했다가 순서대로 모든 경우의 수를 구한다. 바이러스가 퍼진 상태 + 벽이 최대 3개가 설치된 상태에서 최대 안전한 장소가 얼마나 확보됐는지 비교하며 max값을 구한다. 2 0 0 0 1 1 00 0 1 0 1 2 00 1 1 0 1 0 00 1 0 0 0 0 00 0 0 0 0 1 10 1 0 0 0 0 0..

https://www.acmicpc.net/problem/2206문제원문을 보면 알 수 있듯이, 왼쪽 위 기준에서 오른쪽 아래로 가는데 벽(1)을 한 번만 깰 수 있고 다음 부터는 깰 수 없다. 그러한 제약사항이 있는 상태에서 최단 거리를 구하면 된다.아이디어BFS를 이용하는데 Queue에 들어가는 정보가 (x,y)와 벽을 깬 적이 있는지에 대한 boolean이 들어가면 된다. code#include #include #include using namespace std;const int MAX = 1000; // 그리드 최대 크기// (-1, 0) (0, 1) (1, 0) (0, -1) 네 방향 이동int dx[] = {-1, 0, 1, 0}; // 방향 배열: x 좌표int dy[] = {0,..

https://www.acmicpc.net/problem/1987문제좌표의 크기가 주어지고, (1,1)부터 시작하는데 같은 알파벳을 만나면 안될때 까지 상하좌우로 움직일 시 최대한 많이 갈 수 있는 칸은 몇인지 찾는 문제이다.아이디어DFS와 백트래킹을 이용한다.인접한 상하좌우 좌표를 확인하여 기록된 알파벳이 없으면 DFS를 호출한다. 여기서 백트래킹을 추가하여 DFS를 통해 visited(알파벳)을 기록하는데 갈수 있는 곳 까지 간 후 다시 visited를 해제하는 방식을 이용한다.위 GIF는 문제의 예제로 백트래킹과 DFS가 어떻게 동작하는 지 그림판으로 나타내보았다. H-A에서H-A-D-G-J-FH-A-J-G-DH-A-J-F-D의 DFS가 적용되고 H-F에서H-F-J-A-D-GH-F-J-G-D-AH-..

https://www.acmicpc.net/problem/1707 문제이분 그래프란?그래프 이론에서 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다. 쉽게 말해서 어느 정점을 선택했을 때 간선을 통해 어디로 가든 RBRBRB...로 반복되어야 한다. (RED, BLUE) 이것을 풀어서 생각하면 두 집합으로 나눌 수 있는 그래프를 말한다. 즉 왼쪽이 있는 그래프를 모양만 좀 다르게 위치를 옮겨주면 오른쪽 그림이나 사실 똑같은 건데, 이런식으로 오른쪽 그림으로 만든 후 선 그어서 두 집합으로 나뉘어지면 그게 이분 그래프다. 아이디어BFS, DFS 방식으로 모두 풀이가 가능하다. ..

https://www.acmicpc.net/problem/16928스크래핑 문제로 open graph tag가 안뜸.문제글보단 그림으로 보면 편할 것이다. 1~100까지의 인덱스를 가진 Grid가 있지만 1차원인 배열로 봐도 상관없다. 뱀을 만나면 다시 내려가야 되고 사다리를 발견하면 껑충 뛰어넘어갈 수 있다.  아이디어①BFS1부터 1~6자리까지 모두 시행 후, BFS방식을 사용해 지름길을 통하거나 뱀을 피해 먼저 100에 도착하는 경우를 채택한다. visit[]을 통해 방문했던 인덱스인지 확인하고 아니라면 Queue에 push한다. queue에 들어간 좌표와 카운트는 level순으로 들어가고 순차적으로 빠질 수 있어 BFS가 된다. Code#include #include using namespace ..

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 요구사항 ① 다이나믹 프로그래밍 ② 행렬 곱 ③ MOD 1000으로 나타내기 ④ 분할정복 (시간복잡도 단축) 코드 #include #include #include #define MOD 1000 using namespace std; typedef long long ll; int dp[5][5][38]; int result[5][5]; void init() { cin.tie(NULL); cout.tie(NULL);..

https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 요구사항 ① 첫 째줄, 두 째줄에 시작하는 숫자(Min)와 끝나는 숫자(Max)를 적어준다. ② Min이상 Max이하의 숫자 중 소수들의 합과 최솟값을 구해준다. ③ 만약 소수가 없으면 -1을 출력한다. 주의사항 - 코드 #include #include using namespace std; int main() { int min, max; int sum = 0; int prime_m; cin >> min >>..