Little Jay

시험기간에 너무 공부가 안되서 푼 문제 KMP, Boyer-Moore, NP-Hard, NP-Complete 등등 너무 어렵다 정말 학교에서 알고리즘 과제하는데 string pattern matching 알고리즘이 너무 어려워서 string 관련 문제 하나 풀었다. 어렵지는 않은데 입력을 받을때 cin >> str을 하면 틀리고, getline(cin, str)을 해주면 맞았다 이건 또 왜 그런지 잘 모르겠다 백분율 구하는 문제라서 크게 어렵지는 않았던 문제 #include using namespace std; map m; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string str; float cnt = ..

Creating New Process 새로운 Process를 만드는 데에는 여러가지 방법들이 있다. Directly하게 Process를 생성하는 경우가 있지만, Cloning과 Replacing 기법을 사용해서 새로운 Control Flow를 지니는 Process를 생성한다. Clonging하는 것은 말 그대로 복제본을 하나 생성하는 것이다. 이때 생성된 Process를 Child Process라고 부르는데, 이 Process는 Parent Process, 즉 자신을 만든 Parent Process와 PID(Process ID)만 빼고 나머지가 같다. 이러한 Child Process를 만드는 것은 fork() system call을 통해 가능하다. 이를 Process Spawning이라고도 하며, Cal..

1, 2가 입력되었을때를 생각안했다가 틀렸던 문제 base case에 대해서도 항상 생각하자 #include #define endl '\n' using namespace std; int n; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; int left = 1; int right = 2; int total = 1; int ans = 0; if (n == 1 || n == 2) { cout

Process 프로세스에 대한 정의는 다양하다. OS를 다루는 부분에서도 설명을 또 할것이지만, 여기서도 정의를 해보겠다. Process는 프로그램이 실행 준비가 되어 메모리에 올라가있는 상태이다. 이를 반대로 말하자면 Program은 아직 Code의 형태로 Disk에 존재하는 것이다. 조금더 상세히 명세를 하자면, Program의 Code와 Data가 Memory에 저장된 상태이다. 이때 OS는 PCB라는 Data Structure을 활용해서 Process를 나타낸다. Process는 각 Program에게 두 가지 Key Abstraction을 제공한다. 이는 Independent Logical Control Flow, Private Address Space인데, Independent Logical C..

최근에 알고리즘 수업을 들으면서 Kruskal Algorithm을 기반으로 한 Strongly Connected Component를 구하는 과제를 수행했었다. DFS를 두번 수행하는 이 알고리즘은 구현의 난이도가 Tarjan's Algorithm보다 쉽기때문에 인터넷에 많이 올라와 있었다. 그래서 내 코드의 표절률에 대해 궁금해졌고, 비교군의 파일 하나와 내 코드를 비교해보았다. 이 방식은 인도인 유튜브에 있는 방식을 한글로 받아 적고, 다른 곳에서 정리된 것을 내가 모은 것임을 알리고 시작한다. https://www.youtube.com/watch?v=5CyOTf2DHSg 먼저 moss@moss.stanford.edu 에게 메일을 보내야한다 제목은 상관없고 본문에 registeruser mail 자기이..

파티션을 활용한 브루트포스 문제 #include #define endl '\n' using namespace std; int n; int arr[11]; int calc(int start, int end) { int x = 1; for (int i = start; i > n; for (int i = 1; i > arr[i]; } int temp, ans = 0; for (int i = 1; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { temp = calc(1, i) + calc(i + 1, j) + calc(j + 1, k) + calc(k + 1, n); ans = max(ans, temp); } } ..

인접행렬로 문제를 푸는 것을 선호하는데, 이렇게 인접 리스트로 푸는게 오랜만이라 시간이 좀 걸렸다. 항상 느끼는 거지만 인접행렬이 더 편한 것 같다. #include #define endl '\n' #define MAX 100005 using namespace std; int n, m, init; vector v[MAX]; bool visited[MAX]; int solve() { int cnt = 0; queue q; q.push(init); visited[init] = true; while (!q.empty()) { auto current = q.front(); q.pop(); if (!v[current].size()) { return cnt; } if (visited[v[current][0]]) b..

입력받는것을 계속 int로 받다가 실패했다. 띄어쓰기가 없는 것은 char이나 string으로 받아야 하는 것에 유의하자. n-1일때 return true 해야하는데 m-1로 계속 써서 실패했다. 항상 조건을 잘 보도록 하자. #include #define endl '\n' using namespace std; int n, m; int board[1005][1005]; bool visited[1005][1005]; const int dx[4] = { 1, -1, 0, 0 }; const int dy[4] = { 0, 0, 1, -1 }; bool bfs(int y, int x) { visited[y][x] = true; queue q; q.push({ y, x }); while (!q.empty()) {..

Status Register CPU에는 Status Register, PSW라는 아주 작은 레지스터를 지니고 있다. 이는 CPU의 current status를 저장하기 위한 레지스터이다. CPU는 이 레지스터를 통해 코드의 flow를 Control하게 된다. Status Register는 인텔 x86 아키텍쳐에서는 Condition Code를 저장한다고 한다. Condition Code는 Single Bit으로서 이를 통해 flag를 저장한다. 이 Flags들은 operation의 결과에 따라 set된다. 일반적으로 많이 알려진 Condition Code에는 CF Carry Flag ZF Zero Flag SF Sign Flag OF Overflow Flag 등이 존재한다. 앞선 포스팅에 나와있는 레지스..

greedy한 문제였다 단순히 닭이 소의 시간 안에 들어있는지 아닌지를 파악해주면 되는 문제라 쉬워보였지만, 소를 priority queue로 정렬하는데에 있어서 시작시간만을 기준으로 정렬하면 틀리는 문제였다. priority queue의 정렬 함수를 구현하는 것이 결국 관건이었던 문제이다 #include #define endl '\n' using namespace std; int c, n; struct comp { bool operator()(pair a, pair b) { if (a.second != b.second) return a.second > b.second; return a.first > b.first; } }; vector chicken; priority_queue cow; int main..