본문 바로가기

Computer Science25

트리의 순회 - 레벨 순서 순회 1. 레벨 순서 순회란? 레벨 순서 순회는 위에서 아래로, 좌에서 우로 순차적으로 순회를 하는 것입니다. 위의 트리에서 레벨 순서 순회를 할 경우, 결과는 1 - 2 - 3 - 4 - 5 - 6 이 됩니다. 개념적으로는 가장 이해하기 쉽고 간단한 순회 방법이지만, 구현은 상대적으로 까다로운 편입니다. 2. 구현 1) 재귀 Queue q = new LinkedList(); public void levelOrder(TreeNode node) { System.out.print(node.getData() + " "); // ① q.add(node.getLeftChild()); // ② q.add(node.getRightChild()); TreeNode temp = q.remove(); // ③ if(temp !.. 2022. 10. 12.

트리의 순회 - 전위 순회, 중위 순회, 후위 순회 1. 트리의 순회 (Tree traversal) 트리 순회란 트리의 모든 노드를 방문하는 것을 말합니다. 방문 순서에 따라 다음 3가지 방법이 있습니다. 처음에는 헷갈리지만 몇 번만 연습해보면 매우 간단하다는 것을 깨닫게 되실 겁니다. 2. 전위 순회(preorder) - VLR 전위 순회는 먼저 자기 자신을 방문한 뒤, 왼쪽 자식-오른쪽 자식 순으로 방문합니다. 만약 자식에게 또 자식이 있다면 자식 노드를 방문하기 전에 자식의 왼쪽 자식 노드를 방문합니다. 즉, 자기 자신을 방문한 다음(V) 왼쪽 자식으로 이동하여 자식이 있는 지 확인하고, 있다면 자식이 없는 리프 노드(leaf node)를 만날 때까지 계속 왼쪽으로 이동합니다. 왼쪽 서브트리에 대한 방문을 모두 마친 뒤에야 (L), 오른쪽 자식에 대.. 2022. 10. 11.

스택과 (원형) 큐 Stack & Queue 만들기 1. 소개 스택과 큐는 쉽고 간단하지만, 운영체제의 시스템 스택이나 스케줄링 등 다방면으로 활용되는 중요한 자료구조입니다. 스택과 큐는 모두 원소를 하나씩 저장하고 저장된 원소를 순서대로 출력 및 삭제하는 방식으로 동작합니다. 차이점으로는, 스택은 가장 나중에 입력된 원소가 가장 먼저 출력되는 후입선출(Last In First Out, LIFO) 방식인 반면, 큐는 가장 먼저 입력된 원소가 가장 먼저 출력되는 선입선출(First In First Out, FIFO) 방식입니다. 2. 구성 스택과 큐는 기본적으로 원소들을 저장할 저장소와 현재 위치를 기억하는 포인터, 그리고 현재 상태를 체크할 2가지 메서드, 핵심 기능인 삽입과 삭제를 위한 메서드 2개가 필요합니다. 3. 구현 with Java (1) 스택.. 2022. 9. 27.

OS 프로세스와 스레드 프로세스 Process : 실행 중인 프로그램 또는 스케줄링의 대상이 되는 작업을 말합니다. 프로그램이 실행되려면 우선 메모리에 적재되어야 하고, 스케줄러가 자원을 할당해줄 때까지 기다려야 합니다. 이때 메모리에서 자기 차례를 기다리거나 실행되고 있는 프로그램의 인스턴스를 프로세스라고 합니다. 프로세스는 ① 코드, 데이터, 힙, 그리고 스택으로 나뉘는 메모리 영역 ② CPU 시간 ③ 주소공간 등을 할당받게 됩니다. 각각의 프로세스는 독립적이며 서로 데이터를 주고받기 위해서는 특별한 통신방법을 통해야 합니다. - Inter Process Communication (IPC, 프로세스간 통신) : socket, message queue, pipe, named pipe, semaphore, shared memo.. 2021. 11. 30.

선택정렬, 버블정렬, 삽입정렬 1. 개요 1) 선택정렬 가장 간단한 정렬방법입니다. 6 3 4 5 1 2 리스트 중에서 최소값을 찾아 맨 앞에 위치시킵니다. 1 6 3 4 5 2 그리고 나머지 원소 중에서 다시 최소값을 찾습니다. 1 2 6 3 4 5 이를 n번 반복하면 1 2 3 6 4 5 1 2 3 4 6 5 1 2 3 4 5 6 정렬된 리스트를 얻을 수 있습니다. 2) 버블정렬 오른쪽 끝에서부터 최소값(왼쪽에서 시작할 경우는 최대값)을 거품이 올라오듯 보글보글 불러오는 방법입니다. 인접한 두 개 원소를 비교해서 작은 값을 땡겨오고 또 옆에 있는 놈과 비교해서 땡겨오고 하다보면 최소값이 리스트 시작점에 쌓이게됩니다. 3) 삽입정렬 길이가 1인 정렬된 리스트에 원소를 하나씩 추가하여 정렬된 리스트의 길이가 n이 되면 종료합니다. 2.. 2021. 11. 9.

스택과 괄호의 값 문제 : https://www.acmicpc.net/problem/2504 1. 개요 주어진 괄호들이 규칙에 맞는지 확인, 계산하는 문제입니다. 2. 고난과 역경 1) check () 우선 괄호의 짝이 맞는지 확인하기 위해 왼쪽 괄호를 하나씩 읽어와 스택에 추가합니다. 오른쪽 괄호를 만났을 때 스택이 비어있거나, 꺼내온 값이 왼쪽 괄호가 아니라면 규칙에 어긋나므로 0을 리턴합니다. 처음 완성한 check() 에는 " ( ( [ " 와 같이 왼쪽 괄호만이 들어왔을 때 그냥 통과시켜버리는 문제가 있었습니다. check가 규칙에 맞지 않는 녀석들을 통과시켜버리는 바람에 EmptyStackException 이 발생했습니다. for 문이 종료되었을 때, 스택에 값이 남아있다면 0을 리턴하는 문장을 추가하여 문제를.. 2021. 11. 4.

이전 1 2 3 4 5 다음

티스토리툴바