개발개발

1. 문제 https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 2. 풀이 숫자들이 여러개 입력 될 때 각 숫자는 n = a * x + r(x는 나누는 수, a는 몫, r은 나머지)로 표현 할 수 있다. A, B, C,.... 이렇게 숫자가 오름차순을 나열 되어있다고 할 때, 각 숫자들은 a * x + r, b * x + r, c * x + r....로 표현 될 수 있고 r = A - a * x = B - b * x A - B = x * (a - b) 로 근접한 두..

1. 문제 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 2. 풀이 큐에 출력 해야 하는 순서를 넣고, 스택에 수들을 넣었다 빼며, 답을 넣는다. 숫자들은 오름차순으로 스택에 들어가므로 현재 스택에 들어갈 숫자를 변수로 잡아 이를 증가시키며 스택에 숫자를 넣는다. while문을 통해 큐의 원소가 없을 때 까지, 즉 모든 숫자를 출력할 때 까지 아래의 과정을 반복..

1. 풀이 큐 내 문서를 이동할 때 마다 인덱스가 변하므로 처음 입력받은 문서의 인덱스를 중요도와 함께 저장한다.(queue) 현재 있는 문서들 중 중요도가 높은 것 부터 출력해야 하는데 큐 자료구조 상 먼저 넣은 것이 먼저 출력되므로 중요도를 역순으로 큐에 넣는다.(queue numbers). 중요도에 따른 카드수를 저장한다.(int cardNum[10]) 큐가 빌 때 까지 큐의 첫 원소를 꺼내서2) 그렇지 않은 경우 큐의 뒤에 다시 넣는다. 1) 남은 카드들의 중요도 중 가장 높은 경우 카드 수와 중요도를 갱신 +) 꺼낸 원소가 답일 경우 -> 결과를 리턴하며 종료한다 2. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26..

1. 문제 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 2. 풀이 백트래킹을 이용해 풀었다. 재귀를 이용해 넣을 수 있는 숫자를 계속 넣어가면서 빈칸을 채워가다가 넣을 수 없는 숫자가 온 경우 이전의 빈칸의 숫자를 수정한다. 과정은 다음과 같다. 빈 칸의 좌표를 저장 첫번째 빈칸부터 for문을 이용해 1부터 9까지 숫자를 증가시켜가며 넣을 수 있는 숫자가 있는지 확인한다. 넣을 수 있는 숫자가 있는 경우 그 숫자를 빈 칸에 넣는다. 넣을 수..

코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include using namespace std; int r, c;int sheepRes = 0, wolfRes = 0; // 최종 양, 늑대 수char map[251][251]; // 지도bool visit[251][251]; // bfs 수행시 방문 여부를 표시할 배열queue q; // bfs에 이용할 큐. int nowX, nowY, newX, newY; void bfs(int i, int j) { int move[4][2] = { { 1, 0 },{ -1, 0 },{ 0,..

1. 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 2. 풀이 입력 받은 수부터 연산을 수행해가며 가장 횟수가 적은 경우를 얻기 위해 DP 배열에 각 경우의 값을 저장한다. 입력 받는 수를 X라 했을 때, X/3, X/2 X-1로 총 3가지 연산이 가능하다. 세 연산이 모두 가능한 상황 일 경우 X-1이 가장 큰 연산횟수가 드는 것이 확실히며 X-1 연산은 모든 경우에 가능하므로 X-1 연산을 한 경우의 값을 DP 배열에 가장 먼저 저장한다. X-1 연산을 수행할 경우의 결과를 기본 값으로 두고 두 연산이 가능할 경우에 각각의 연산을 수행해 두 연산(..

코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include #include #include using namespace std; struct n { int number; // 숫자 string res; // 연산과정}; bool isVisit[10001];queue q; int calD(int n){ // D연산 return (n * 2) % 10000;} int calS(int n) { // S연산 return n-1 >= 0 ? n-1 : 9999;} int calL(int n)..

코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include #include #include #include using namespace std; int len;char map[25][25]; // 실제 지도(0,1)bool visit[25][25] = { false, }; // 방문 여부 표시int dir[4][2] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 동서남북 이동queue q; // 모든 단지의 위치를 담는 큐 bool check(int row, int col) { ..

코드 1) pair 이용 현재 위치와 해당 위치까지 이동하는 데 걸린 시간을 함께 저장하기 위해 pair를 이용한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include #include using namespace std; int bfs(int s, int e) { bool visit[100001] = { false }; // 왔던 곳에 중복해서 가는 경우를 피하기 위해 queue q; // 현재 위치, 걸린 시간 q.push({ s,0 }); // 맨 처음의 위치, 시간을 큐에 넣음 while (!q.empty()) { pair now = q.front(); // 현재위치 걸린 시간 vis..