https://www.acmicpc.net/problem/10844 풀이 과정dp 파트가 약해서 정리해보고자 한다.문제를 요약해 보자면 ' N자리 수가 있을 때, 인접한 모든 자릿수가 1씩 차이씩 나는 수가 몇 개인지 구하는 것'이다. 여기서 유의해야 할 점은 다음 두 가지를 조심해야 한다. 1) N번째 자릿수의 자릿값이 0인 경우: 다음 자릿수의 자릿값은 1밖에 올 수가 없다.2) N번째 자릿수의 자릿값이 9인 경우: 다음 자릿수의 자릿값은 8밖에 올 수가 없다. 즉 10 다음에 붙을 수 있는 값은 1밖에 없으므로 101이 되는 것이고,만약 19가 온다면 8밖에 올 수 없으므로 198이 되는 것이다.그 외의 값 (2~8)은 각 값보다 -1 또는 +1 인 값을 가질 수 있다. 그럼 자릿값은 0~9를 가질..

https://www.acmicpc.net/problem/17406 풀이과정크기가 N X M 배열이 있을 때 각 행에 있는 모든 수의 합이 가장 최소일 때를 구하는 문제이다. 회전 연산이 세 정수 (r, c, s)로 주어지고가장 왼쪽 윗 칸 (r - s. c - s)가장 오른쪽 아래 칸 (r + s, c + s)정사각형을 시계 방향으로 한 칸씩 돌리면 된다. 예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다. r = 3 c = 4 s = 2가장 왼쪽 윗 칸 (3 - 2, 4 - 2) = (1, 2)가장 오른쪽 아래 칸 (3 + 2, 4 + 2) = (5, 6)A[1][1] A[1][2] → A[1][3] → A[1][4] → A[1][..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에www.acmicpc.net풀이과정처음에는 단순하게 DFS 재귀 백트래킹을 이용하여 구현했다.하지만, DP를 사용하지 않으면 시간초과가 났다. 괜히 골드3 문제가 아니다.DP와 DFS를 같이 사용해야 하는 새로운 문제 유형이었다.만약 이 그림 (0, 0)에 판다를 냅둔다면, (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 1) 을 통해서 총 5일을 살게 될 것이다. 그럼 dp[0][0] ..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net ✅ 누적합이란? x0, x1... xn까지 수가 있을 때 y0 = x0, y1 = x0 + x1, yn = x0 + x1 +... + xn처럼 해당 n까지의 합을 의미한다. y0 = x0 y1 = x0 + x1 y2 = x0 + x1 + x2 ... yN = x0 + x1 + ... + xN ✅ 누적합의 성질 i부터 j의 합을 구하려면 누적합 j에서 누적합 i - 1을 빼주..

https://programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 문제를 딱 보자마자 유니온 파인드 알고리즘이 생각났다. 풀고보니 유니온 파인드의 기본적인 문제이며, 부모 노드의 중복되지 않은 숫자의 개수는 몇 개인지 세면 되는 단순한 문제였다. 풀이 1 #include #include #include using namespace std; int parent[201]; int getParent(int x){ if(parent[x] == x) return x; re..

https://programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 이 문제는 다익스트라의 기본 문제이다. 다익스트라 알고리즘을 활용하여 dist 값을 찾아낸 뒤, 가장 큰 값을 찾아 그 값과 일치하는 개수를 세면 된다. #include #include #include using namespace std; const int INF = 1e9; vector dist; vector edge[20001]; priority_queue pq; void dijkstra(int..

https://programmers.co.kr/learn/courses/30/lessons/12949 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 3중 for문에 익숙해지면 풀 수 있는 문제이다. #include #include using namespace std; vector solution(vector arr1, vector arr2) { vector answer; for(int i = 0; i < arr1.size(); i++){ vector v; for(int j = 0; j < arr2[0].size(); j++){ int sum =..

https://programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 이 문제는 (0, 1, 2)(0, 2, 1)(1, 0, 2)(1, 2, 0)(2, 0, 1)(2, 1, 0) 다 돌아보면서 가장 많이 탐험할 수 있는 던전의 수를 세는 것이다. 그러므로, next_permutation 알고리즘과 dfs 알고리즘을 둘 다 쓸 수 있다. 풀이 1 (next_permutation) next_permutation 알고리즘을 쓰기 전에 먼저 정렬을 해준다. k의 수는 순열 ..

https://programmers.co.kr/learn/courses/30/lessons/12936 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 이 문제는 next_permutation 알고리즘으로 풀면 쉽게 풀리지만, 그렇게 해선 시간초과가 나는 문제이다. 해결 방법은 팩토리얼을 사용하여 각 자리의 수를 직접 구해야 된다. 풀이 1 #include #include using namespace std; long long facto(int n){ if(n == 1) return 1; return n * facto(n - 1); } void r..

https://programmers.co.kr/learn/courses/30/lessons/70129 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 단순한 문제인데 생각보다 시간을 많이 뺏긴 문제이다. s가 1이 아닐 때 반복문을 계속 돌려주고, 0의 개수를 세며 전체 길이에서 0의 개수를 뺀 수를 다시 2진수로 만들면 된다. #include #include #include using namespace std; string Binary(int n){ string str = ""; while(n != 0){ str += to_string(n % ..