Step-by-Step

문제를 풀다보면 특정 값으로 나눈 나머지값을 구하라는 문구를 많이 접하게 되었다. 자료형 범위를 넘어가지 않도록 조건을 제시해 준 것인데, 만약 전체 곱의 나머지를 구하라고 하면, 전체 곱이 나오기 전에 오버플로우가 발생할 수 있다. 이때 사용하는 것이 모듈러 연산이다. 모듈러 연산 (Modular Arithmetic) 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산 모듈러 합동 (Modular Congruent) 두 A,B 숫자가 M을 모듈러한 결과 값이 같다면 모듈러 합동관계라고 한다. A mod M = b mod N A ≡ B mod M 모듈러 합동식 A = B + K * M (K는 정수) 이 식에서 B를 이항하게 되면, A - B = K * M 두 정수 A, B와 양의 정수 M에 대해 다음..

시간만 있다면 더더더 공부하고 싶지만.. 모든 일정이 끝난 후 다시 재개....ㅠㅠ 간단한 문제 풀기 위해서 일단 꼭 알아야 하는 것들만 정리하겠다! 언제까지 검색하고 있을래??? 당장 외우자!!! Queue // 헤더 #include // 선언 queue q; // 내장 함수 q.pop(); // front 데이터 삭제 q.push(); // back에 데이터 추가 q.front(); // front 데이터 반환 q.back();// back 데이터 반환 q.size();// 현재 큐 사이즈 q.empty();// 비어있는지 swap(q1, q2);// 두 큐 내용 바꿈 Stack // 헤더 #include // 선언 stack stack; // 내장 함수 stack.push();// top+1에 데이..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net BFS + DFS만 주구장창 하던 나 반성해.. DP 연습 좀 해야겠다고 느낀 문제 😂 그냥 피보나치 수열처럼 단순히 누적으로 넣는 것이 아니라 좀 문제를 제대로 이해해야 전략을 세울 수 있다. 문제에서 주어진 예제 동전 3개로 10을 만들어야 한다. 일단 주의할 점은 0원을 만들기 위해서 모두 선택하지 않는 경우의 수 1개가 있다. 설명은 아래 그림 참조 (잘 그린지는 모르겠지만.) 코드 #inc..

C랑 C++ 중에 하나를 써야 하는 일이 생겼다. 전공 수업시간에 C프로그래밍을 배웠었는데, 대학교 2학년때 뿐이었고.. 그 뒤로는 JAVA 외길 인생이었다. (+Python도 종종 씀) C로 할까 하다가 입출력 간단한 C++로 결정 ! I/O 헤더파일 #include - Input/Output Stream std 클래스 using namespace std - namespace : 이름 공간 / std : 클래스- std class : cout, cin, endl 등 함수들 정의된 클래스- 사용할 때 std::cin 이런식으로 써야하는데 위 코드 정의를 해두면 그냥 cin 이렇게 써도 된다. Vector // 헤더 #include // vector 벡터명(크기); => 크기는 생략 가능 vector v;..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 다섯 종류의 CCTV가 있고 모두 각도를 조절할 수 있다. 사각지대를 최소화할 수 있는 경우의 수를 구하는 것이다. 모든 경우를 찾기 위해 DFS로 탐색했다. 1,2,3,4,5번이 각각 탐색 방향이 다른데, 한 방향으로 탐색하는 메소드를 구현해서 방향에 맞게 돌려주고, 수에 맞게 호출해줬다. package BOJ_SS; import java.util.*; public class boj1..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 와 .. 노트에 열심히 풀어가면서 썼던 문제ㅋㅋㅋ 가장 중요한 건 톱니바퀴 4개는 동시에 돌아간다는 것이다!!! 나는 2번째 톱니바퀴가 돌면.. 양 옆으로 한개씩 보고 돌릴지 안돌릴지 판단하고 구현했는데, 테케가 다 틀려서 몹시 당황했다.. 동시에 돌아가는것만 잘 알면 금방 풀릴듯! 각 톱니 데이터는 2차원 배열로 만들어서 저장해뒀고, 12시 방향이나 3시,9시 방향은 idx로 저장해서 반시..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 생각보다 너무 어려웠던..문제.. 생각해야하는 경우가 너무 많다. 일단 행과 열 각각 따로따로 탐색해야 하는데, 좌→우 / 우→좌든 상→하/하→상이든 상관없다. (어차피 오르막이랑 내리막 조건이 같기 때문) 문제에 나와있는 조건에 맞게 길 탐색만 하면 나머지는 상관없다. 1. 다음칸이 같은 높이면 그냥 전진 2. 다음칸이 1칸 낮은 경우, 다다음칸이 똑같이 1칸 낮은지 확인 후 전진 (내리막 사용가능) - 이 때, sl..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 지문을 잘 읽은 후에 풀어야 한다고 느낀 문제! 예제 2번에서 6개의 팀원이 있을 때, 0,1,3번이 팀을 이룬다면 스타트팀은 해당 부분의 합으로 능력치로 결정된다. 자동으로 링크팀은 2,4,5번으로 해당 부분의 합이다. Sii는 항상 0이기 때문에 i==j일때는 값을 더하지 않았고 스타트팀에 들어간 팀원은 ArrayList에 담아놓고 링크팀 계산에 엮기지 않도록 하였다. package BOJ_SS; import ja..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net DFS 방법을 익힐때 접했던 문제이다. ※ 포인트 - 3번째 줄에서 입력값으로 받는 사칙연산의 개수는 op로 선언된 int[] 배열에 저장 - dfs를 실행하면서 op[i] 값이 0보다 크면(사용할 수 있는 연산자가 남아있을 경우) 반영하여 재귀호출 - 이때 op[i]는 한 번 사용했으므로 1감소 시켜줌 - cnt가 n일때 (사칙연산 n-1개..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 첫줄에는 행과 열의 수를 알려주고, 둘째줄부터는 행렬의 값들을 알려준다. 그림은 0과 1로 이루어져있으며, 0은 공백 1은 그림 이다. BFS 풀이방식을 이용했다! 문제풀이는 다음과 같다. import java.io.IOException; import java.util.*; public class Main { static int[] dx = {1,-1,0,0}; static int[] dy = {0,0..