본문 바로가기

Algorithm26

Monge array란? 정의 $n \times m$인 matrix가 존재할 때, $A[i, j] + A[k, l] \leqq A[i.l] + A[k,l]$이면 monge array라고 한다. ( $1 \leqq i < k \leqq n and 1 \leqq j 2021. 10. 31.
1965번 상자넣기 문제의 해결법 앞에 상자를 넣기 위해서는 뒤에 상자가 앞의 상자보다 더 커야 한다. 최고로 많이 넣을 수 있는 문제를 푼다고 하면, 최장증가부분수열의 문제와 같다고 볼 수 있다. 예제 1번 박스부터 시작하여 1번 박스보다 큰 모든 박스에게 +1해준다. 6번 박스보다 작은 것들은 1번 박스때의 숫자를 가지고 오고 큰 숫자들은 +1이거나 이전 박스까지 센 숫자 중 큰 것을 넣어준다. 점화식 $$dp[i][j] = \begin{cases} max(dp[i][i]+1, dp[i-1][j]), & \text{if }n\text{ box[i] < box[j]} \\ dp[i-1][j], & \text{if }n\text{ box[i]} \ge \text{box[j]} \end{cases} $$ 소스코드 public.. 2021. 5. 19.
공유기 설치 - 2110번 풀이 방법 L이 증가 할수록 공유기의 개수를 감소한다. 만약 크기가 L이고 i번째에 공유기를 설치했다면 다음 공유기를 설치할 좌표(j)는 아래 공식과 같다. $$ X[i] + L 2019. 6. 9.
최소값 찾기 - 11003번 해결방법 세그먼트 트리로 안 풀렸다.세그먼트 트리로는 정말 힘들다그래서 우선순위큐로 풀었다. 근데 이것도 겨우겨우 시간 통과했다. 우선순위큐는 최대값을 반환하므로 최소값을 찾기 위해 {-값, index}를 input으로 받는다. priority_queue pq; // { -값, index } 그리고 최솟값의 인덱스가 i - L + 1라면, pq.top().first를 출력하고 아니라면 해당 인덱스가 나올때까지 반복한다. 전체코드 #include #include using namespace std; priority_queue pq; int N, L, A; int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> N >> L; for.. 2019. 5. 19.
탑 - 2493번 해결방법 stack을 이용하여 해결 할 수 있다. stack에는 index를 넣는다. if num[stack.top()] input보다 큰 값이 stack이 나올때 까지 pop한다. -> stack이 empty라면 0을 출력 -> 아니라면 stack.top()을 출력 -> stack에 index를 푸쉬한다. else -> st.top() 출력 -> stack에 index 출력 전체소스 #include #include using namespace std; int N, num[500001]; int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); stack st; cin >> N; for (int i = 1; i > num[.. 2019. 5. 19.
나머지 합 - 10986번 해결방법 SUM(0 ~ i) % M의 개수를 받는다. i > M; while(N--) { cin >> a; sum += a; num[sum % M]++; } ll ans = num[0]; for (int i = 0; i < M; ++i) ans += (num[i] * (num[i] - 1)) / 2; cout 2019. 5. 19.
타일채우기 - level 4 해결방법 dp를 이용하여 풀었다. $$ dp[N] = dp[N-1] + 2*dp[N-2] $$ N번째 경우의 수는 dp[N-1]번째에서 1 X 2 직사각형을 채울 경우와 dp[N-2]에서 2 X 1 직사각형과 2 X 2 직사각형을 채울 경우의 수를 합친것이다. 소스코드 #include using namespace std; int dp[1001]; int N, M; int main() { cin >> N >> M; dp[1] = 1; dp[2] = 3; for(int i = 3; i 2019. 5. 12.
3개의 숫자를 더하여 술래가 원하는 숫자를 만드세요 - level 2 해결 방법 문제 자체가 어렵다기 보다는 예외 케이스가 많아서 힘들었다. 일단 이 문제 반례를 찾으시는 분은 아래 케이스를 해보길 바랍니다. input 5 5 5 2 12 12 output 2 5 5 전체 소스 #include #include #include #include using namespace std; typedef long long ll; ll num[30], cnt, T, n; vector check; ll sum(vector v) { ll ret = 0; for(int i = 0; i < v.size(); ++i) ret += v[i]; return ret; } void dfs(vector v, int here, int c) { if(c == 3) { if(T == sum(v)) { for(.. 2019. 5. 11.
여행경로 - level 3 해결방법 dfs, bfs문제이고 솔직히 쉬운 문제였는데 오래걸렸다. 첫 번째는 문제에 대한 오해였다. 이 티켓을 사용해서 모든 도시를 다 방문해야만한다. 단순히 dfs를 통해서 사용하는 것이 아니라 실제 다 모든 도시 방문 && 모든 티켓 사용인지를 확인해줘야만 한다. 전체 소스 #include #include #include #include #include using namespace std; int T; vector v; vector dfs(string s, vector t, vector ans, int cnt) { ans.push_back(s); if (cnt == T) return ans; vector tmp; for (int i = 0; i < t.size(); ++i) { if (t[i][0].. 2019. 5. 8.
체육복 - level 2 해결방법 좀 더 신중히 고민하면 쉬운문제이다. 여벌 옷은 가지고 온 아이들은 수업에 참여 할 수 있다. 그래서 lost, reserve에서 같은 번호가 있다면 두 곳 모두에서 제거해주는 전처리가 필요하다. Time Complexity sort과정이 두번 있다. $$ O(2NlogN) $$ 전처리 과정은 reserve와 lost같은 것을 찾으므로 for문 2개로 돌아간다. $$ O(2N^{2}) $$ 마지막 계산 같다. $$ O(2N^{2}) $$ 따라서 $$ O(2NlogN + 4N^{2}) $$ 전체 소스 #include #include #include using namespace std; int solution(int n, vector lost, vector reserve) { sort(lost.be.. 2019. 5. 6.
단속카메라 - level 3 해결방법 왜 2점 밖에 안주는지 모르겠지만 쉽지 않았다. 아이디어 위의 그림은 예시를 그림으로 한 것이다. 그림을 보면 알 수 있듯이 겹치는 것들 중 진출 좌표(r[i][1])이 가장 작은 것이 가장 많이 겹치게 할 수 있다. 하지만 안 겹치는 선은 안 겹치는 선들 중 가장 처음 것을 기준으로 다시 몇개 겹칠 수 있는지 계산하면 된다. 알고리즘 r[i][0], r[i][1] 오름차순으로 정렬 변수 end : i번째까지 중 가장 작은 r[i][1] $$ end\ =\ min(end,\ r[i][1]) $$ 만약 end < r[i][1]이면 answer증가시키고, end = r[i][1]해준다. $$ end\ =\ r[i][1] $$ Time Compexity 정렬은 O(NlogN)이고, 업데이트는 O(N).. 2019. 5. 6.
1931번 - 회의실 배정 해결방벙 그리디 방법으로 해결하였다. 증명 회의실을 가장 많이 사용 할 수 있는 경우는 1. 끝나는 시간이 빠른 것, 2. 시작시간이 빠른 것 순으로 정렬 하고 가능한 시간의 개수를 탐색하면 된다. $$ END_{i} >= END_{j} \ (단, \ i는\ 가장\ 빨리\ 끝나는\ 회의, \ j는\ i제외한\ 회의, \ END는\ 이후\ 가능한\ 회의의\ 개수)$$ 그러므로 끝나는 회의의 수가 가장 빠르면 더 많은 회의를 할 수 있다. 전체 소스 #include #include #include using namespace std; int N; vector time; bool cmp(pair a, pair b) { if (a.second == b.second) return a.first < b.first;.. 2019. 5. 5.
줄 서는 방법 - level 3 해결방법 쉬운듯 어려운 문제였다. 해결방법은 머리 속으로 바로 생각났는데 처음 구현해보는 알고리즘이라 고생을 많이 했다. 충분히 프로그래머스를 이용하여 코딩테스트를 보는 회사에서 나올 수 있는 문제라고 여겨진다. k번째의 경우의 수를 구하는 문제이다. 만약 아래와 같이 next_permutation으로 푼다면 효율성 테스트를 통과하지 못해 효율적인 방법을 생각해내야 한다. do { k--; if(k == 0) break; } while(next_permutation(answer.begin(), answer.end())); factorial을 이용하여 문제를 푼다면 더 빠르게 풀 수 있다. 예를 들어 보자! n = 10이라고 가정한다. 만약 첫 번째 자리수가 바뀌기 위해서는 k > 9! 하므로, k < 9.. 2019. 5. 4.
6549번 - 히스토그램에서 가장 큰 직사각형 해결방법 라인 4번 문제와 흡사한 문제로 보인다. 이상하게 요즘 문제들이 쉬운듯 어려운 문제가 많이 보이는데 여러가지 자료구조를 안써보았기 때문이라고 생각한다. 무작위로 풀면서 사고력을 길러야 겠다. 내가 푼 방법은 2가지 이다. segment tree + conqure & divide방법과 stack방법이다. Segment Tree + conquare & divide Segment Tree는 각 구간에서 가장 높이가 낮은 index를 저장해준다. int init(int leftn, int rightn, int node) { if (leftn == rightn) return tree[node] = leftn; int mid = (leftn + rightn) / 2; int leftv = init(left.. 2019. 5. 2.
동전0 - 11047번 해결방법 알고리즘은 그리디를 사용하였다. 하지만 그리디를 사용해도 최적인지 증명과정이 필요하다. 증명 문제에서는 i개의 동전이 있고, 오름차순으로 주어진다. N을 금액이라고 할 때 동전이 N보다 작다면 항상 아래와 같다. $$ N / C_{i} K >> N; int ans = 0; for (int i = 0; i > c[i]; for (int i = K - 1; i >= 0; --i) if (N >= c[i]) { ans += N / c[i]; N -= (N / c[i] * c[i]); } cout 2019. 4. 29.
동물원 - 1309번 해결방법 O을 배치한 경우, X를 배치 하지 않은 경우라고 할 때 O X | X O | X X 3가지 경우의 수로 둘 수 있다. 그래서 dp를 N * 3개의 배열을 두고 시작하였다. int dp[100001][3] 점화식은 어떻게 될까? 점화식도 3가지로 나눌 수 있다. 만약 O X경우라면 이전의 경우의 수는 X O | X X가 되어야만 하기 때문에 아래와 같아진다. 나머지도 똑같은 방식으로 구해본다면 점화식을 구할 수 있다. $$ dp[i][0] = dp[i-1][1] + dp[i-1][2] $$ $$ dp[i][1] = dp[i-1][0] + dp[i-1][2] $$ $$ dp[i][2] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] $$ 전체코드 #include using n.. 2019. 4. 29.
3980번 - 선발명단 해결방법 bitmask dp로 해결하였다.dp를 2차원 배열로 (position, state)를 담을 수 있게 정의하였다. int dp[11][1 > t) % 2 == 0은 t라는 포지션이 0일 경우 아직 배정이 안됬으므로 배정을 해야한다는 조건이다. 더해서 포지션의 능력치가 0이 되면 안되기 때문에 s[p][t] != 0아닌 것도 포함해줘야 한다. sub를 둔 이유는 조건에 맞는 포지션이 없을 경우 -1를 리턴하는데, 이 경우는 포지션을 모두 배정하지 못한 경우의 수므로 제외시켜줘야 한다. if ((state >> t) % 2 == 0 && s[p][t] != 0) { int sub = solution(p + 1, state | 1 t) % 2 == 0 && s[p][t] != 0) { int sub .. 2019. 4. 20.
1102번 - 발전소 해결방법 해당 문제는 bitmask dp로 풀었다. bit가 켜지면 발전소가 켜진 것이고, bit가 꺼지면 발전소가 꺼진 것이다. bitmask dp로 푼 이유는 a번째 발전소가 j번째 가동시킬때와 b번째 발전소가 j번째 발전소를 가동시킬때가 다르기 때문이다. 문제를 풀 때 유의할 점은 0개 이상일 경우이다. 0개 이상일 경우 0을 리턴해야하지 -1를 리턴하게 하면 안된다. int dp[1 > i) % 2 == 1) cnt++; if (cnt >= T) return 0; T보다 작다면 비트가 0인 수를 찾은 다음 비트가 1인 수들 중에서 비용 값을 더해주고 0비트를 1로 바꿔 재귀시켜준다. for (int i = 0; i > i) % 2 == 0) { // 안켜진 발전.. 2019. 4. 19.
튜브의 소개팅 - level 4 해결방법 고려해야 변수는 y, x, d(거리)이다. 따라서 3차원 배열로 dp를 정의했다. ll dp[51][51][2510]; 점화식은 아래와 같이 된다. newy, newx는 다음번에 이동할 좌표를 의미한다. 다음 좌표는 해당 좌표의 +1이므로 d+1번째에 저장한다. 이전까지의 s + time_map[y][x]를 저장하면 된다. $$ dp[newy][newx][d+1] = min(dp[newy][newx][d+1], dp[y][x][d] + time_map[y][x]) $$ 당연히 수다시간은 제한이 있으므로 제한 시간 넘으면 못가게 해야 한다. if(dp[y][x][d] + time_map[y][x] 2019. 4. 14.
서울에서 경산까지 - level 4 해결방법 2차원 dp로 해결하였다. i는 도시, j는 시간을 의미한다. int dp[101][100010]; 점화식은 아래와 같다. k는 이전도시까지의 시간이다. 이전도시 시간과 + 현재도시 시간(걷는 방법과 자전거 2가지 모두)에 이전 도시까지 + k번째 기부금(걷는 방법과 자전거 2가지 모두)값의 넣는다. $$ dp[i][k + 현재도시 시간] = max(dp[i][k + 현재도시 시간], dp[i-1][k] + k번째 기부금) $$ 하지만, K(전체시간)을 넘으면 안되므로 예외처리를 해줘야 한다. if(k + travel[i][0] 2019. 4. 14.
GPS - level 4 해결방법 먼저 점화식을 세워보자! $$ dp[i][j] = min(dp[i][j], dp[i-1][here] + error) $$ 여기서 i는 시간을 의미하고, j는 각 노드를 의미한다. here은 j노드와 연결된 인접노드를 의미한다. dp[i][j]는 이전 시간 인접노드들의 에러들 중 최소를 + error(1 또는 0)을 의미한다. int dp[110][210]; // 시간과 노드로 구성된 dp int error = gps_log[i] == j ? 0 : 1; // gps_log[i]와 현재 노드가 같다면 0 아니면 1 초기화 과정이다. adj[i].clear()는 꼭 써주자! 아무래도 프로그래머스는 전역변수도 초기화가 안되는 모양이다. for(int i=0;i 2019. 4. 13.
단체사진 찍기 - Level 4 해결방법 경우의 수를 구하는 문제이다. 다행히 n의 최대크기가 8이므로 8! = 40,320개로 모든 경우의수를 세면서 풀 수 있는 문제이다. 이 문제를 풀면서 next_permutation이라는 함수를 새로 배웠다. 그 동안 재귀나 반복으로 풀었는데, 한결 쉬워질거 같다. 먼저 vector에다가 8개의 수를 모두 넣었다. 그리고 pos배열을 하나 만들어 해당 알파벳의 index번호를 넣었다. vector f = {&#39;A&#39;, &#39;C&#39;, &#39;F&#39;, &#39;J&#39;, &#39;M&#39;, &#39;N&#39;, &#39;R&#39;,&#39;T&#39;}; int pos[26]; 그 다음 do ~ while문을 통해 나오는 다음 경우의 수를 통해 문제의 조건과 일.. 2019. 4. 6.
게임 맵 최단거리 - Level 4 해결방법 문제는 (0,0)부터 (n-1, m-1)까지 가는 거리 중 최소값을 구하는 것이다. 이런 문제는 항상 BFS가 답이다! DFS로 구현해도 되지만 DFS의 TimeComplexity가 너무 크기 때문에 시간초과가 된다. 다익스크라 알고리즘도 BFS를 쓰는 이유로 사용되고 있다! 삼성에서 이런 문제가 출제되기도 하는데 무조건 BFS다! 나는 struct로 (y,x)위치와 거리가 있는 구조체를 만들었다. struct node { int y, x, d; node(int yy, int xx, int dd) : y(yy), x(xx), d(dd) {} node() {} }; 그 다음 BFS로 구현하였고 먼저 (n - 1, m - 1)도착한 거리를 answer에 대입하고 break해주었다. BFS는 먼저 도.. 2019. 4. 6.
쿠키 구입 - level 4 해결방법 이 문제는 두 아들에게 똑같은 쿠키를 줄 경우 가장 큰 쿠키의 개수를 구하는 문제이다. 아들 1에게는 N - M번째까지의 쿠키를 주었다면, 아들2에게는 M+1 - K번째까지의 쿠키를 준 쿠키가 같아야 되고 가장 큰 수를 return해야 된다. 까지의 배열에는 쿠키의 수가 임의의로 존재한다. 만약 이 문제를 경우의 수마다 합을 한다면 Time Compexity는 우주까지 간다. 그래서 배열을 이용해 M번째 까지의 합을 미리 저장해 놓는 것이 좋다. 만약 I - J까지의 합을 구하고 싶다면 J번째 합에서 I - 1번째의 합을 빼주면 된다. int sum[N+1]; for (int i = 0; i < cookie.size(); ++i) sum[i+1] = sum[i] + cookie[i]; 먼저 아들.. 2019. 4. 5.
도둑질 - level 4 해결방법 이 문제는 처음에 0번을 터는 수와 1번을 터는 수로 나눌 수 있다. 인접한 집을 털 수 없기 때문에 이전전 집과 현재와 이전 집중에 누가 큰지가 현재 값이 된다. $$ dp[0][i] = max(dp[0][i-1], dp[0][i-2] + money[i]) $$ $$ dp[1][i] = max(dp[0][i-1], do[0][i-2] + money[i]) $$ 위의 점화식을 보면 똑같이 보이겠지만 위에 점화식은 처음 집을 털 경우이므로 마지막집은 항상 털면 안되고, 아래 점화식은 2번째 집부터 털기 때문에 마지막집을 털어도 된다. 점화식을 통해 dp는 2 * 집의 수만큼 2차원 배열로 정의했다. int dp[2][1000001]; 아래는 초기화 코드이다. dp[0][1]에도 넣어준 이유는 반복.. 2019. 4. 5.
Brute Force vs Dynamic Programming 1. Brute Force(완전탐색) Brute Force의 이름을 살펴보자면, Brute는 짐승을 의미한다. 일반적으로 짐승은 본능에 의지해 &#39;무식함&#39;을 나타낸다. 그렇다면 여기서 &#39;무식함&#39;은 무엇일까? 그것은 모든 경우의 수를 찾아보는 것이다. 아주 간단한 예로 1 ~ 100가지 숫자 중에서 원하는 숫자 하나를 찾아본다고 하자! 100을 찾고 싶다면, 1부터 쭉 조사해서 100번을 찾을 때까지 반복한다. 이런 알고리즘적 &#39;무식함&#39;을 Brute라고 표현한 것이다. 가장 유명한 문제로 &#39;외판원 순회&#39;라는 문제가 있다. 1,2,3,4,5라는 노드가 있고 모든 노드를 1번씩 방문하고 출발했던 노드로 되돌아 오는 최소의 경로를 찾는 문제이다. 아래와 같.. 2019. 4. 1.

티스토리툴바