걸음마코딩기

문제풀이 처음에는 연결리스트 사용해서 circular queue를 사용해야겠다고 생각했다. 하지만 복잡하기 때문에 그냥 단순하게 필요한 순번의 번호가 나올때까지 뽑아서 다시 Queue 뒤에 저장하는 방식으로 야매 circular queue를 구현했다. Queue에 N만큼의 정수를 저장해준다. K-1번째까지의 원소를 pop해서 Queue 뒤에 push해준다. K번째의 원소를 pop해준다. Queue에 원소가 1개 남을때까지 반복해준다. (출력 형식때문에) 마지막원소를 출력해주고 마무리한다. 코드 #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int..

풀이과정 괄호 문제는 스택의 대표적 문제이다. 짝맞추는 문제이므로 '('가 들어왔을때만 스택에 넣어준다. ')'가 들어왔을 때 스택이 비어있다면 잘못된 괄호이므로 "NO"를 출력해주고 아니라면 짝이 맞았으므로 스택을 pop해준다. 문자열 길이만큼 진행한 뒤 스택이 비어있지 않다면 짝이 안맞았음을 의미하므로 "NO"를 출력한다. 스택이 비어있다면 짝이 다 맞았다는 것을 의미하므로 "YES"를 출력한다. #include #include using namespace std; void VPS(string inp) { stack s; for (int i = 0; i < inp.length(); i++) { if (inp[i] == '(') s.push('('); else { if (!s.empty()) s.pop..

간단하게 스택을 구현하면 되는 문제로, 배열을 써서 풀었고 STL stack을 사용한 간단한 버전도 올려놨다. [1차원 배열 이용] #include using namespace std; void push(int value); void pop(); void size(); void empty(); void top(); int N; int top_v = -1; int myStack[100000]; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string com; cin >> N; for(int i=0; i> com; if(com == "push") { int x; cin >> x; push(x); } else if(c..

🚦 이번 포스팅에서는 〰️ ▶️ 큐(Queue)란? ▶️ 큐(Queue) functions - C++ ▶️ 큐(Queue) 구현 방법 ▶️ 원형 큐(Circular Queue)에 대해서 ▶️ 우선순위 큐(Priority Queue)에 대해서 ▶️ 덱(Deque)에 대해서 ▶️ 큐(Queue) 사용 사례 ▶️ 스택(Stack) vs 리스트(List) vs 큐(Queue) 📎 큐(Queue) 란? 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 이는 나중에 집어넣은 데이터가 먼저 나오는 ..

🚦 이번 포스팅에서는 〰️ ▶️ 스택(Stack)이란? ▶️ 스택(Stack) functions - C++ ▶️ 스택(Stack) 구현 방법 ▶️ 스택(Stack) 사용 사례 ▶️ 스택(Stack) vs 리스트(List) vs 큐(Queue) 📎 스택(Stack)이란? 말 그대로 "쌓아놓은 더미"를 뜻한다. 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조이며, 대표적인 예시로 프링글스 통을 생각하면 좋다. 가장 최근에(마지막으로) 들어온 데이터가 가장 먼저 나간다는 의미로, 가장 먼저 들어온 데이터가 먼저 나가는 Queue의 반대개념이다. 📎 스택(Stack) functions - C++ 스택은 LIFO(Last In First Out) 형태로, 가장 ..

📌 정렬 알고리즘 사용 시 고려할 사항 시간 복잡도 메모리 사용량 안정성 (stability) : 데이터의 순서가 바뀌는지 여부 직렬 vs 병렬 💡 안정성을 고려하는 이유 : 모든 정렬 알고리즘은 같은 key를 가진 데이터의 순서를 안 바꾼다고 착각하기 때문이다. 📌 정렬 알고리즘을 선택할 때 고려할 사항 정렬할 데이터의 양 데이터와 메모리 이미 정렬된 정도 필요한 추가 메모리의 양 상대위치 보존여부 (안정성) 💡 대표적인 정렬 알고리즘의 시간복잡도 O(n^2) O(nlogn) Insertion sort ❗️best = O(n) in sorted list ❗️worst = O(n^2) in reverse sorted Quick sort ❗️worst = O(n^2) in already sorted lis..

단순한 sorting 문제로, 직접 구현해도 되지만 나는 간단하게 STL의 sort 함수를 이용했다. #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; int arr[N]; for(int i=0; i> arr[i]; sort(arr, arr+N); for(auto x : arr) cout a; arr.push_back(a); } sort(arr.begin(), arr.end()); arr.erase(std::unique(arr.begin(), arr.end()), arr.end()); for(auto x : arr) c..

🔅 Greedy Algorithm (탐욕 알고리즘)이란? ➡️ 선택의 순간마다 눈앞에 보이는 최적의 상황만을 쫓는 알고리즘 ➡️ 최적해를 구하는게 탁월하다 ❕ 순간마다의 선택은 그 순간에 대해서는 최적이지만, 선택들을 계속 수집한 최종적인 해답은 최적이라는 보장은 없다 ➡️ 탐욕 알고리즘을 적용하는 문제들은 지역적으로 최적 && 전역적으로 최적인 문제들이다. ➡️ 대표적인 문제 : 거스름 돈 문제 🔅 탐욕 알고리즘 구현 방법 1. 선택 절차 (Selection Procedure) : 현재 상태에서의 최적의 해답 선택 2. 적절성 검사 (Feasibility Check) : 선택한 해의 문제 조건 만족도 검사 3. 해답 검사 (Solution Check) : 원래의 문제 해결되었는지 검사하고, 해결되지 않..

A* 알고리즘이란? Dijkstra 알고리즘의 확장판으로 Best-First 검색을 이용해 시작점->도착점 까지의 가장 적은 비용을 사용하는 경로를 찾음 - 조사하지 않은 node중 가장 효율적이라 판단되는 node를 찾음 - 찾은 node가 도착점이면 종료, 아니면 인접 node들 중 다시 찾음 - 조사한 node들은 close list에 저장, 조사하지 않은 node들은 open list에 저장 ** Dijkstra 알고리즘은 시작노드만 지정하고 다른 모든 노드에 대한 최단 경로를 파악, A* 알고리즘은 시작노드와 목적지 노드를 분명하게 지정하여 이 두 노드간의 최단 경로를 파악한다는 것이 다르다! - 각 정점은 목적함수값 g(x)를 가지고있으며 best-first 검색을 통해 g(x)값이 가장 좋은..

KMP 알고리즘이란 ? 최대 접두부를 구현하여 불일치를 감지할 때마다 이전의 일치 문자열로 돌아가 점프하는 방식으로 시간 복잡도는 최악의 경우 O(N) : 문자열 길이 * 패턴 길이 [ 구성 요소 ] lps[] : 패턴 문자열에서 접두사와 접미사가 일치하는 최대길이 저장 pattern[] : 패턴 문자열 text[] : 주어진 문자열 KMP 알고리즘 함수 구현하기 예시 문자열 ) ABAABAB i 문자열 lps[i] 0 A 0 1 AB 0 2 ABA 1 3 ABAA 1 4 ABAAB 2 5 ABAABA 3 6 ABAABAB 2 => lps에 최대길이인 3이 들어감 lps 구현 코드​ void lps_array(string pattern, int M, int lps[]) { int len = 0; //접두..