1차원 배열이 주어지면 그 수에서 두 개를 뽑아서 더해주면 된다. 단 중복을 허용하지 않고 오름차순으로 정렬해야 한다. 제한 사항을 보면 numbers의 길이가 100 이하이다. 따라서 이중 포문으로 해줘도 \(O(N^2)\)의 시간복잡도를 가지기에 중복을 방지하는 stl set을 사용해서 자기 자신인 i == j 인 경우를 제외하고 전부 넣어준다. 이후에 반복문을 모두 돌았다면 answer에 삽입해주면 된다. 1234567891011121314151617181920#include #include #include using namespace std; vector solution(vector numbers) { vector answer; set s; int n = numbers.size(); for (in..

N * N 행렬에 각각 캐릭터의 번호가 주어지면 Stack에 넣어서 같은 번호가 나오면 pop 하고 아니면 push 하는 쉬운 문제였다. #include #include #include using namespace std; int pick(vector& board, int col) { for (int i = 0; i < board.size(); i++) { if (board[i][col] == 0) continue; int ret = board[i][col]; board[i][col] = 0; return ret; } return 0; } int solution(vector board, vector moves) { int answer = 0; stack s; for (int i = 0; i < moves..

이번에는 다익스트라 알고리즘을 공부해 봤다. 사실 다익스트라는 너무 잘 알려진 알고리즘이라 다른 여러 블로그들을 참고해서 www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 이 문제를 푸는 식으로 알아봤다. const int INF = 1e9; vector ar[20001]; // ar[from].push_back({to, cost}) from -> to , 가중치 vector d; // 거리값을 갱신해주는 배열 일단 기본적으로 가중치..

www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 두 포인터를 활용한 재미있는 문제였다. n을 입력받아서 소수 판정을 해주고 prime 배열에 넣어주고 두 포인터를 쓰면 된다. #include #include using namespace std; const int MX = 4000001; vector sieve; vector prime; int s, e, sum, cnt; void era(int n) { sieve.resize(n + 1, true); sieve[0] = sieve[1] = false; for (int i = 2; i * i = n) sum -= prime[s++..

www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 슬라이딩 윈도를 사용해서 공간 복잡도를 O(1)로 만들고 풀어야 하는 문제. 라이님의 블로그를 참고해서 풀었다. DP식 짜는 것은 매우 쉽지만 필요 메모리가 무려 4MB이다... DP 식을 잘 보면 cin >> TMX[j]; TMN[j] = TMX[j]; TMX[j] += max(MX[1], (j == 1) ? max(MX[0], MX[2]) : MX[j]); TMN[j] += min(MN[1], (j == 1) ? min(..

www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 � www.acmicpc.net 각각 i부터 j까지의 부분합 중 k인 수가 몇 개인지 세는 문제이다. 일단 prefix sum을 통해서 배열을 채웠는데 for (int i = 1; i > x; d[i] += d[i - 1] + x; } 이 후가 문제이다. 여기서 각각의 원소에 대해서 \(O(N^2)\) 으로 짜면 시간 초과가 난다. 따라서 i 부터 j 사이의 부분합의 개수..