Bull

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);..

개념 그래프는 데이터 구조의 하나로서, 여러 개의 정점(Vertex)과 이들을 연결하는 간선(Edge)으로 구성된다. 그래프는 사회 네트워크, 인터넷 연결, 도로망 등 다양한 시스템을 모델링하는 데 사용된다. 그리고 간선을 나타낼 때는 단방향, 양방향을 고려할 수 있다. 가장 일반적인 두 가지 방법은 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix)을 사용하는 것이다. 예시 위와 같은 그래프는 다음과 같이 설명할 수 있다. (양방향이라 할때) $0$ → 1,4 0은 1,4로 연결되어있다. $1$ → 0,2,3,4 1은 0,2,3,4와 연결되어있다. $2$ → 1,3 2는 1,3과 연결되어있다. $3$ → 1,2,4 3은 1,2,4와 연결되어있다. $4$ → 0,1,3 ..

설명 뤼카의 정리(Lucas' Theorem)는 조합론에서 사용되는 중요한 정리로, 특히 모듈로 $p$ ($p$가 소수일 때)의 이항계수를 계산할 때 유용하다. 이 정리는 프랑스의 수학자 에두아르 뤼카(Édouard Lucas)에 의해 발견되었다. 공식 뤼카의 정리의 핵심은 이항계수 $\binom{n}{k}$ (n과 k는 양의 정수, $\binom{n}{k}$는 n 위에 k를 쓴 이항계수를 의미)가 소수 $p$에 대하여 모듈로 $p$로 나눈 나머지를 구할 때, $n$과 $k$를 $p$진법(베이스 p)으로 확장한 후 각 자릿수를 별도로 이항계수 계산에 적용하여 최종 결과를 모듈로 $p$로 얻을 수 있다. 이를 수학적으로 표현하면, $n$과 $k$를 $p$진법으로 표현했을 때, $(n = n_0 + n_1p..

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 >>..

https://leetcode.com/problems/two-sum/description/ LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 class Solution { public: vector twoSum(vector& nums, int target) { } }; input으로 nums 벡터와 target 을 받은 후, nums 벡터에 있는 원소들 중..