문자열 압축 문제

목표알파벳의 연속으로 주어진 문자열을 각 문자에 대응되는 개수순으로 문자열을 압축하기방법방법에는 크게 두가지가 있다. 문자열 전체를 순회해서 알파벳의 문자별로 하나씩 세는 방법과 문자열을 한번 정렬한 뒤에 알파벳을 문자별로 세는 방식이 있다. 전자는 한 문자당 문자열 전체를 순회해야하는 반면에 후자는 문자열을 정렬하는 비용을 투자하는 대신에 정렬 단계 이후에는 문자열을 한번만 순회하면 된다.분석전자는 시간복잡도가 O(N^2)이다. 후자는 O(NlogN + N)이다. 따라서 데이터의 크기가 무한할 때 후자가 성능이 좋다.정리로직 중에 컨테이너가 데이터를 전체 탐색해야하는 경우에 정렬을 먼저하자.

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 12. 8.

캐시

캐시란캐시는 빠른 장치와 느린 장치 사이의 병목현상을 줄이기 위한 데이터 임시저장소이다.데이터를 임시로 저장하면 해당 데이터를 다시 계산하고 가져오는 시간 등을 절약할 수 있다. 캐시의 예CPU의 레지스터Redis 데이터베이스용어캐시히트: 빠른 장치가 캐시에 원하는 데이터를 찾아내는 사건캐시미스: 원하는 데이터를 찾아내기 못한 사건캐시미스가 발생할 경우, 빠른 장치는 느린장치로 접근해서 원하는 데이터를 캐시에 등록한다.지역성의 원리캐시를 설정할 때는 자주 사용하는 데이터 이여야한다. 자주 사용하는 데이터의 판단기준은 지역성이다. 지역성은 시간적 지역성과 공간적 지역성으로 나뉜다.시간적 지역성: 최근에 사용하는 데이터에 다시 접근하려는 특성공간적 지역성: 최근에 접근한 데이터의 인근 데이터에 접근하려는 특..

• format_list_bulleted 컴퓨터과학/운영체제
• · 2024. 12. 6.

탐색

탐색탐색이란 자료들 중에 원하는 자료를 찾는 작업이다. 자료들의 구조와 형태에 따라 탐색의 성능이 결정된다.항목이란 탐색의 기본단위다. 항목은 항목키와 데이터로 구성된다. 항목키는 항목 식별자다. 따라서 탐색이란 특정 항목키를 가진 항목을 찾는 작업이다.순차탐색순차탐색은 정렬 되어 있지 않은 배열에서 항목을 찾는 작업으로 가장 직관적이고 구현하기가 쉽다. 순차탐색 함수는 탐색범위가 low부터 high까지 매개변수로 주어지고 탐색이 성공하면 항목의 인덱스를, 실패하면 -1을 반환한다.

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 12. 5.

시스템 간의 데이터 교환: JSON, XML

시스템 간의 데이터 교환다양한 시스템 간에 데이터를 효율적으로 교환하기 위해서는 통일 된 양식이 필요하다. 초기에는 XML 형식으로 데이터를 교환하였다. 하지만 XML보다 더 가벼운 양식이 필요하여 JSON이 만들어졌다. 시스템 간에 데이터를 교환할 때는 시스템 외부로 보내기 위한 작업인 직렬화, 외부 데이터를 받아서 시스템 내부에서 처리하기 좋은 형태로 변환하는 역직렬화 과정을 거친다. 직렬화와 역직렬화직렬화란 외부의 시스템에서도 사용할 수 있도록 데이터를 바이트 스트림 형태로 변환하는 기술이다. 바이트 스트림은 데이터를 담는 양식으로 JSON, XML 등이 있다.역직렬화란 외부에서 들어온 바이트 스트림을 시스템에서 처리할 수 있는 형태로 변환하는 기술이다. 자바스크립트 시스템에서 JSON을 받은 경우..

• format_list_bulleted 컴퓨터과학/CS기초
• · 2024. 12. 3.

다이나믹 프로그래밍

최적화 문제정의최적화 문제란 주어진 조건 하에서 목표를 최대화하거나 최소화하는 해를 찾는 문제를 말한다.구성요소목표함수: 최적화하려는 대상으로 이를 최대화하거나 최소화한다.제약조건: 최적화 과정에서 반드시 지켜야할 조건이다. 예를 들어 자원의 제한 등이다.변수: 최적화 대상이 되는 요소로 주로 생산량, 경로, 작업 스케줄 등이다.예시일상생활에서 지도를 따라 최단경로 찾기가 있다. 시작점에서 도착점까지의 이동거리, 시간, 비용 등을 최소화하려하기 때문이다. 금융에서는 포트폴리오 최적화, 가격 책정 최적화가 있고 운송 등에서 버스 배차시간 최적화 등이 있다.해결방법론최적화 문제의 특징에 따라 적용할 수 있는 방법들이 나뉜다. 최적화문제가 최적부분구조를 갖고 있는 경우에 분할정복 기법을 적용할 수 있다. 하지..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 11. 29.

1.9 중요한 주제들

2024.11.29 - [컴퓨터과학/컴퓨터구조: CSAPP] - 1.8 시스템은 네트워크를 사용하여 다른 시스템과 통신한다 1.8 시스템은 네트워크를 사용하여 다른 시스템과 통신한다2024.11.27 - [컴퓨터과학/컴퓨터구조: CSAPP] - 1.7 운영체제는 하드웨어를 관리한다 ( 운영체제, 프로세스, 가상메모리, 파일) 1.7 운영체제는 하드웨어를 관리한다 ( 운영체제, 프로세스, 가상메모리,gyht.tistory.com내 작업이 의미를 판단하는 법개발자가 인정 받는 방법 중에 하나는 프로그램의 성능을 개선하는 것이다. 하지만 성능이란 뭘까? 우리는 동일한 작업이라도 더 빠르게 처리하는 프로그램이 있다면 그 프로그램의 성능이 좋다고 한다. 즉, 동일 작업을 더욱 빠르게 처리할 수 있도록 프로그램을 ..

• format_list_bulleted 컴퓨터과학/컴퓨터구조
• · 2024. 11. 29.