피너클의 it공부방

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net dp를 이용하는 문제다. dp란 계산한 내용을 저장한뒤 다음에 필요로 할때 꺼내 사용하는 알고리즘이다. solve함수를 지정해 문제를 해결할것이다. solve함수는 현재 위치를 나타내는 now와 마지막으로 추가한 수를 나타내는 last를 전달받는다. 10 20 10 30 20 50 solve함수를 현재 위치의 배열을 추..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 구간합을 이용한 문제다. long long sum[1025][1025]; long long ssum[1025][1025]; long long arr[1025][1025]; arr은 입력받을 배여르 ssum은 sum을 만들기 전 배열, sum은 2차원 배열의 구간합이다. for (int i = 1; i arr[i][j]; } } arr을 입력받은 다음 fo..

https://www.acmicpc.net/problem/1268 1268번: 임시 반장 정하기 첫째 줄에는 반의 학생 수를 나타내는 정수가 주어진다. 학생 수는 3 이상 1000 이하이다. 둘째 줄부터는 1번 학생부터 차례대로 각 줄마다 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 5 www.acmicpc.net 간단한 구현문제다. cin >> n; for (int i = 1; i arr[i][j]; } } n을 입력받고 n만큼의 학생의 데이터를 입력받는다. int ban = 1001, stu = -1; for (int i = 1; i stu) { stu = sol; ban = i; } } cout

https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 간단한 구현문제다. string s; while (true) { cin >> s; if (s == "0") break; if (chk(s)) cout s; if (s == "0") break; if (chk(s)) cout

https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net dp를 이용해 푼 문제다. string str; string sam; int cache[1000001][11]; int k; str은 입력받는 문자열, sam은 중간중간 바뀌는 문자열이다. cache는 dp에서 사용하는 저장공간이며 k는 바꾸는 횟수다. int solve(string s, int num) { if (num == k) return stoi(s); int &ret = cache[stoi(s)][num]; if (ret != -1) return ret; i..

https://www.acmicpc.net/problem/1331 1331번: 나이트 투어 나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며, 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는 경로이다. 다음 그림은 나이트 투어의 한 예이다. 영식이는 6× www.acmicpc.net 구현문제다. bool visited[7][7]; int dx[8] = { 2, 2, 1, -1, -2, -2, -1, 1 }; int dy[8] = { -1, 1, 2, 2, 1, -1, -2, -2 }; visited는 나이트가 이동한 장소 dx와 dy는 나이트가 이동하는 위치를 나타낸다. string s; cin >> s; int x = s[0] - 'A'; int y = s[1] - '1'; i..

https://www.acmicpc.net/problem/1251 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다 www.acmicpc.net 그냥 전부다 한번씩 확인해보면 된다. #include #include #include using namespace std; string str; int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin >> str; string ans = "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"; f..

https://www.acmicpc.net/problem/9214 9214번: 첫 번째 항 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄에 걸쳐 최대 100글자의 정수 n이 주어지며, 입력의 끝은 0으로 주어진다. www.acmicpc.net 문자열을 사용하는 구현문제다. int i = 1; string str; while (true) { cin >> str; if (str == "0") break; cout

https://www.acmicpc.net/problem/24508 24508번: 나도리팡 첫 번째 줄에는 정수 $N$, $K$, $T$ 가 공백을 사이에 두고 주어진다. ($2 \le N, K \le 10^5$, $0 \le T \le 10^9$) 두 번째 줄에는 정수 $A_1, A_2, \cdots, A_N$ 이 공백을 사이에 두고 주어진다. ($0 \le A_1, A_2, \cdots, www.acmicpc.net 그리드와 투 포인터를 이용한 구현문제다. cin >> n >> k >> t; v.resize(n); for (int i = 0; i > v[i]; sort(v.begin(), v.end()); 바구니안 나도리의 수를 입력받은 다음 정렬해준다. 앞에있는 적은 나도..

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 범위 안의 소수를 어떻게 찾을것인지와 두 홀수 소수의 합으로 n을 어떻게 나타낼것인지가 관건이다. bool visited[1000001]; vector v; bool visited에는 소수인지 아닌지 여부가 들어갈 것이다. vector v에는 소수가 들어갈것이다. for (int i = 3; i n; if (n == 0) break; n을 입력받고 n이 0이면 반복문을 종료..