Computer Science
-
[CS] 정규 표현식 Regular Expression, RegexComputer Science/CS 2023. 1. 19. 23:13
Regular Expression 정규식은 특정한 규칙을 가진 문자열의 집합을 표현하는 데 사용하는 형식 언어입니다. 정규 표현식은 많은 텍스트 편집기와 프로그래밍 언어에서 문자열의 검색과 치환을 위해 지원하고 있습니다. 기본 개념 패턴(pattern)으로 부르는 정규 표현식은 특정 목적을 위해 필요한 문자열 집합을 지정하기 위해 쓰이는 식입니다. | 여러 항목 중 선택, A | B 는 "A" or "B" 와 일치한다는 의미. () 괄호를 사용하여 연산자의 범위와 우선권 정의. gr(a|e)y 는 "gray" or "grey" 집합을 둘 다 기술하는 동일 패턴 ? 0번 or 1차례까지의 발생을 의미. colou?r 는 "color"와 "colour"를 둘 다 일치 시킴 * 별표는 0번 이상의 발생을 의미..
-
[Algorithm] DFS( Depth-First Search), BFS(Breadth-First Search)Computer Science/Algorithm 2022. 11. 28. 19:18
1. DFS 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동 로투 노드(혹은 임의의 다른 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식 ▶모든 노드를 방문하고자 하는 경우에 이 방법을 선택 ▶깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함 ▶검색 속도 자체는 BFS에 비해서 느림 ▶ 스택, 재귀함수로 구현 ① 탐색 시작 노드를 스택에 삽입하고 방문처리 ② 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리 ③ 위 과정을 수행할 수 없을때까지 반복 - 노드 방문 시 방문(Visited)여부를 반드시 검사해야 한다. 아니면 무한 루프에 빠질 수 있음. - 탐색 과정이 ..
-
[CS] Graph, TreeComputer Science/CS 2022. 11. 28. 18:44
트리 ⊂ 그래프 그래프 노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료 구조이다. 순환 혹은 비순환 구조를 이룬다. 그래프의 구현 방법은 2가지 방식이 있습니다. - 인접 행렬(adjacency matrix) : 2차원 배열을 사용하는 방식 - 인접 리스트(adjacency list) : 리스트를 사용하는 방식 두 방식의 메모리와 속도 차이는 다음과 같습니다. V : 노드의 개수, E : 간선의 개수 일 때, 인접 행렬은 O(v^2), 인접 리스트는 O(E) 만큼의 메모리 공간이 요구됩니다. 인접 행렬은 O(1), 인접 리스트는 O(V)만큼의 시간이 소요됩니다. 트리 그래프와 같이 노드와 노드 간을 연결하는 간선으로 구성된 자료 구조이다. 트리는 두 개의 노드 사이에 반드시 1개의 경로만을 ..
-
[Algorithm] Union-Find algorithmComputer Science/Algorithm 2022. 11. 7. 17:19
Disjoint Set - 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 즉, 공통 원소가 없는 "상호 배타적"인 부분 집합들로 나눠진 원소들에 대한 자료구조 Union-Find algorithm - 서로소 집합(Disjoint Set)을 표현할 때 사용하는 알고리즘 - 그래프 알고리즘으로 Union(합집합) + Find(찾기) 로 '합집합 찾기'라는 의미를 가지고 있다. - 여러 노드 중 2개의 노드를 선택하여 같은 그래프에 속해 있는 지 확인하는 알고리즘이다. 연산 - Make-set(x) // 초기화 : x를 유일한 원소로 하는 새로운 집합 생성 - Union(x, y) // 합하기 :원소 x가 속한 부분집합과 원소 y가 속한 부분집합의 합집합을 구한다. ..
-
[자료구조] Linked list (연결리스트)Computer Science/Data Structure 2022. 9. 23. 21:11
Linked List 란? node라는 객체로 이루어져 있다. 여러개의 node를 연결함으로써 데이터 표현 가능 시작(주소) - 연결(link) - 끝(null pointer or circular) 코드로 아래와 같이 구현할 수 있다. typedef struct Node{ int data; Node *next; }Node; Linked list 장점 동적으로 메모리 사용가능 메모리 효율적 사용 데이터 재구성 용이 대용량 데이터 처리 적합 Linked list 단점 특정 위치 데이터 검색 느림 메모리를 추가적으로 사용해야 함 Singly Linked list Circularly Linked list : 마지막 노드가 다시 처음 노드를 가리킴.
-
[CS] 동기 비동기 프로그래밍Computer Science/CS 2022. 9. 7. 23:47
동기(Synchronous) 현재 작업의 응답이 끝남과 동시에 다음 작업이 요청된다. 함수를 호출하는 곳에서 호출되는 함수가 결과를 반환할 때까지 기다린다. 작업 완료 여부를 계속해서 확인한다. 비동기(ASynchronous) 현재 작업의 응답이 끝나지 않은 상태에서 다음 작업이 요청된다. 함수를 호출하는 곳에서 결과를 기다리지 않고, 다른 함수(callback)에서 결과를 기다린다. 작업 완료 여부를 확인하지 않는다. (싱글쓰레드에서 비동기적인 프로그래밍을 한다고 해서 멀티쓰레드처럼 동시 다발적인 실행이 가능해지는 것은 아니다.) 블록킹(Blocking) 블록킹 (Blocking) : 자신의 수행결과가 끝날 때까지 제어권을 갖고 있는 것 논블록킹(non-blocking) 논블록킹 (non-blockin..