PS

· PS
2579. DPhttps://www.acmicpc.net/problem/2579  [풀이]점화식을 1차원 배열로 만들면 연속해서 계단을 밟는 조건을 표현하기 어려워 2차원 배열 d로 선언한다.또한 각 계단의 점수를 s 배열에 저장해둔다.d[k][1]은 연속적으로 계단을 밟지 않고 올라와서 k번째 계단에 올라왔을 때 점수의 최댓값을 의미하고 d[k][2]는 직전 계단을 밟아 두 번째 계단이며 k번째 계단일 때 점수의 최댓값을 의미한다.따라서 d[k][1]일때는 반드시 k-2번째 계단을 밟았을 것으므로 max( d[k-2][1], d[k-2][2] ) + s[k] 가 되고d[k][2]일때는 반드시 직전 계단인 k-1번째 계단을 밟았을 것이므로 d[k-1][1] + s[k] 가 된다. #include "bit..
· PS
1463. DPhttps://www.acmicpc.net/problem/1463 [풀이]BFS로도 풀이 가능하지만 점화식을 세워 DP로 풀이가 가능하다.d[1] = 0으로 두고 입력값 X일 때 연산의 최솟값을 d[X]라고 하면 d[2]부터 d[X]까지 for문으로 돌아가며 최솟값을 구할 수 있다.#include "bits/stdc++.h"using namespace std;int d[1000001];int main(){ ios::sync_with_stdio(0); cin.tie(0); int input; cin >> input; for (int i=2; i tmp; if (i%3==0) tmp.push_back(d[i/3] + 1); // 3으로 나눌 때 if (i%2==0) tmp.push_ba..
· PS
1929. 에라토스테네스의 체https://www.acmicpc.net/problem/1929[풀이]일반적으로 n이 소수인지를 판별할 때 n을 2부터 n-1까지 나눈 나머지로 판별한다. 시간복잡도가 O(n)이다.그러나 m과 n 사이의 소수를 판별할 때는 이중 반복문이 사용되어 O(n^2)이 된다. n의 최대크기가 1,000,000정도로 커졌을 때 위와 같은 방식으로는 시간초과를 피할 수 없다. 그래서 에라토스테네스의 체라는 수학적 방법을 사용하게 되는데, 그냥 이게 더 빠르구나하고 외우고 활용하는게 좋을 것 같다. 우선 최대크기의 배열을 하나 잡는다. 나는 a[1000001]라고 잡았다.1) 그리고 각 인덱스값을 값으로 할당해준다.2) 2부터 n까지 돌며 해당 배열의 값 중에 '어떤 수의 배수'인 값만 ..
· PS
1926. to_string()https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5PTeo6AHUDFAUq&categoryId=AV5PTeo6AHUDFAUq&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 3 6 9 게임을 프로그램으로 제작중이다. 게임 규칙은 다음과 같다. 1. 숫자 1부터 순서대로 차례대로..
· PS
10814. stable_sort() https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net [풀이] 해당 문제는 pair의 first를 기준으로 오름차순 정렬하는 문제인데 first가 같을 때 먼저 입력 받은 pair를 먼저 출력하는 문제이다. 그냥 sort를 사용해서 구현해도 입력받은 순서대로 정렬되는 것처럼 보이지만 실제로 이를 보장하진 않는다. 따라서 stable_sort()를 사용해 이를 보장받아야 한다. #include using namespac..
· PS
[풀이] n개 자연수 중 r개를 고르는 조합 문제이지만 nCr에서 r의 모든 경우의 수를 고려해야 하는 문제이다. 따라서 각 숫자가 포함되냐, 아니냐 두 가지 경우로 나눠 2^n 개의 경우의 수를 고려하는 문제로 바꿔 생각할 수 있다. 예를 들어, n=3이고 {1,2,3}을 고려해야하는 문제라면 3C0, 3C1, 3C2, 3C3 네 가지 경우를 모두 고려해야 하며 해당 경우의 수는 모두 1+3+3+1 = 8가지인데, 각각을 포함되냐 포함되지 않냐로 구해도 마찬가지로 2^3 = 8가지 이다. 이를 재귀함수를 이용해 구현하면 다음과 같다. vector v; int n, ret; void go(int idx, int sum) { if (idx == n){ ret = max(ret, sum%11); return..
· PS
1260. 노드와 간선으로 이루어진 DFS, BFShttps://www.acmicpc.net/problem/1260 1260번: DFS와 BFS첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사www.acmicpc.net [풀이]노드와 간선으로 BFS, DFS 문제를 해결해야 하는 경우, 아래 그림의 이론을 바탕으로 코드를 짜야한다.간선을 vector adj[1000] 으로 노드를 int vis[1000] 로 구현한다.#include using namespace std;vector adj[1002];int vis1[1002];int..
· PS
1697. BFS https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net [풀이] 문제를 보고 BFS라는 것을 알아야 하는 문제이다. 꼭 2차원배열에서 상하좌우로 움직이지 않더라도 1차원배열에서도 앞 뒤로 움직이는 문제를 BFS로 해결할 수 있다. 또한 해당 코드에서 N과 K가 같을 때를 edge case로서 예외처리 해주어야 한다. #include using namespace std; int board[1000000]; i..
· PS
2178. BFS https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net [풀이] 각행의 수들은 붙어서 입력이 들어온다. 이러한 경우 이중 for문을 통해 입력받는 방법을 코드로 확인할 수 있다. 2차원 배열 board을 선언할 때부터 문자열의 배열로 선언할 수도 있지만 더욱 실수할 확률이 높다. 뿐만 아니라 각 칸의 dist 배열을 2차원으로 초기화하는데 이중 for문이 필요하기 때문에 같이 사용하면 된다. #include using namespace std; #define X f..
· PS
1620. Map https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net [풀이] 시간복잡도에 관계없이 코드를 짜면 vector를 사용한 구현 방법도 존재하고 map 하나만 사용한 구현 방법도 가능하지만 모두 시간초과가 발생하며 map와 map 두 개의 map을 사용한 구현 방법만이 Accepted를 받을 수 있다. 1) 먼저 pair의 vector 를 사용한 코드를 보자 vector a; int N,M; int main(..