asdsa112 님의 블로그

1. N은 50. 집의 갯수 최대 2500개 치킨집의 개수는 13개. 13C6(치킨집 고르는 경우의 수) * (100*100)(집에서 치킨집 가는 탐색) * 6개 라고 해도 1억회는 안넘고, 1초까지는 안걸림. 1. 최대 M개를 고르라니까 조합을 써야되겠다 ! 하는 사고방식이 일어나야 함.2. 그리고는 완전탐색으로 일일히 거리 계산해주면서 최소값 구하면 됨. #include using namespace std;using pii = pair;int N, M;int board[51][51];int visited[14];vector cv;vector hv;vector indexv;int res = 987654321;int cal(int y1, int x1, int y2, int x2){ return a..

1. N이 최대 20개. 20 X 20의 배열이 가능함.2. 그러면 한 행, 한 열당 뒤집거나 안뒤집으니 2의 40승임.3. 기존의 사고방식으로는 정면돌파 불가능함. 1. 행에서 한번 뒤집으면, 열은 이미 최소값이 정해져 있음.2. 뒤집힌 행에서 열은 어차피 뒤집으면 되기 때문에, 앞이건 뒤건 상관없이 적은 갯수만 세면 된다는거임. 3. 그렇게 되면 행이나 열만 뒤집으면 되니, 2의 20승으로 줄어듦.4. 그리고 경우의 수 문제니 재귀를 돌면서 뒤집는 경우의 수 혹은 안뒤집는 경우의 수로 해보고, 최소값을 구하면 됨. #include using namespace std;int N;vector arr;int res = 987654321;void go(int here){ if (here == N) ..

1. N개의 식재료 중에서 골라서 경우의 수 따지는 문제임.2. N이 15이하 이므로 비트마스킹으로 접근해볼 수 있겠음.3. 그러면 최대 시간복잡도가 2^15정도니까 충분함. 1. 비트마스킹 로직은 흔한 비트마스킹 로직이라 괜찮음.2. 출력이 문제인데, 오름차순 + 같은 비용의 집합이 하나 이상이면 사전 순 출력임.3. map으로 (최소 비용, idx배열을 담는 vector) 쌍으로 관리해서 집합을 사전 순 정렬하면 됨. 출력이 .. 좀 ... 재미없다 .. #include using namespace std;struct diet{ int p; int f; int s; int v; int price;};int N;int mp, mf, ms, mv;int res = 9876..

C++로 만든 Iocp Server 및 winapi 클라이언트를 연동한 C++ 프로젝트를 C#으로 하나의 단일 게임엔진으로 통합하는 과정이었습니다. 근데 C++에서는 winapi의 함수 호출은 #pragma comment('user32.lib') 뭐 이런 걸로 user32라이브러리 파일을 통해서 링크한 후 CreateWindowExW 이런 함수들을 쓰면 그만이었는데, 막상 C#으로 통합하려하니까 C#에서는 어떻게 하지 ? ?? ? ? 라는 문제점에 봉착했습니다. 1. 일단 런타임이든 윈도우 생성이든 네트워크든간에 OS 기능을 빌려와야 함. - OS는 그 기능을 native dll (x64/x86 기계어 dll 파일)형태로만 노출하기 때문에, 해당 native dll에 접근해서 가져오면 되겠습니..

1. 시간제한은 모르겠지만, 배열 크기 100만이기 때문에 순회 한번에 끝내볼 것임. 1. answer에 비어 있으면 넣고, 만약 안 비어있으면 맨 위에 요소랑 비교해보고 다르면 삽입함. #include using namespace std;vector solution(vector arr) { vector answer; for (auto item : arr) { if (!answer.empty() && answer.back() == item) { continue; } else { answer.push_back(item); } } return answer;}

