피너클의 it공부방

https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net dfs를 이용해 푼 문제다. cin >> n >> m; for (int i = 0; i > str[i]; } memset(visited, false, sizeof(visited)); 기본 세팅을 해준다. int w = 0, b = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { ..

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net dfs를 이용한 문제다. cin >> n >> m; for (int i = 0; i > a >> b >> c; graph[a].push_back({ b, c }); graph[b].push_back({ a, c }); } 값을 입력받은뒤 그래프를 양방향으로 연결해준다. for (int i = 0; i < m; i++) { memset(visited, false, sizeof(visi..

https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 그리드를 이용한 문제다. 두번째 예제를 통해서 확인해보자. 19 20 1 5 12 14 16 16 19 각 크레인은 19와 20이고 화물은 아래와 같다. 화물은 미리 정렬시켜둔다. 현재 첫번째 크레인이 움직일 수 있는 가장 무거운 화물은 7번째 화물이다. 19 20 1 5 12 14 16 16 19 두번째 크레인이 움직일 수 있는 가장 무거울 화물은 6번째 화물이다. 19 20 1..

https://www.acmicpc.net/problem/1083 1083번: 소트 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전 www.acmicpc.net 그리드를 이용한 문제다. 예제 2를 예로 들어보면 아래 그래프 상태에서 s는 2인 상황에이다. 3 5 1 2 4 총 2번 움직일수 있는 상태에서 움직일수 있는 범위는 파란색 만큼이다. 3 5 1 2 4 3을 선택하면 0번 움직이는거고 5를 선택하면 1번 움직이는거, 1을 선택하면 2번 움직이는 것이다. 가장 최선의 움직이는 방법은 5를 선택해 1번 움직이는 것이다. 5 3 1 2 4 이제 s는..

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