software engineering/algorithms
<안내글>
알고리즘과 관련된 정리 내용은 앞으로 특별한 경우가 아니면 아래 레포지토리 내 문서에 기록할 예정입니다. https://github.com/hagukin/PS/blob/main/algorithms.md
software engineering
software engineering/PS
<안내글>
알고리즘 문제풀이는 특별한 경우가 아니면 앞으로는 블로그 대신 아래 레포지토리에 기록할 예정입니다. https://github.com/hagukin/PS
software engineering/algorithms
이분탐색, 파라메트릭 서치
https://marades.tistory.com/7 이진탐색(Binary Search)와 파라메트릭서치(Parametric Search) 오늘 처음으로 소개할 알고리즘은 이진 탐색과 파라메트릭 서치입니다. 많은 분들이 이진 탐색에 대해선 많이 들어보셨을거라 생각하지만 파라메트릭 서치라는 알고리즘은 아마 생소하신 분 marades.tistory.com 관련 문제: BOJ 1114 https://dongwoo338.tistory.com/13 [boj 1114] 통나무 자르기 www.acmicpc.net/problem/1114 알고리즘 : 이분탐색(파라메트릭) + 그리디 몇주 전 풀고 올려야지! 하고 생각만 하다 이제야 올리는 문제다. 처음에 문제 분류가 그리디 + 이분탐색으로 되있어서 난 그리 dongwo..
software engineering/PS
boj 17619
#include #include #include using namespace std; constexpr int MAXN = 100002; int N, Q; int x1[MAXN]; int x2[MAXN]; int logSorted[MAXN]; // x1기준 오름차순으로 정렬된 Log들의 인덱스 int logGroup[MAXN]; // x1기준 오름차순으로 정렬된 Log들의 그룹번호 int logOrder[MAXN]; // logOrder[log.ind] = 정렬순서 /* logs - 그냥 값 저장 logSorted 1 3 2 4 5 6 logGroup 0 0 0 0 1 1 logOrder X 0 2 1 3 4 5 3번과 5번 연결 확인: logGroup[LogOrder[3]] == logGroup[Log..
software engineering/PS
boj 1670
#include #include constexpr long long MOD = 987654321; using namespace std; long long dp[5001]; // dp[k] = k*2일때의 값 int N; long long getCnt(int x) { if (dp[x/2]) {return dp[x/2];} if (x==0) return 1; // inner or outer가 0일 경우 long long ret = 0; for (int i=1;i> N; memset(dp, 0, sizeof(dp)); dp[1] = 1; dp[2] = 2; cout
software engineering/PS
boj 1765 (union-find)
#include #include #include using namespace std; int n, m; vector enemList[1001]; int group[1001]; bool isRoot[1001]; int getRoot(int a) { if (group[a] == a) return a; else { int tmp = getRoot(group[a]); group[a] = tmp; // update root return tmp; } } void unionTwo(int a, int b) { // 루트끼리 합쳐야 한다 int ra = getRoot(a); int rb = getRoot(b); if (rb > ra) group[rb] = ra; else group[ra] = rb; } int getGr..
software engineering/PS
boj 2011 (bottom-up)
#include #include #include using namespace std; constexpr int DIVN = 1000000; int memo[5001]; // memo[i] = s[i,s.length() - 1]로 만들 수 있는 모든 암호의 갯수. string s; void wrongInput() { cout s; if (s.empty()) {wrongInput(); return 0;}; // 빈 암호문 int ei = s.length()-1; if (s[ei]!='0') memo[ei] = 1; for (int i=ei-1; i>=0; i--) { if (s[i+1] == '0' && s[i] == '0') {wrongInput(); return 0;} if (s[i]!='0' && s[..
software engineering/PS
boj 14890
#include #include #include using namespace std; int N, L; int hmap[101][101]; bool slope[101][101]; int ret = 0; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); memset(hmap, 0, sizeof(hmap)); memset(slope, false, sizeof(slope)); cin >> N >> L; for (int i=0;i hmap[i][j]; } } // 가로줄 경로 for (int i=0;i