티스토리

Ressi 🌱

검색하기

블로그 홈

Ressi 🌱

hini7.tistory.com/m

Ressi의 성장기 🌱

구독자: 22

방명록 방문하기

주요 글 목록

[후위표기법] 후위표기식으로 계산기 만들기 (html, js 이용) :: 개념에서 구현까지 후위표기법으로 계산기 만들기 계산기 관련 외주가 들어와서 해보던 중, 예전에 배웠던 후위표기법을 사용해야했다. 그런데 기억이 안나서 검색 없이 혼자 구현하려다 보니 너무 어려웠다... 검색해보니까 stack을 이용해서 후위표기법을 만드는 간단한 방법이 나와있어서 까먹지 않기 위해 기록한다. 후위 표기법 수식 트리 후위 표기법이란 계산식에서 계산을 위해 사용하는 표기법이다. 예제와 함께 살펴보자. 수식 : 9x3+1-3%3 수식이 주어졌을 때 비연산자와 연산자로 나눈 후, 각 항목을 하나의 노드라고 생각하면 트리 형태로 만들 수 있다. 이러한 트리는 수식을 트리라는 자료구조로 만든 것이니 수식트리, 즉 Expression Tree라고 불린다. 트리 순회와 표기법 트리를 순회하는 방식에는 prefix(전위).. 공감수 1 댓글수 0 2020. 12. 21.
[c++] 알고리즘 개념공부 :: 최단경로 찾기 (Dijkstra 알고리즘) 최단 경로 그래프에서 유도되는 문제들 중 최단 경로 문제가 있다. 주어진 그래프에서 특정 정점에서 다른 정점까지의 최단 경로(가중치 합이 최소인 경로)가 무엇인지를 알아내는 문제이다. 이는 이전의 MST 문제와 다르다. 모든 정점을 포함할 필요가 없기 때문이다. 하지만 MST에서 사용했던 Prim(Dijkstra) 알고리즘을 응용해서 구현할 수 있다. [MST] Dijkstra 알고리즘 구현 vertice(정점)는 3가지 분류로 나뉜다. tree vertice(T) : tree에 속해 있는 정점 fringe vertice (F) : tree에 포함되지 않으면서 연결되어있는 정점 unseen vertice (U) : 나머지 MST에서 T와 F의 정점 사이의 최소 가중치를 계속 갱신해주었던 것 대신에, 최단.. 공감수 0 댓글수 0 2020. 9. 20.
[c++] 알고리즘 개념공부 :: MST (Prim/Dijkstra, Kruskal, 시간복잡도) MST Spanning Tree : 그래프 내의 모든 정점을 포함하는 트리 우선 트리의 정의는 connected undirected acyclic graph (연결 비방향 비순환 그래프)이다. 모든 노드는 연결되어있으며, 방향성은 없고 순환이 존재하지 않는 그래프이다. 하나의 그래프가 주어졌을 때, 그래프 내에서 여러 트리를 찾을 수 있다. 그 중 특별하게 모든 정점을 포함하는 트리를 Spanning Tree라고 한다. 다르게 말하면 Spanning tree(신장 트리)는 그래프의 부분 그래프면서 간선의 수가 가장 적은(최소 연결) 그래프이다. 감이 안온다면 그림으로 살펴보자. 위의 그림과 같이 그래프가 주어졌을 때, 최소한의 간선을 사용하여 모든 정점을 포함하는 부분 그래프가 여러 개 존재한다. 이 부.. 공감수 0 댓글수 0 2020. 9. 20.
[c++] 알고리즘 개념공부 :: 그래프 탐색 (BFS, DFS) 그래프 탐색 그래프를 탐색하는 기법에는 대표적으로 2가지가 있다. 너비 우선 탐색인 BFS(Breadth-First Search)와 깊이 우선 탐색인 DFS(Depth-First Search)이다. BFS BFS는 큐를 이용하여 구현한다. 설명 트리로 예를 들었지만, 모든 그래프에서 마찬가지로 동작한다. 루트 노드를 queue에 넣는다. queue의 노드를 하나 꺼낸 후, 해당 노드와의 인접 노드를 모두 queue에 넣는다. 위의 방식을 모든 노드가 완료될 때까지 반복한다. stack에 들어간 순서를 보면 다음과 같다. 1=>2=>3=>4=>5=>6=>7=>8 따라서 트리에서 BFS를 실행하여 탐색을 하는 것은 레벨 순회를 하는 것과 같다. DFS DFS는 스택을 이용하여 구현한다. 설명 트리로 예를 들.. 공감수 0 댓글수 0 2020. 9. 13.
[c++] 알고리즘 개념공부 :: 순열과 조합 (코드, next_permutation 이용, 직접 구현) 순열과 조합 순열 정의 순열은 중복없이 n개 중 r개를 뽑아 순서를 정해 나열하는 경우이다. 위의 그림처럼 A, B, C 세가지 원소가 있을 때, 2개를 뽑아 순서를 정하는 것을 3P2라고 한다. 아래와 같은 경우의 수가 나오므로 총 6가지 이다. 순열은 P(Permutation)로 표현하며 식은 다음과 같다. $$ {}n\mathrm{P}{r} = \frac{n!}{(n-r)!} $$ 중복 순열이라는 특별한 경우는 순열 중 같은 종류의 것을 다시 뽑을 수 있는 경우를 말한다. 중복 순열은 Π로 표현하며 식은 다음과 같다. $$ {n}\mathrm{\pi}{r} = n^r $$ 구현 순열 // 직접 구현 void swap(vector& set, int a, int b){ int tmp = set[a]; .. 공감수 0 댓글수 0 2020. 9. 7.
[c++] 알고리즘 개념공부 :: 최대 최소 찾기 (토너먼트 트리, selection 알고리즘) 최대 최소 찾기 선택 문제 주어진 리스트의 최대, 최소 값을 찾거나 n번째 큰 값, n번째 작은 값을 찾는 과정도 프로그램에서 많이 등장한다. 이렇게 n개의 숫자들 중 k번째로 작은(또는 큰) 값을 찾는 문제를 'Selection problem' 즉, 선택 문제 라고 한다. 최대 최소 찾기 선택 문제에서 가장 쉬운 문제가 최대 / 최소를 찾는 문제이다. 주어진 리스트의 최대값을 찾기 위해서는 어떤 방법을 사용하면 될까? 정렬 먼저, 이전에 배웠던 정렬을 이용할 수 있다. 정렬 후 리스트의 마지막 요소를 가져오면 최대값을 알 수 있기 때문이다. 하지만 중간 요소들의 정렬은 최대값을 찾는데에 불필요한 과정이다. 따라서 정렬을 이용하면 정렬의 최소 시간복잡도인 O(nlgn)로 문제를 해결할 수 있다. min/.. 공감수 0 댓글수 0 2020. 9. 7.
[c++] 알고리즘 개념공부 :: 탐색 (선형 탐색, 이진 탐색, 해시 탐색) 탐색 탐색은 주어진 자료들 중 원하는 조건에 해당하는 자료를 찾는 과정이다. 컴퓨터에서 탐색은 자주 이루어지므로 효율적인 방식으로 수행하는 것이 중요하다. 이전에 배웠던 '정렬'은 탐색을 수행할 수 있는 방법 중 하나이다. 정렬은 리스트를 하나의 기준으로 나타내기 위해서도 쓰이지만 원하는 자료를 빠르게 탐색하기 위해 쓰이기도 한다. 물론 굳이 정렬이 아니더라도 탐색을 수행할 수 있는 방법은 있다. 정렬 보기 앞으로 소개할 탐색은 다음의 4가지 종류이다. 선형탐색 이진탐색 해시탐색 BST 탐색을 위해서는 배열, 연결 리스트, 트리, 그래프 등 다양한 자료구조가 사용되며, 상황에 따라 맞춰서 사용하면 된다. 자료구조 보기 선형 탐색 순차 탐색이라고도 불리는 선형 탐색은 가장 간단한 탐색 방법이다. 선형 탐색.. 공감수 0 댓글수 0 2020. 8. 30.
[c++] 알고리즘 개념공부 :: 탐색 - BST BST BST(Binary Search Tree)는 트리의 한 종류이자 이진탐색을 위한 방법 중 하나이다. 과정 BST를 이용한 탐색에서는 다음과 같은 과정을 거친다. 이진 탐색 트리 만들기 (생성) 루트 노드에서 내려가면서 원하는 요소 찾기 (탐색) 삭제 및 삽입 하기 (삭제 / 삽입) 예시 먼저 이진 탐색 트리를 만들어보자. 이진 탐색 트리는 부모 노드를 기준으로 왼쪽 서브트리에는 더 작은 값의 노드가 오른쪽 서브트리에는 더 큰 값의 노드가 있어야한다. 따라서 요소를 하나씩 삽입하면서 알맞은 위치를 찾아주면 된다. 결과적으로 나온 이진 탐색 트리를 중위 순회하면 정렬된 리스트가 된다. 그 다음에는 루트 노드에서 내려가면서 원하는 요소를 찾고 삭제해보자. 원하는 요소는 6이다. 왼쪽 그림에서 오른쪽 그.. 공감수 0 댓글수 0 2020. 8. 30.
[c++] 알고리즘 개념공부 :: 정렬 (퀵 정렬, 합병 정렬) 퀵 정렬 개념 퀵 정렬의 세부과정은 다음과 같다. pivot이라는 요소를 선택한 후, pivot을 기준으로 왼쪽에는 pivot보다 작은 요소들을 놓고 오른쪽에는 pivot보다 큰 요소들을 놓는다. 이후 순환호출을 이용하여 재귀적으로 왼쪽, 오른쪽으로 분류해둔 요소들에 대해 전과 같은 과정을 반복한다. 위의 그림은 오른쪽 요소들에 대해 순환호출한 모습이다. 분할이 불가능할 때까지 반복하다보면 최소한의 요소로 나누어지고 이후 순서대로 결합을 진행한다. 위의 그림에서 색이 칠해져있는 요소들을 순서대로 합치면 된다. 퀵 정렬은 분할 정복 알고리즘 중 하나이다. pivot으로 2개의 부분 배열을 생성하는 분할(Divide) 과정과 부분 배열을 재귀적으로 호출하는 정복(Conquer) 과정과 정렬된 부분 배열을 합.. 공감수 0 댓글수 0 2020. 8. 25.
[c++] 알고리즘 개념공부 :: 정렬 (선택 정렬, 버블 정렬, 삽입 정렬) 선택 정렬 개념 max, min 정렬이라고도 불린다. 처음부터 끝 원소까지 훑으면서 최소나 최대를 찾아서 리스트의 처음이나 끝에 넣고 해당 원소를 제외한 다른 원소에 대해 다시 정렬을 시행하는 방법이다. 무작위로 정렬된 데이터의 처음부터 끝까지 탐색한 후, 가장 큰 수를 리스트의 마지막 요소와 교환한다. 그 후 마지막 원소를 제외한 채로 처음부터 끝까지 데이터를 탐색한 후, 가장 큰 수를 리스트의 마지막 요소와 교환한다. 구현 의사 코드는 다음과 같다. (min 정렬) for i=0 to n: a[i]부터 a[n-1]까지 차례로 비교하여 최소값이 있는 a[j]를 찾는다. a[i]와 a[j]를 바꾼다. (max 정렬) for i=0 to n: a[0]부터 a[n-i-1]까지 차례로 비교하여 최대값이 있는 .. 공감수 1 댓글수 0 2020. 8. 16.
[c++] 알고리즘 개념공부 :: 정렬 (개요) 정렬 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 문제가 '정렬'이다. 보통 컴퓨터에서는 탐색을 위해서 정렬을 수행한다. 탐색은 정렬을 통해 하는 것보다 더 강력한 알고리즘이 있지만, 한 번 데이터를 정렬해두면 다음부터는 이진 탐색이라는 빠른 알고리즘을 몇 번이고 사용할 수 있기 때문에 유용하다. 그래서 주어진 무작위의 데이터를 정렬하는 것에 많은 연구자들이 방법을 내놓았는데, 앞으로 설명할 6개의 정렬 알고리즘이다. 그 외에도 많은 정렬 알고리즘이 존재한다. 모든 정렬의 설명에 앞서서 예제로 설명할 데이터는 다음 그림과 같이 무작위로 배치되어있는 1~7의 데이터이다. 정렬 알고리즘의 시간 복잡도는 비교 + 이동으로 측정한다. 특성 정렬 알고리즘은 여러 기준에 따라 나뉠 수 있다. 시간 복.. 공감수 0 댓글수 0 2020. 8. 16.
[c++] 알고리즘 개념공부 :: 재귀호출 (동적 계획법) 🍑동적 프로그래밍 동적 프로그래밍은 Dynamic Programming 즉, DP라고 불리는 알고리즘 기법이다. 복잡한 문제를 점화식으로 만들어 분할 정복할 때, 반복문 또는 재귀를 사용할 수 있는데 이 과정에서 계산의 결과 값을 저장해두어 중복되는 계산을 하지 않도록 만들어준다. 이는 점화식 이렇게 결과 값을 저장해두는 것을 메모이제이션이라고 하는데, 보통 배열의 형태로 수행된다. DP 과정 전체 문제를 부분 문제로 단순화한다. 1번의 과정에서 점화식을 도출한다. 점화식을 이용하여 배열로 간단히 해결할 수 있는지 생각한다. bottom-up top-down 없다면 재귀함수를 만들고 메모이제이션한다. 메모이제이션 방식은 보통 배열이다. 전체 문제를 해결한다. 대표 문제 피보나치 수열 구하기 피보나치 수열.. 공감수 0 댓글수 1 2020. 8. 9.
[c++] 알고리즘 개념공부 :: 재귀호출 (완전탐색) 재귀호출 재귀함수란 함수 내에서 자기 자신을 다시 호출하는 함수이다. 프로그래밍할 때 반복되는 작업들이 대해서는 반복문을 사용하거나 재귀함수를 이용해서 표현한다. 기저 사례란 더 이상 쪼개지지 않는 가장 작은 작업으로, 이에 도달했을 때는 재귀호출을 멈추고 답을 곧장 반환해야한다. 기저 사례를 정할 때는 모든 사례의 답이 기저 사례를 이용하여 계산될 수 있도록 해야한다. 완전 탐색 (== Brute Force, Exhaustive search) 완전탐색은 컴퓨터의 연산능력을 이용하여 가능한 경우의 수를 모두 나열하면서 답을 찾는 알고리즘이다. 입력의 크기가 작을 때 적절한 알고리즘이며 더 빠른 알고리즘의 기반이 된다. 답을 무조건 찾을 수 있다는 장점이 있지만, 찾는데에 오랜 시간이 걸린다는 단점이 있다.. 공감수 0 댓글수 0 2020. 7. 31.
[c++] 알고리즘 개념공부 :: 비트조작 (비트마스크, 연산, 코드 구현) 비트 조작 개념 비트(bit)란 0과 1의 값을 가질 수 있는 데이터의 단위이다. 4bit를 모은 단위를 니블(nibble)이라 부르고, 8bit를 모은 단위를 바이트(byte)라고 부른다. 2byte를 모은 단위는 일부 전자통신기기에서 워드(word)라고 한다. 구현 C++에서는 비트를 다루기 위해서 이라는 헤더를 포함해서 사용한다. 연산 C++에서 비트연산들은 위에서 언급한 라이브러리로 쉽게 가져다 쓸 수 있지만, 개념 공부 측면에서 그냥 구현도 하고 라이브러리 사용법도 익혀두려한다. 메모리 상에 변수를 저장하는 것이 1byte 단위로 가능하기 때문에, bit 단위의 자료형은 없다. 다만 bool 형은 메모리 상에서 1byte를 차지하지만 가능한 값이 true 혹은 false 밖에 없으므로 이를 이용.. 공감수 0 댓글수 0 2020. 7. 31.
[c++] 알고리즘 개념공부 :: 자료구조 - 구조체 구조체 구조체는 배열과는 다르게 다른 자료형의 변수들을 모아서 하나의 단위로 표현하는 자료형이다. 용도 연결리스트나 그래프에서 노드를 나타낼 때, 데이터와 포인터 부분이 존재한다. 구조체를 사용하면 데이터와 포인터 부분을 각각 구성하여 하나의 자료형으로 만들어줄 수 있다. 이 때, 포인터는 해당 구조체의 포인터형이므로 이 구조체는 자체 참조 구조체가 된다. C++ struct Node { int value; Node* pointer; // 자체 참조 구조체 }; int main() { Node A; // 구조체 선언 A.value = 4; Node* Ap = A.pointer; // . 연산자로 접근 int Avalue = A.value; Ap = A; Avalue = Ap->value; // 포인터로 .. 공감수 0 댓글수 0 2020. 7. 28.
[c++] 알고리즘 개념공부 :: 자료구조 - 힙 힙 용도 구현 종류 연산 정렬 힙 힙은 추상적 자료형인 우선순위 큐를 구현하기 위해서 만들어진 자료구조이다. partial-ordering (부분 정렬)을 만족하는 left-complete binary tree (좌측 완전 이진 트리) 이다. 부분 정렬을 만족한다는 말은 '부모 노드와 자식노드' 간에는 특정 대소관계 성립하지만, '형제노드'간에는 해당 대소관계가 성립하지 않는다는 뜻이다. 이진 탐색 트리에서는 중복된 값을 허용하지 않지만 힙 트리에서는 허용한다. 용도 힙은 추상적 자료형인 우선순위 큐를 구현하기 위해서 만들어진 자료구조이다. 배열과 연결리스트를 이용하면 삽입과 삭제 연산 중 하나가 O(n)일 수 밖에 없다. 하지만 힙을 이용하면 가장 큰 값이나 가장 작은 값을 둘 다 O(logn)만에 빠.. 공감수 0 댓글수 0 2020. 7. 28.
[c++] 알고리즘 개념공부 :: 자료구조 - 트리 트리 용도 용어 정리 종류 이진 트리 일반 트리 스레드 이진 트리 구현 배열 표현법 연결리스트 표현법 트리 활용 탐색 집합 표현 허프만 코드 트리 트리란 그래프의 한 종류로 무방향 연결 비순환 그래프(Connected Undirected Acyclic Graph)이다. 루트 노드가 존재하고, 루트 노드를 제외한 모든 노드의 in-degree가 1인 방향그래프라고 말할 수도 있다. 계층적인 구조를 가지며 그래프의 한 종류이므로 비선형 자료구조에 속한다. 용도 계층적인 조직을 표현하기 위해 사용되거나, 컴퓨터의 디렉토리 구조 / 인공지능의 decision tree 등에 이용된다. 또한 자료의 탐색 / 정렬 / DB 구성이나 분자구조식 설계 등에서도 다양하게 이용된다. (결정트리)(이진탐색) 용어 정리 노드 .. 공감수 0 댓글수 0 2020. 7. 28.
[c++] 알고리즘 개념공부 :: 자료구조 - 그래프 그래프 용도 용어 정리 기본 심화 구현 인접 행렬 인접 리스트 비교 연산 분류 방향성에 따른 분류 연결에 따른 분류 사이클에 따른 분류 특수한 그래프 탐색 도출된 문제들 관련 알고리즘 참고 그래프 그래프란 '노드'와 노드를 연결하는 '간선'으로 이루어진 자료구조이다. 지금까지의 살펴본 자료구조들(리스트, 스택, 큐 등)과는 달리 그래프는 비선형 자료구조 이다. 용도 그래프는 일상생활에서 연결되어있는 객체 간의 관계를 표현할 때 사용된다. 예로 지도나 지하철 노선도, 전기회로, 도로 등을 들 수 있다. 또한 컴퓨터 세부전공에서는 통신 네트워크 분야에서도 쓰이며, 논리회로를 설계하고 분석하는 데에도 사용된다. 최근에는 웹사이트의 링크 연결(Page Rank)이나 SNS 상의 친구관계를 표현하는 데에도 사용되.. 공감수 0 댓글수 0 2020. 7. 28.
[c++] 알고리즘 개념공부 :: 자료구조 - 서론 서론 자료구조 자료구조는 컴퓨터에서 자료를 정리하고 조직화하는 다양한 구조를 말한다. 프로그램은 자료구조와 알고리즘으로 이루어져있기 때문에, 자료구조는 반드시 공부해야하는 분야이다. 자료구조는 먼저 단순 자료구조와 복합 자료구조로 구분되고, 복합 자료구조에는 선형 구조와 비선형 구조가 있다. 순차적으로 살펴보자. 배열, 문자열 연결 리스트 스택, 큐, 덱 그래프 트리 힙 구조체 공감수 1 댓글수 0 2020. 7. 28.
[c++] 알고리즘 개념공부 :: 자료구조 - 스택, 큐, 덱 스택 특징 용도 연산 삽입 삭제 접근 구현 큐 용도 종류 연산 삽입 삭제 접근 구현 우선순위 큐 덱 용도 구현 스택 스택은 LIFO(Last-In First-Out), 즉 후입선출의 자료구조이다. 구조는 다음과 같은 형태이며, 접시처럼 쌓여서 이후에 삽입된 데이터가 먼저 빠져나가도록 되어있다. top 변수는 가장 최근에 들어온 요소를 가리키며 스택이 비어있으면 -1이다. 특징 LIFO 내부 요소를 확인할 방법이 pop 말고는 없다. 용도 입력의 역순이 필요할 때 스택을 주로 사용하며, 함수의 호출에서 복귀 주소를 기억하기 위해서 시스템 스택이 사용되기도 한다. 또한 괄호 검사, 계산기, 미로 탐색 등의 경우에 스택이 유용하게 사용된다. 계산기에서 중위 표기식(infix)을 후위 표기식(postfix)으로.. 공감수 1 댓글수 0 2020. 7. 19.
[c++] 알고리즘 개념공부 :: 자료구조 - 연결 리스트 연결 리스트 리스트란? 정의 배열과의 비교 연산 삽입 삭제 접근 종류 / 구현 리스트란? 리스트는 순서를 가진 항목들의 모임이다. 이를 나타내는 대표적인 방법은 2가지가 있는데, 하나는 배열을 이용하는 방법이고 나머지 하나는 연결리스트를 이용하는 방법이다. 배열을 이용한 리스트를 선형리스트라고 하는데 구현 자체는 간단하고 임의접근이 가능하지만, 삽입 / 삭제 연산 시 다른 요소들의 이동이 불가피하므로 오버헤드가 크다. 연결리스트는 구현이 복잡하고 순차접근이 필요하지만 삽입, 삭제가 효율적이다. 정의 연결리스트란 아래의 그림과 같이 데이터와 링크로 이루어진 노드로 구성되어있다. 링크는 다음 요소를 가리키는 포인터이다. 연결리스트의 처음에는 헤드 포인터가 헤드 노드를 가리키고 있으며, 마지막 노드의 링크는 .. 공감수 0 댓글수 0 2020. 7. 19.
[c++] 알고리즘 개념공부 :: 자료구조 - 배열, 문자열 목차 배열 선언 초기화 접근 다차원 배열 희소 행렬 표현 주소와 포인터 포인터 특징 제약 동적 메모리 할당 동적 배열(vector) 문자열 선언 초기화 함수 배열 / 문자열 배열 배열이란 단일 식별자로 _같은 자료형_의 여러 변수를 접근할 수 있게 해주는 자료구조이다. 선언 c++에서는 int arr[3];와 같이 자료형 배열이름[배열 길이];로 변수를 선언한다. 이 때, 대괄호 내의 요소의 갯수는 '컴파일 타임 상수'여야한다. 소스코드를 컴파일할 때, 고정 배열의 길이를 알아야하기 때문이다. 따라서 매크로 기호 상수 (ex_ #define ARRAY_LEN 5)나 열거자(ex_enum A{ARRAY_LEN = 5})는 배열의 길이로 사용할 수 있다. const 또한 컴파일 시 고정되는 상수이므로 사용가.. 공감수 0 댓글수 0 2020. 7. 19.
[컴퓨터 보안] 타원곡선 DSA 디지털 서명 설명 및 구현코드 타원곡선 DSA 디지털 서명 자료조사 DSA란? 디지털 서명 알고리즘(Digital Signature Algorithm, DSA)은 디지털 서명을 위한 표준이다. NIST가 1991년 8월 DSS라는 미국 전자서명 표준에서 이용하기 위해 정부용 전자서명 알고리즘으로 발표했으며, 현재는 DSA와 함께 ECDSA, RSA를 사용하고 있다. 디지털 서명 인증 방식 전자서명(디지털 서명)은 무결성, 인증, 부인방지를 만족해야한다. 전자서명에는 공개키 암호화 알고리즘이 쓰이며 크게 3가지 종류의 알고리즘이 있다. 합성수의 소인수분해문제가 어렵다는 데에 기초한 RSA형 알고리즘 유한체의 이산대수 문제가 어렵다는 데에 기초한 ElGamal형 알고리즘 타원곡선을 이용한 EC-DSA, EC-KCDSA DSA는 이 중 E.. 공감수 3 댓글수 0 2020. 7. 4.
[운영체제 정리] 파일 & 파일시스템 파일 시스템 정리 개요 오랜 기간 동안 저장되어야하는 정보의 저장에는 몇가지 조건이 있다. 프로세스가 종료된 후에도 정보가 유지되는 비휘발성 많은 정보를 저장할 수 있는 큰 용량 다수의 프로세스가 동시에 접근 가능한 접근성 오랜 기간동안 큰 정보를 저장하는 장치 중 하나인 Disk는 고정된 크기의 block들로 구성되어있는데, 다음과 같은 질문들을 불러일으킬 수 있다. Disk에 저장한 정보를 어떻게 찾을 것인가? 정보의 양이 방대해서 정보를 찾기가 쉽지 않다. 빈 공간을 어떻게 관리할 것인가? 새로운 정보를 저장할 때 빈 공간을 찾아서 사용해야한다. 사용자 별 권한을 어떻게 관리할 것인가? 데이터를 보호해야한다. 이 해답은 파일 과 파일시스템 에서 찾을 수 있다. 파일 파일은 저장 장치에 정보를 저장하.. 공감수 1 댓글수 2 2020. 7. 3.
[c++] CAS 구현 및 ABA 문제 해결 :: mutex(spin lock)와의 비교 Mutex와의 비교 코드 #include #include #include #include #include #include using namespace std; class Node { public: int value; Node* next; Node() : value(0) { next = NULL; } Node(int k_value) { next = NULL; value = k_value; } }; int node_n; //random 구현 random_device rd; mt19937 gen(rd()); uniform_int_distribution dis(0, 10); //출력을 위한 mutex mutex mut; class LFStack { private: Node * head; public: void .. 공감수 0 댓글수 1 2020. 7. 2.
[c++] CAS 구현 및 ABA 문제 해결 :: ABA 해결_4. 그 외의 방법들 목차 문제 정의 lock free 구현 ABA 해결 int형 구현(+ Hazard pointer) Counter 그 외의 방법들 mutex lock(spin lock)과의 비교 그 외의 방법들 DCAS _InterlockedCompareExchange128 사용 위의 Counter 기법과 비슷하다. 64bit를 모두 이용하여 주소를 표현하는 CPU에서는 위의 Counter 기법을 사용할 수 없으므로 c++의 _InterlockedCompareExchange128 연산을 이용하여 이를 대신할 수 있다. 이 연산은 64bit 자료형 2개를 묶어서 128bit로 CAS 연산을 시행할 수 있다. 이 때 64bit 씩 분리하여 새로운 값으로 바꾸어줄 수 있다. lock 변수 이용 어셈블리어까지 보면 lock-fr.. 공감수 1 댓글수 0 2020. 7. 2.
[c++] CAS 구현 및 ABA 문제 해결 :: ABA 해결_3. Counter 구현 목차 문제 정의 lock free 구현 ABA 해결 int형 구현(+ Hazard pointer) Counter 그 외의 방법들 mutex lock(spin lock)과의 비교 Counter #include #include #include #include #include #include using namespace std; class Node { public: int value; Node* next; Node() : value(0) { next = NULL; } Node(int k_value) { next = NULL; value = k_value; } }; int node_n; //random 구현 random_device rd; mt19937 gen(rd()); uniform_int_distribut.. 공감수 0 댓글수 0 2020. 7. 2.
[c++] CAS 구현 및 ABA 문제 해결 :: ABA 해결_2. hazard pointer 목차 문제 정의 lock free 구현 ABA 해결 int형 구현(+ Hazard pointer) Counter 그 외의 방법들 mutex lock(spin lock)과의 비교 Hazard Pointer https://m.blog.naver.com/PostView.nhn?blogId=jjoommnn&logNo=130127286459&proxyReferer=https:%2F%2Fwww.google.com%2F 를 참고하여 작성하였다. 문제점 먼저 delete를 이용하여 객체를 삭제하면, 해당 객체를 참조하고 있던 스레드에 문제가 생길 수도 있고 객체가 삭제된 주소에 다시 같은 객체가 할당되어 ABA 문제가 일어날 가능성이 있다. 새로 객체를 할당하는 것은 사용자가 관리하는 list가 아니다. 1번 문제를 .. 공감수 0 댓글수 2 2020. 7. 2.
[c++] CAS 구현 및 ABA 문제 해결 :: ABA 해결_1. int형 구현 목차 문제 정의 lock free 구현 ABA 해결 int형 구현(+ Hazard pointer) Counter 그 외의 방법들 mutex lock(spin lock)과의 비교 ABA 해결 int형 구현 ABA 문제는 매개변수를 int형으로 구현하면 쉽게 해결할 수 있다. 하지만 문제점은 존재한다(뒷부분에 언급). 코드 #define _CRT_SECURE_NO_WARNINGS #define NULL_INT -1 // NULL 값 #include #include #include #include #include // #include #include using namespace std; struct Node { int data; Node* next_node; }; int node_n; atomic free_l.. 공감수 0 댓글수 1 2020. 7. 2.
[c++] CAS 구현 및 ABA 문제 해결 :: 문제 정의, 기본 CAS 구현 목차 문제 정의 lock free 구현 ABA 해결 int형 구현(+ Hazard pointer) Counter 그 외의 방법들 mutex lock(spin lock)과의 비교 문제 정의 문제 Linked List 자료구조에서 push()와 pop() 연산을 구현한다. Linked List는 FreeList와 HeadList 두가지가 있으며 여러 스레드가 두 개의 List를 번갈아가며 push, pop 연산을 수행한다. 스레드들이 각각 연산을 수행하기 위해서는 List들에 대한 상호배제가 필요하다. 해석 상호 배제에는 여러가지 방법이 있지만, 크게 두가지로 나눌 수 있다. lock 변수의 조건을 체크하며 반복문을 돌고 있는 spin lock과, lock 변수 없이 계속 시도하면서 적절한 때에 동작을 수행.. 공감수 1 댓글수 0 2020. 7. 2.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.