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/17471 풀이과정먼저 문제에 대해서 간단히 설명해보자면 다음과 같이 그래프가 주어졌을 때2가지 구역으로 나눠서, 두 구역의 인구수 차이의 최솟값을 구하는 문제이다. 여기서 유니온 파인드 알고리즘을 생각할 수 있었다. 문제의 조건으로는각 구역은 1개 이상의 지역으로 이루어져야된다고 한다. (1) (2, 3, 4, 5, 6)(2) (1, 3, 4, 5, 6)....(1, 2) (3, 4, 5, 6)(1, 3) (2, 4, 5, 6)(1, 4) (2, 3, 5, 6)...(1, 2, 3) (4, 5, 6)(1, 2, 4) (3, 5, 6) 이런 식으로 2가지 구역이 나눠질 수 있어서지역의 개수 N개에서최소 지역의 개수인 1부터 최대 N / 2개까지 뽑..

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

2차원 누적합으로 2차원 배열을 풀어보자.2차원 배열의 누적합도 1차원 배열의 누적합과 크게 다르지 않다. 1차원 배열에서 sum[N]은 1번째부터 N번째까지의 합을 나타냈다. 그럼 이차원 배열 sum[N][M]을 (0,0)부터 (N,M)까지의 합이라고 해보자.빨간 부분 (3, 3)부터 (5, 5)의 합을 어떻게 구할 수 있을까? prefixSum[5][5]는 (1,1)부터 (5,5)까지의 합을 나타내므로 해당 부분에서녹색 부분(prefixSum[2][5])을 빼주고, 노란 부분(prefixSum[5][2])을 빼주고, 두 번 빠진 녹색과 노란색이 만나는 부분(prefixSum[2][2])를 한번 더 더해주면 될 것이다.  그럼 (0,0)부터 (N,M)까지의 모든 위치의 값만 유효한 시간 내에 구할 수 ..

도둑이 보석가게에 배낭을 메고 침입했다.배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다.각 보석들의 무게와 가격은 알고 있다.배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은? 배낭 채우기 문제는 다이나믹 프로그래밍의 유명한 유형이다.그중에서도 보석을 자를 수 있다고 가정하는 Fractional Knapsack 문제와자를 수 없다고 가정하는 0-1 Knapsack 문제가 있는데,전자보다는 후자가 주로 다루어진다. 0-1 Knapsack 문제는 다이나믹 프로그래밍이라는 방법을 쓰는 기본적인 문제로 알려져 있다.DP를 잘 모른다면 생각나는 방법은 두 가지 정도가 있을 것이다. 1. 모든 경우의 수를 넣어본다 (Brute-Force)n개의 보석이 있다고 치..

DFS, 인접행렬, 역행렬을 사용하는 문제이다. Candidate | Softeer Assessment UI softeer.aiS -> T로 가는 경로가 존재해야 하고,T -> S로 돌아오는 경로가 존재해야 한다.fromS와 fromT만 사용하면 S -> T와 T -> S 경로를 독립적으로 찾게 되며, 이는 각각의 경로가 서로 다른 노드를 포함할 수 있다. 예를 들어, S -> T 경로가 포함하는 노드가 T -> S 경로와 일치하지 않을 수 있다. 그래서 역행렬이 알고리즘이 필요하다. fromS: S에서 출발하여 도달할 수 있는 모든 노드.fromT: T에서 출발하여 도달할 수 있는 모든 노드.toS: S로 도달할 수 있는 모든 노드 (역방향 그래프).toT: T로 도달할 수 있는 모든 노드 (역방향 그..

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

#include using namespace std;ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL); sort 사용자 정의 정렬// 1차원 벡터bool cmp(int a, int b) return a &v1, vector &v2){ if(v1[1] == v2[1]) return v1[0] u, pair t){ if(u.first==t.first) return u.second  정렬 후, 중복제거sort(v.begin(), v.end());v.erase(unique(v.begin(). v.end()), v.end()); 정렬된 경우 이분탐색 (크거나 같은 값, 더 큰 값)lower_bound는 정렬된 배열에서 탐색값이 2개 이상 있..

백트래킹현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 - 제약 조건을 만족하는 문제를 해결하기 위해 쓰는 알고리즘 - 특정 조건을 만족하는 조합 알고리즘에 해당하는 모든 해를 찾는 문제 - 모든 경우의 수 중 조건에 위배되는 경우는 빼고 답을 찾는 것 - 답이 될 수 있는 모든 경우의 수를 DFS를 이용해 찾음 - 만약 답이 될 수 없는 경우면 더 이상 탐색하지 않고 이전으로 돌아감 ‼️ 주의재귀로 푸니까 스택 메모리 제한을 확인해야된다.N이 클 경우 백트래킹을 적용하면 시간초과 난다. 백트래킹 알고리즘의 시간 복잡도는 주로 문제의 조건에 따라 달라진다. 선택할 수 있는 숫자가 N개이고, 수열의 길이가 M이므로 총 경우의 수는 O(N^M)다. 따라서 최악의 경우에는 지수 시간이 소요..

https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이과정 먼저, 장르별로 재생횟수, 고유번호를 같이 m1 맵에 넣어주고 장르별로 재생횟수의 합을 m2 맵에 넣어준다. - cmp 함수 m1의 맵을 돌면서 재생횟수가 같으면 고유번호를 오름차순해주고, 재생횟수가 다르면 재생횟수를 내림차순해준다. (여기서 auto &x : m1은 x를 m1의 요소에 대한 참조로 가져오기 위해 &를 사용한다. 원본을 변경하기 위해서는 참조를 사용해야 합니다.) - cm..