본문 바로가기

Computer Science26

다이나믹 프로그래밍 Dynamic Programming 1. divide and conquer와 dynamic programming의 차이 divide and conquer(분할정복)는 하나의 문제를 해결할 수 있을 정도의 작은 부분으로 분할하여 하나하나 정복해나가는 프로그래밍 기법을 말합니다. 작게 나눌수록 복잡해 보였던 문제는 단순화되고 보다 쉽게 해결책을 도출해낼 수 있게 됩니다. dynamic programming(동적계획법)은 문제를 작은 조각들로 분해하여 한꺼번에 해결한다는 점에서 분할정복과 유사해보입니다. 하지만 분명한 차이가 있습니다. 분할정복은 하나의 문제를 작은 문제들로 나누고, 그 작은 문제들을 해결한 결과를 합쳐나가는 방식으로 문제에 대한 최종 해를 구하는 것인 반면, 다이내믹 프로그래밍은 일련의 문제들을 해결하기 위해서 문제를 작은 조.. 2022. 12. 29.

트리의 순회 - 레벨 순서 순회 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.

이전 1 2 3 4 5 다음

티스토리툴바