HyeLog

void insert(int data) { NodePointer i, element; i = head->next; while(i->data next; element = (NodePointer) malloc (sizeof(Node)); element->data = data; i->prev->next = element; element->prev = i->prev; i->prev = element; element->next = i; } https://opentutorials.org/module/1335/8940 Doubly linked list (이중 연결 리스트) - Data Structure (자료구조) 소개 doubly linked list의 핵심은 노드와 노드가 서로 연결되어 있다는 점입니다. 아래 그..

덱(Deque): 데이터의 삽입과 삭제가 front 와 back에서 이루어 질 수 있음. deque의 선언은 deque [변수이름] -> Ex) deque dq; 원소 접근은 dq[idx] dq.front() dq.back() dq.begin() (iterator와 사용) dq.end() - 마지막의 "다음"을 가리킴. (iterator와 사용) dq.push_front(3) dq.pop_front() dq.push_back(3) dq.pop_back() dq.size() dq.empty() 출처: https://blockdmask.tistory.com/73

그리디(Greedy) 알고리즘(=탐욕 알고리즘)은 미리 정한 기준에 따라서 매번 '가장 좋아 보이는' 답을 선택하는 방법이다. 매우 효율적이고 간단하지만, 항상 최적인 해를 얻는다는 보장은 없다. 그리디 알고리즘의 대표적인 예제는 '거스름돈 문제'이다. 거스름돈이 670원인 경우, 10원짜리 67개를 주면 손님은 매우 불쾌해 할 것이다. 500원짜리 1개, 100원짜리 1개, 50원짜리 1개, 10원짜리 2개를 주는 방법 즉, 동전의 개수가 최소가 되도록 거슬러 주는 것이 최적인 방법이다. 이를 알고리즘으로 간단히 정리하면, ① 가장 좋아보이는 동전 고르기(가장 금액이 큰 동전) - Selection ② 고른 동전들의 총액이 거스름돈을 초과하는지 검사 - Feasibility Check ③ 최종적인 총액..

큐에 대한 기본 이해 큐(Queue)는 FIFO(First In First Out = 선입선출) 구조를 가진다. 큐의 사이즈가 N이고, 위와 같은 초기 상태를 가질 때 - 큐가 꽉 찬 상태: rear==N-1 - 큐가 비어 있는 상태: front==rear (원소의 개수 = rear - front 가 0) - 삽입: rear+1 을 한 뒤에 그 자리에 원소를 삽입 - 삭제: front+1 을 한 뒤에 그 자리의 원소를 삭제 큐의 문제점 앞이 비어있음에도 불구하고, rear==N-1이 되어 큐가 꽉 찬 상태로 인식된다. (더 이상 삽입이 불가능하다.) 원형 큐에 대한 기본 이해 원형 큐는 앞서 말한 큐의 단점을 보완한 구조이다. - 큐가 꽉 찬 상태: (rear+1)%N==front (비어 있는 상태와 구..

다이나믹 프로그래밍이란? ▷다이나믹 프로그래밍은 주어진 문제를 더 작은 문제로 분할해서 가장 작은 문제의 답부터 구한 후 저장해놓고, 필요하면 꺼내쓰는 알고리즘이다. 따라서 답을 저장하기 위한 배열을 구축해야한다. 다이나믹 프로그래밍의 유형 2가지 ① Top-down 방식 재귀함수를 활용하여 큰 문제를 해결하기 위해 작은문제를 호출한다. 다만, "메모이제이션" 기법을 활용하여 중복연산은 하지 않는다. 여기서 "메모이제이션"은 계산한 값을 리스트에 메모함으로서 중복된 연산을 하지 않고 바로 값에 접근하는 방식이다. ② Bottom-up 방식 반복문을 활용하여 점화식을 통해 작은문제부터 해결하여 큰문제를 해결한다. 다이나믹 프로그래밍에 주로 사용되는 방식이다. 왜냐하면 점화식이 곧 반복문의 식이 되기 때문이..

▶최대공약수 -유클리드 호제법(유클리드 알고리즘): 2개의 자연수의 최대공약수를 구하는 알고리즘. -유클리드 알고리즘 내용: 2개의 자연수 a, b (단, a>b)에 대해서 a와 b의 최대공약수는 b와 a%b의 최대공약수와 같음을 이용한다. a%b를 r이라 할 때, b와 r의 최대공약수는 또다시 r과 b%r의 최대공약수이다. 이렇게 계속 나머지를 구하는 과정을 반복하면, 나머지가 0인 순간이 오는데, 그때 나누는 수가 a와 b의 최대공약수다. ▶최소공배수 2개의 자연수 A, B가 있을 때, A=a*G, B=b*G (단, a와 b는 서로소, G는 A와 B의 최대공약수)이면, A*B=a*b*G*G, a*b*G=L (L은 A와 B의 최소공배수)이므로 L=A*B/G 즉, A와 B의 최소공배수는 두 수의 곱을 두..

백트래킹(Backtracking)은 DFS 기반의 알고리즘으로, 노드들을 탐색하다가 해답이 될 가능성이 없는 노드(nonpromising)를 만나면 그 노드를 탐색의 대상에서 제외시키고(pruning; 가지 치기) 부모 노드로 되돌아가서 다른 경로에 대한 탐색을 계속하는 알고리즘이다. 백트래킹의 장단점은 다음과 같다. ◎ 장점 - 현 경로상의 노드들만 기억하면 되므로 BFS에 비해 저장공간의 수요가 적다. - 목표노드가 깊은 단계에 있을 때 BFS보다 해를 구하기에 유리하다. ◎ 단점 - 해가 없는 경로에 깊이 빠질 가능성이 있다. - 얻어진 해가 최단 경로라는 보장이 없다. 가장 대표적인 문제로는 N-Queen 문제가 있다. (백준 해당 문제 링크: https://www.acmicpc.net/probl..

C++는 표준 템플릿 라이브러리(STL)를 제공한다. STL에 구현된 제네릭 클래스나 함수를 잘 활용하면, 더 쉽게 C++ 프로그램을 작성할 수 있다. 그 중 벡터(vector)는 스스로 크기를 조절하는 배열을 구현한 제네릭 컨테이너(container) 클래스이다. 우리는 멤버함수를 통해서 배열에 원소를 저장, 삭제, 검색할 수 있다. vector를 사용하려면 우선 헤더파일을 include 해야 한다. #include 그리고 vector 객체를 생성해야한다. 안에 타입을 지정한다. vector my_vector; vector name; // 헤더 파일 include vector는 배열과 마찬가지로 [ ]로 원소에 접근할 수 있다. my_vector[3] = 7; vector에 원소를 삽입하려면 push_..