컴퓨터공학 & 정보통신79 [알고리즘/수학] 나머지 분배 법칙 개요 나머지 분배 법칙은 사칙 연산의 분배 법칙과 다릅니다. 나머지 분배 법칙 아래 분배 법칙을 적용한 결과, 사칙 연산의 분배 법칙과 다르게 기존의 나머지 연산 적용이 남아있습니다.( a + b ) % mod = ( a % mod + b % mod ) % mod 알고리즘 문제에서의 주의점 간혹 알고리즘 문제에서 오버플로를 피하기 위해 편의 상 N을 나눈 값을 출력하라고 합니다. (예: 1000000) 앞서 설명했듯 나머지 분배 법칙은 사칙 연산의 분배 법칙과 다르다는 점을 명심해야 합니다. 두 개 이상의 경우에 수를 문제 풀이 과정에서 연산해야 하는 경우 한꺼번에 묶어서 나누어 주어야 합니다. 아래 두 연산은 서로 다른 값을 도출하기 때문입니다. 알고리즘 문제에서 요구하는 사항을 정확히 인식해서 나누어.. 2024. 8. 23. [백준] 1946 신입 사원 c++ 접근 두 가지의 성적을 비교하여 신입 사원 간 우위를 확인하기 위해서는 서류 성적을 먼저 정렬할 필요가 있어 보입니다. 그 후 면접 성적을 비교하여 가장 많은 신입 사원의 수를 계산해야 합니다. 정렬 후 첫 번째 신입사원은 다른 신입사원보다 반드시 서류 성적이 뛰어날 것이므로 면접 성적이 어떻게 되었든 반드시 합격하는 신입사원입니다. (정렬 후 그리디한 접근이 이 문제에서 반드시 최대의 경우의 수를 도출하는 이유입니다.) 첫 번째 신입 사원과 두 번째 신입사원의 면접 성적과 비교하였을 때, 만약 첫 번째 신입사원보다 면접 성적이 좋은 경우 두 번째 신입사원을 비교 기준으로 변경합니다. 달리 얘기해서, 이미 서류 성적이 낮은 세 번째 네 번째 ... 신입 사원들은 두 번째 신입사원보다 면접 성적이 높기만 .. 2024. 8. 11. [알고리즘] Strict Weak Ordering C++ 에 대한 이해 개요C++ sort 함수에 비교 함수를 직접 작성할 때, segment fault 에러가 발생할 수 있습니다. 작성한 비교 함수가 strict weak ordering 를 만족하지 않아서 에러가 발생합니다. Strict Weak Ordering일련의 순서를 결정하는 weak ordering의 종류 중 하나입니다. C++ sort 함수의 비교 함수는 Strict Weak Ordering 을 만족해야 합니다.Stict Weak Ordering은 아래 조건들을 만족해야 합니다. For all a, comp(a, a) == false.If comp(a, b) == true then comp(b, a) == false.if comp(a, b) == true and comp(b, c) == true then co.. 2024. 8. 10. [백준] 2178 미로 탐색 c++ 개요 항상 완전 탐색 문제가 모두 bfs 및 dfs로 풀 수 있는 것은 아닙니다. 이 문제는 bfs로 풀어야 하는 문제입니다. 접근 방법 (1,1) 좌표에서 (N,M) 좌표까지 이동하기 위해 필요한 최소 칸 수를 구해야 합니다.BFS 또는 DFS 기법을 통해 탐색을 해야 합니다.일반적인 완전 탐색의 조건은 아래와 같습니다.문제 요구사항에 만족하는 범위에 위치좌표의 값이 0이 아니며처음 방문문제 특성 상 (1,1)좌표를 제외하고 좌표의 값이 1인 경우일 때, 무조건 처음 방문하는 좌표입니다. 따라서 처음 방문하는 좌표를 계속 탐색하며 값을 갱신해 주면 됩니다. 솔루션#include #include #include #include using namespace std;int N, M;int dx[4] = {.. 2024. 8. 9. [백준] 17485 진우의 달 여행 (Large) c++ 개요 인터넷에 유사한 풀이가 없어 해당 문제의 솔루션을 공유합니다. 체크리스트 DP 문제 유형임을 알고 접근했는가? DP 3차원 자료구조로 풀이를 작성했는가? 접근 방법 DP[i][j][k] 는 i행, j열에 왔을 때, 마지막으로 k 방향(0, 1, 2)으로 움직여 도착한 모든 경우의 수 중 최소 비용입니다. 예를 들어 DP[i][j][0] 은 DP[i-1][j+1][1] 과 DP[i-1][j+1][2] 중 더 작은 값과 현재 위치의 비용을 더한 값이 됩니다. (i-1행 j+1열에서 왼쪽으로 이동하여 i행 j열로 도착했기 때문) 솔루션을 간단하게 작성하기 위해 벡터의 크기를 +2 하여 2e9 (int 자료형에 담을 수 있는 정수 중 최댓값 근사값) 을 저장했습니다. 솔루션 #include #include.. 2023. 11. 17. [알고리즘/메모] C++ STL sort compare 함수 템플릿 개요 #include 에 sort 함수 내 comapre 함수에 대한 코드 예제입니다. 코드 템플릿 compare에서 참을 반환하는 조건을 기준으로 정렬됩니다. sort(target.begin(), target.end(), compare); #1 compare 예제 a < b 기준, 즉 올림차순으로 정렬됩니다. bool compare(int a, int b){ if(a < b){ return true; } return false; } #2 compare 예제 a 벡터 내 1번째 원소와 b 벡터 내 1번째 원소를 기준으로 올림차순 정렬 bool compare(vector a, vector b){ if(a[1] < b[1]){ return true; } return false; } #3 compare 예제 .. 2023. 10. 19. 이전 1 2 3 4 5 6 ··· 14 다음
