전공 지식/자료구조 && 알고리즘
-
Floyd’s Tortoise and Hare - Two Pointers전공 지식/자료구조 && 알고리즘 2025. 4. 9. 01:05
LinkedList 에서 Cycle 이 존재하는지 확인 & Cycle 이 시작하는 위치를 찾는 방법 bool hasCycle(ListNode *head) { ListNode* slow = head; ListNode* fast = head; while(fast != NULL && fast->next != NULL) { slow = slow -> next; fast = fast->next->next; if(fast == slow) return true; } return false; } * Cycle 이 있다면 결국 두 포인터가 만난다 라는 부분에서 착안함.- Cycle 이 ..
-
Boyer moore majority vote algorithm 보이어무어 과반수 투표 알고리즘전공 지식/자료구조 && 알고리즘 2025. 3. 16. 19:17
Boyer moore majority vote algorithm 보이어무어 과반수 투표 알고리즘- 배열에서 과반수를 차지하는 숫자를 시간복잡도 O(n), 공간복잡도 O(1) 에 찾을 수 있는 알고리즘- 항상 과반수가 존재 할 때 성립하는 알고리즘임 int candidate = nums[0];int count = 1;for(int i = 1; i 1. 과반수가 될 후보를 골라낸다. 처음은 nums[0];2. 반복문을 돌며 과반수가 맞는지 확인하는 과정을 거친다.2-1. 과반수에 해당하는 숫자가 없다면 현재 숫자를 과반수 후보로 지정2-2. 현재 숫자가 과반수 후보와 같다면 갯수를 1 증가 시킨다.2-3. 과반수 후보와 다르다면 1을 감소 시킨다.--------------------------------..
-
-
Minstack 구현하기 , leet code Min Stack전공 지식/자료구조 && 알고리즘 2018. 12. 7. 15:14
leetCode 문제를 풀던 중 Min Stack 문제를 만나게 되었다. (https://leetcode.com/problems/min-stack/)기본 스택과 할 수 있는 기능은 똑같은데 getMin 함수를 통해 min 값을 추출하는 것이 중요하다. 나는 여기서 stack 이 현재 min값과 자신의 값을 둘다 가지고 있으면 해결할 수 있을 것이라 생각했다.이제 어떻게 풀었는지 보여주겠다. class MinStack { public: stack st; MinStack(){ } void push(int x) { int mmin; if(st.size() == 0) mmin = x; else mmin = min(st.top().second, x); st.push({x,mmin}); } void pop() { ..
-
스택으로 큐 구현하기!전공 지식/자료구조 && 알고리즘 2018. 12. 7. 15:07
스택과 큐는 push, pop 하는 위치가 완전히 반대이다.스택을 이용해서 큐를 구현할 수 있다~ stack st1; stack st2; void push(int num) { st1.push(num); } int pop() { if(st2.empty()) { while(!st1.empty()) { int num = st1.top(); st1.pop(); st2.push(num); } } int ret = st2.top(); st2.pop(); return ret; } int top() { if(st2.empty()) { while(!st1.empty()) { int num = st1.top(); st1.pop(); st2.push(num); } } return st2.top(); } 이제 이 함수를 가지..
-
2293 동전1전공 지식/자료구조 && 알고리즘 2018. 12. 7. 13:52
동전 DP는 왜 매번 헷갈릴까? 까먹고 헷갈리고 맨날 이렇다 정리하면 안그럴꺼라고 믿고 정리를 해서 확실히 알아둬야겠다 https://www.acmicpc.net/problem/2293 우선 동전1 문제이다. 각 동전들을 사용하여 K원을 만들 수 있는 경우의 수를 출력하는 문제이다. 생각해 보아야 할 것은 *순서만 다른 것은 같은 경우이다* 와 *경우의 수* 이다. 이 문제를 어떻게 해결할까? 사실 답은 간단하다. N개의 동전을 쓸 것인데 지금 만들 수 있는 돈이 있을 때, 그 동전을 사용해서 만들 수 있는돈에 그 경우의 수를 포함시켜주면 된다. 사실 이걸 이해하는 데 까지 오래걸렸었지만 이제 간단하다는 것을 알게 되었다. int dp[10010]; int arr[101]; int n,k; int mai..