안녕 세상아,

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 규칙 찾는 다이나믹 프로그래밍은 너무 어려워.. #include #include using namespace std; int arr[1001]; int dp[1001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin ..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net dfs, bfs 기본 문제이다. 거의 템플릿같은 문제라고 생각하고 이대로 외우면 될 것 같다. #include #include #include using namespace std; int n, m, v;//정점, 간선, 시작 정점 bool isVisited[1001] = { false };//정점 방문 여부 int map[1001][1001];//인접 행렬 그..

https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 스택을 사용하는게 아니라 sstream 사용하는건줄 알고 헤맸다.. 스택을 사용해서 문제에 나오는 조건마다 조건문을 작성하고 풀면 그래도 나쁘진 않을듯. 그치만 여기까지 생각하는게 꽤나 어렵다고 생각한다 내기준에서...ㅜ #include #include #include using namespace std; //스택 출력 void printStk(stack& stk)..

stringstream은 공백 기준으로 문자열을 자를 때 사용할 수 있다. stringstream을 사용하기 위해서는 sstream 헤더를 include해야한다. #include 공백 기준으로 문자열을 자를 때 뿐만 아니라 문자열에서 int값을 찾을 때도 사용된다. #include #include int main() { // 공백 기준 문자열 자르기 string s = "abc def ghi"; stringstream ss(s); ss.str(s); string word; while(ss >> word) { cout

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 규칙 찾기 약간 조금 까다로웠다. 사실 그냥 내가 규칙 찾기 잘 못하는 것 같다. 규칙은 p(n) = p(n-2) + p(n-3) 이다. #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long long int t, n; cin >> t..

https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 투 포인터 이건 잘 모르겠고 일단 최댓값 갱신하면서 문제를 해결하였다. 누적합을 구한 후 연속적인 날짜의 수 마다 끊어준 후 그 전 누적값을 빼주면 구할 수 있다. 계속 최댓값을 갱신하면서 마지막 최댓값을 출력해주면 된다. #include #include #include using namespace std; int arr[100005]; int maxSum = -1000001; int..

https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이분탐색 문제지만 이분탐색 말고 다른걸로 풀려고 했었고 분명 정답, 반례라고 적혀있는 모든게 맞았지만 바로 틀려버려서 이분탐색 문제로 풀었다. 역시 적힌대로 푸는게 맞는 것 같긴함. 근데 아직도 모르겠다. 이 정답 말고 내가 푼건 왜 틀린건지,,, ㅜ #include #include #include using namespace std; int main() { ios::sync_with_std..

https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net N과 M (4)번 문제에서 새로운 배열만 만들어주면 된다. #include #include using namespace std; int n, m; int arr[10];//입력받은 원래 배열 bool isVisited[10] = { false }; int ans[10];//출력할 배열 void dfs(int depth, int x) { if (x == m) { for (int i = 0;..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 첫번째 계단일 때와 두번째 계단일 때는 고민 없이 구할 수 있다. 하지만 세번째 계단부터는 연속해서 3개 계단을 오를 수 없는 규칙이 있기 때문에 고민을 해야한다. 세번째 계단을 오르기 위해서는 1. 시작 -> 첫번째 계단 -> 세번째 계단 2. 두번째 계단 -> 세번째 계단 이렇게 두가지 경우가 있다. 이 중 더 큰 한가지를 선택해야되기 때문에 max(1,2) 이렇게 볼 수 있다. #include #incl..

https://www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주 www.acmicpc.net 예제 보고 복잡해보여서 아찔해졌지만 조금만 생각하면 쉽게 풀 수 있는 문제이다. 출발점, 도착점과 행성의 중점 거리 구한 후 반지름 보다 작으면 진입한다고 판단할 수 있기 때문에 cnt++를 해준다. 만약 크면 만나지 않고 지나가는 것이기 때문에 continue하면 된다. 굳이 배열로 받지 않고 x1, y1, x2, y2 이렇게 놔둬도 될 것 같다. 어짜피 4개밖에 없으니까 #inc..