software engineering/PS
<안내글>
알고리즘 문제풀이는 특별한 경우가 아니면 앞으로는 블로그 대신 아래 레포지토리에 기록할 예정입니다. https://github.com/hagukin/PS
software engineering/PS
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
software engineering/PS
boj 16724
#include using namespace std; int N, M; string grid[1001]; int visited[1001][1001]; int ret = 0; char getGrid(int y, int x) { return grid[y][x]; } void dfs(int y, int x, int num) { if (y>=0 && x>=0 && y N >> M; for(int i=0;i> grid[i]; } int cnt = 0;//cnt != ret for (int i=0;i
software engineering/PS
boj 2225 (top-down & bottom-up)
// top-down과 bottom-up 감을 찾을 수 있는 좋은 베이직한 문제 // 두 방식 모두로 풀이가 가능하다. // top down #include #include using namespace std; int N, K; long long dp[201][201]; long long sumCnt(int n, int k) { if (n==0) return 1; if (k==1) return 1; if (dp[n][k]) return dp[n][k]; for (int i=0;i> N >> K; memset(dp, 0, sizeof(dp)); cout > n >> k; memset(dp, 0, sizeof(dp)); for (int i=0;i 0 0 0 여기 끝에 6붙여서 0 0 0 6 만들면 경우의 수..