1. 알약이 최대 30개인데 반으로 쪼개 먹을 수도 있으니 최대 60번. 그러면 먹냐 안먹냐니까 최대 경우의 수가 2^60까지 될 수 있음. 2. 가능한 문자열의 경우의 수기에 경우의 수 덧셈으로 진행하면 될 것 같음. 1. 2^60은 말도 안되지만, 경우의 수 덧셈이라면 얘기가 다름. 2. 재귀로 경우의 수를 돌면서 메모제이션을 진행하면 충분히 가능할 수 있음. 3. 알약 한 조각을 꺼내면 반 조각 갯수를 올리고, 만약 반 조각을 먹는다면 한 조각 갯수를 안 내리면 됨. #include using namespace std;int n;long long dp[40][40];long long go (int day, int half){ if (day 0) { if (half 0) ..

1. 30번 이동 가능. 나무는 1번 나무, 2번 나무 존재. 그러면 경우의수가 최대 2^30임. (1번 나무 혹은 2번 나무를 30번 이동 가능하니까). 2. 그럼 무식한 완전탐색으로는 불가능. 지나왔던 길을 저장하는 방법을 택해서 복잡도를 줄여봐야 함. 1. 현재 위치에서 받을 수 있는 자두 경우의 수, 다음 위치에서 받을 수 있는 자두 경우의 수를 재귀 때 더해주는 것이 포인트임. 2. DP는 재귀 때 경우의 수를 더해주면서, 재귀 탈출 루프에서는 0의 경우의 수를 던지는 게 포인트 인 것 같음. #include using namespace std;int t, w;int tree[1004];int dp[3][31][1004]; // 현재 위치 , 남은 이동 횟수, Timeint go(int cu..

1. 프로그래머스는 제한 시간 이런게 없어서 조건 생각하기가 어렵다고 생각함. 2. 문자열 갯수가 10만 이하라 그냥 순회만 하면서 체크해도 충~~~분할 것 이라 생각했음. 3. 벡터를 추가해서 push_back() 연산이나 pop_back() 연산을 추가하니 시간초과가 생겼음. 4. 그만큼 빡빡하다는 거였음. 1. 최대한 string을 한번만 순회하되, 새로운 STL 컨테이너를 추가해서 함수 호출 연산을 추가하면 시간초과가 일어남. 2. 여는 괄호를 +1로, 닫는 괄호를 -1로 count 체크를 진행하면 됨. 3. 중간에 음수가 발생하면 닫는 괄호가 많아졌다는 뜻이니 false, 순회가 끝나고 count가 0이 아니면 짝이 안맞는다는 소리니 그것도 false. #include using namesp..

1. 솔직히 조건 분석이라고 하기에는 progresses의 갯수가 너무 적음. 2. 그냥 구현 문제라고 보면 될 듯함. 1. progresses 첫 요소가 100이상이면 그때 다 돌면서 100을 넘는지 체크해보기 정도가 포인트가 될 듯함. #include using namespace std;vector solution(vector progresses, vector speeds) { vector answer; int index = 0; while (index = 100) { int cnt = 0; for (int i = index; i = 100) { cnt++; ..

1. 만약 완탐으로 해보겠다. 라고 생각한다면,4방향, 50*50보드면 4^2500 경우의 수임. 2. 그럼 방문처리해서 DFS 식으로 혹은 DP로 간다면 O(M*N)에 상수 4방향 해서 약 10000번 정도. 1. 방문 처리 된 곳을 방문했다면 사이클 이므로 -1을 출력하고 exit 하는 것도 방법. 2. DP는 DFS가 탐색하고 있는 그 경로 자체의 함수 호출스택이 경우의 수를 탐색하고 있는 거라고 생각해보면 됨. 3. 그렇게 생각하면 맵을 벗어났을 때는 게임이 끝난 것 이므로 경우의 수 0을 반환. go 재귀로 들어갈 때는 경우의 수 1개가 추가되는 거임. #include using namespace std;int n, m;int dp[50][50];char board[50][50];int v..