Bull

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 벡터에 있는 원소들 중..

https://www.acmicpc.net/problem/1408 1408번: 24 도현이는 Counter Terror Unit (CTU)에서 일하는 특수요원이다. 도현이는 모든 사건을 정확하게 24시간이 되는 순간 해결하는 것으로 유명하다. 도현이는 1시간 만에 범인을 잡을 수 있어도 잡지 않는 www.acmicpc.net 요구사항 ① 두 시간을 입력 받는다 (00:00:00형식) ② 첫 시간과 2번째 시간의 차를 구한다. 주의사항 ① 여기서 첫째 시간보다 둘째 시간이 더 크다는 조건이 따로 붙어있지 않다. 코드 #include #include using namespace std; int time2sec(string str) { int sum = 0; sum += stoi(str.substr(0, 2)..

https://www.acmicpc.net/problem/5565 5565번: 영수증 첫째 줄에 10권의 총 가격이 주어진다. 둘째 줄부터 9개 줄에는 가격을 읽을 수 있는 책 9권의 가격이 주어진다. 책의 가격은 10,000이하인 양의 정수이다. www.acmicpc.net 요구사항 ①첫째 줄에는 10권의 가격합이 적히고, ②나머지 9줄은 10권 중 9권 각각의 가격이다. 따라서 첫째에 적힌 총 가격에서 나머지 9개의 가격을 빼주면 계산하지 않은 나머지 1권의 가격이 나온다. 코드 #include #include using namespace std; int main() { int sum, price; cin >> sum; for (int i = 0; i > price; s..