피너클의 it공부방

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이면 반복문을 종료..

문제 : https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 흔한 bfs문제다. bfs는 너비 우선 탐색으로 시작 정점에서 가까운 정점들을 우선으로 탐색하는 그래프 알고리즘이다. 이 문제에서 주의해야 하는부분은 bfs에서 방문한 정점을 저장하는 부분이다. 5에서 8로 갈때 5 -> 6 -> 7 -> 8 5 -> 10 -> 9 -> 8 이렇게 2가지 상황이 나올수 있다. 첫번째 상황에서 방문을 체크해버리면 두번째..

문제 : https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 입력 받은 값들중 합이 0에 가까운 두 수를 찾는 문제다. n이 100000일때 이중 for문을 돌리면 시간초과가 나기에 모든 값을 찾아보는건 힘들다. 입력 받은 값들을 정렬시킨다음 투 포인터를 이용해 하나씩 합을 맞춰보면 간단하게 풀수 있다. int a, b, sum = 2000000000; int start = 0, end = n - 1; int a와..

문제 : https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net bfs문제다. bfs는 너비 우선 탐색으로 시작 정점에서 가까운 정점들을 우선으로 탐색하는 그래프 알고리즘이다. 문제에서는 총 범위가 10000이고 특정 정점까지의 최소 명령어를 필요로 하는걸 보고 유추할수있다. 우선 D, S, L, R을 먼저 구현한다. int D(int n) { int num = n * 2; if (num >= 10000) return num % 10000..

문제 : https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 알고리즘을 사용하는 문제다. 다익스트라 알고리즘은 그래프 문제에서 한 정점에서 모든 정점까지 최소비용이 얼마인지를 구하는 알고리즘이다. int dist[1001]; // 비용 모든 정점으로의 비용을 가지는 배열이다. 처음에는 굉장히 큰 수로 초기화 된다. 다익스트라 알고리즘을 돌리며 계속해서 업데이트 해갈것이다. void dijkstra(int..