스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조 (LIFO - Last In First Out) 으로 되어 있다.
자료를 넣는 것을 ‘밀어넣는다’ 하여 푸쉬(push) 라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop) 이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다.
1 min read
스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조 (LIFO - Last In First Out) 으로 되어 있다.
자료를 넣는 것을 ‘밀어넣는다’ 하여 푸쉬(push) 라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop) 이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다.
...돌아와 아직 안 가본 갈래로 다시 내려가는 탐색 방식이다. “깊이 우선” 이라는 이름은 이웃을 폭넓게 훑기 전에 한 방향으로 먼저 파고든다는 뜻이다. 되돌아오는 동작이 필요하므로 방문 경로를 stack 에 쌓는다. 재귀 호출로 쓰면 함수 호출 스택이 그 역할을 대신하기 때문에 코드가 짧아진다. 동작 def dfs(graph, node, visited): visited.add(node) fo...
...저 들어온 것을 먼저 내보내는 처리 순서다. 줄을 선 순서대로 처리한다고 보면 되고, 이 규칙을 구현한 자료구조가 큐(queue) 다. 반대는 나중에 들어온 것을 먼저 꺼내는 LIFO 이고, stack 이 그쪽이다. 어디에 쓰나 BFS — 시작점에서 가까운 정점부터 층층이 방문하려면 “먼저 발견한 정점을 먼저 처리” 해야 한다. 큐에 넣고 앞에서 꺼내는 것이 곧 FIFO 다. 반면 DFS ...
Code 실행할 프로그램의 코드가 저장되는 영역 (컴파일 시 크기가 결정됨) Data 전역 변수, static variable 등 컴파일 시 결정되는 것들에 대한 영역 stack
스택 영역을 표시하기 위한 레지스터인 pointer register 의 한 종류 사용하고 있는 stack 의 최상단 주소 (lowest memory address) 를 저장하는데 사용함
스레드는 stack과 Register를 제외한 모든 자원을 공유하므로, 프로세스 간 통신(IPC)보다 스레드 간 통신 비용이 훨씬 적게 듭니다.
먼저 들어온 것을 먼저 내보내는 처리 순서다. 줄을 선 순서대로 처리한다고 보면 되고, 이 규칙을 구현한 자료구조가 큐(queue) 다. 반대는 나중에 들어온 것을 먼저 꺼내는 LIFO 이고, stack 이 그쪽이다.
Depth-First Search. 그래프나 트리에서 한 갈래를 끝까지 따라 내려간 뒤, 더 갈 곳이 없으면 한 칸 되돌아와 아직 안 가본 갈래로 다시 내려가는 탐색 방식이다. “깊이 우선” 이라는 이름은 이웃을 폭넓게 훑기 전에 한 방향으로 먼저 파고든다는 뜻이다.
Finite State Transducer(FST)는 문자열 같은 입력 시퀀스를 읽으면서, 그 입력에 대응하는 출력 값을 함께 반환할 수 있는 finite state machine이다.
Insertion Sort Selection Sort Merge Sort Bubble Sort quick Sort Heap Sort .
Inorder Search preorder Search postorder Search .
선택 정렬은 다음과 같은 순서로 이루어진다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 하나의 원소만 남을 때까지 위의 과정을 반복한다.
BFS(Breadth First Search)는 시작 node 에서 가까운 node 부터 층별로 방문하는 graph/tree traversal 방식이다. 보통 queue 를 사용한다. 동작 흐름 시작 node 를 queue 에 넣고 방문 처리한다.
삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
두 String 이 주어질 경우 문제 (anagram) 인지 확인하기 예시) cat, tac 가 주어질 때, tac 를 잘 나열하면 cat 이 되므로 True 이 문제는 두 가지 방법으로 풀 수 있었음 Counter 사용 두 개의 Counter 가 서로 동일하면 True 만약 하나의 Counter 만 사용할 수...
Pre-order traversal 은 tree 를 순회할 때 현재 node 를 먼저 방문하고, 그 다음 left subtree, right subtree 순서로 방문하는 방식이다.