염딩코

Longest Common Substring 과 Longest Common Subsequence 란? LCS는 주로 최장 공통 부분 수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다. 문자열 ABCDEF와 GBCDFE를 이용하여 차이점을 예시로 들어보면 해당 예시에서 최장 공통 부분수열(Longest Common Subsequence)은 BCDF, BCDE가 될 수 있습니다. 부분수열이기 때문에 문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열을 찾으면 됩니다. 최장 공통 문자열(Longest Common Substring)은 BCD입니다. 부분문자열이 아니기 때문에 한번에 이어져있는 문자열만 가능합..

안녕하세요! 오늘은 컴퓨터 성능 향상에 중요한 역할을 하는 '캐시(cache)'에 대해 알아볼까요? 캐시는 여러분도 자주 들어보셨을 텐데, 여기서는 누구나 쉽게 이해할 수 있는 방식으로 이 설명해 드리겠습니다. 그럼 시작해 볼까요? 1. 캐시란 무엇인가요? 캐시는 '고속 저장 장치'로, 컴퓨터에서 중요한 역할을 하는 주요 컴포넌트 중 하나입니다. CPU와 메모리 사이에서 데이터를 빠르게 전달하기 위해 사용되는데, 한마디로 "가까워서 빠른 임시 저장소"라고 생각하시면 됩니다. 캐시가 없다면 CPU는 느린 주변장치인 메모리에서 원하는 데이터를 찾아야 하기 때문에 성능이 저하됩니다. 2. 캐시의 역할은 무엇인가요? 캐시는 컴퓨터 성능을 향상하고 실행 속도를 높이기 위한 역할을 합니다. 메모리에서 자주 사용되는..

가상 메모리는 컴퓨터 시스템에서 물리적 메모리의 용량을 초과하여 프로그램의 메모리 공간을 가상적으로 늘이는 기술입니다. 주요 이점은 크게 메모리 관리 향상, 컴퓨터 자원의 효율적 사용 및 프로세스 구현 단순화 등입니다. 가상 메모리는 페이징 및 세그먼테이션 방식으로 구현되며, 사용하는 주소 공간은 물리적 메모리 넘어서어 하드 디스크 또는 SSD에 저장되어 있습니다. 가상 메모리의 주요 동작 과정은 다음과 같습니다: 1. 주소 변환: 프로그램이 실행되기 위해 가상 주소가 참조됩니다 이 때, 가상 주소를 물리적인 메모리 주소로 변환하는 단계가 필요합니다. 이 과정에서 MMU(Memory Management Unit)가 주소 변환 역할을 수행합니다. 2. 메모리의 데이터 로드 및 저장: 변환된 물리 주소에 대..

안녕하세요! 오늘은 C# 프로그래밍 언어에서 중요한 개념인 get과 set 속성에 대해 알아보려고 합니다. get과 set은 C#에서 속성을 정의하고 접근하는 방법을 제공합니다. 이를 통해 데이터의 캡슐화와 접근 제어를 유연하게 할 수 있습니다. 1. get 속성 get 속성은 해당 속성의 값을 반환하는 역할을 합니다. 속성의 값을 가져오는데 사용되며, 일반적으로 public으로 선언됩니다. get 속성은 속성 이름 앞에 get 키워드를 사용하여 정의합니다. 예시를 통해 살펴보겠습니다: private int age; // 필드 public int Age { get { return age; } // get 속성 } 위의 예시에서 Age 속성은 age라는 private 필드의 값을 반환합니다. 다른 클래스나..

이번 시간에는 Backtracking에 대해서 알아봅시다! Backtracking이란 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. DFS와 Backtracking DFS DFS는 가능한 모든 경로(후보)를 탐색합니다. 따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못합니다. 따라서 N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 불가능할 것입니다. Backtracking 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아갑니다. 즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다. 이를 pruning..

안녕하세요! 여러분 오늘은 허프만 코드(Huffman code)에 대해서 공부해 봅시다:) Huffman code란 무엇일까? 압축(compression)은 자료의 크기를 줄이기 위해서 사용합니다. 이 압축을 하는 방식에 따라서 압축된 파일의 용량이 달라질 수 있는데, 그 중 Huffman code는 문자의 출현 빈도에 따라서 다른 길이를 사용하여 압축하는 그리디 알고리즘(greedy algorithm)입니다. Huffman code는 데이터를 매우 효율적으로 압축합니다. 경우에 따라 20%~90%의 용량을 아낄 수 있습니다. Huffman code는 prefix-free* codes로 표현됩니다. prefix-free코드는 어떠한 문자라도 항상 최적의 데이터 압축을 보장합니다. (*prefix code..

Database Organized collection of inter-related data that models some aspect of the real-world. Databases are the core component of most computer applications. Flat File Strawman (strawman은 잘 동작하지 않을 것을 의미함.) Store our database as comma-separated value(CSV) files that we manage ourselves in our application code. Use a separate file per entity. The application must parse the files each time they w..

Merge sort Implementation Divide 하나의 배열을 반으로 나눠 2개의 배열로 만든다. Conquer Subarray가 충분히 작아졌다면, 정렬시킨다. Subarray가 충분히 작지 않다면, Recursion Merge 정렬된 subarray를 합쳐서 하나의 배열로 만든다. Pseudo code // 위의 그림과 함께 보면 이해하기 쉽다. public static void mergeSort(int n, keytype[] S) { if(n > 1) { // 1개일 때는 할 것이 없음. const int h = floor(n/2), m = n-h; // 반으로 나눔. keytype[] U = new keytype[1...h]; keytype[] V = new keytype[1...m];..

동기와 비동기는 프로그래밍에서 중요한 개념 중 하나입니다. 이 둘은 서로 다른 실행 방식을 갖고 있고, 이를 이해하는 것은 프로그래밍에서 매우 중요합니다. 동기적 실행은 각 작업이 순서대로 실행되는 것을 의미합니다. 이것은 일련의 작업 중 하나가 완료될 때까지 다음 작업이 시작되지 않음을 의미합니다. 즉, 코드의 실행이 차단될 수 있습니다. 이는 작업이 오래 걸리거나 중단되는 경우에 문제가 될 수 있습니다. 비동기적 실행은 작업이 순차적으로 실행되지 않는 것을 의미합니다. 대신, 작업은 병렬로 실행됩니다. 비동기 코드는 대개 콜백 함수나 프로미스를 사용하여 처리됩니다. 이러한 방식으로 비동기적 실행은 코드의 차단을 방지할 수 있으므로 응용 프로그램의 반응성을 향상하고, 더 많은 작업을 더 빠르게 처리할 ..

모든 경우의 수를 전부 고려하는 알고리즘. 백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식입니다. 일종의 트리 탐색 알고리즘이라고 봐도 됩니다. 방식에 따라서 * 깊이우선탐색(Depth First Search, DFS) * 너비우선탐색(Breadth First Search, BFS) * 최선 우선 탐색(Best First Search/Heuristic Search) (그냥 뇌없이 짤 수 있다는 것이 장점입니다.) DFS와 Backtracking * DFS(깊이 우선 탐색) : DFS는 가능한 모든 경로(후보)를 탐색합니다. 따..