개발개발

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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #include #include #define MAX 1001 using namespace std; char map[MAX][MAX]; struct point { int row, col; bool isBroken; // 벽 부쉈으면 true int length; // 이동 거리 }; int BFS(int rowSize, int colSize) { int moveDir[4][2] = { { 1, 0 },{ -1, 0 },{ 0, 1 },..

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 #include #include #include #include using namespace std; int main() { int t; cin >> t; string cloth, kind; while (t--) { int n; cin >> n; map m; // 옷 종류와 종류별 수를 담는 map while (n--) { cin >> cloth >> kind; m[kind]++; // 옷 종류별 수 갱신 } long long res = 1; for(auto it = m.begin(); it != m.end(); it++){ res *= it->second + 1; ..

1. 첫번째 원소 기준으로 정렬 bool compare(const pair &a, const pair &b){ return a.first < b.first; } 2. 두번째 원소 기준으로 정렬 bool compare(const pair &a, const pair &b){ return a.second < b.second; } 사용시 sort(v.begin(), v.end(), compare);

1.문제 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 2. 풀이 가장 긴 증가하는 부분수열은 LIS(Longest Increasing Sequence)로 매우 유명한 알고리즘이다. DP를 이용하는 문제는 매번 어렵다. 문제에는 두가지 배열이 있다. 숫자들의 나열이 담긴 배열 현재 인덱스에 해당하는 숫자까지의 LIS를 저장하는 배열 문제에서 2)의 배열에서 이전까지..

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

코드 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)..