Computer Science

오늘은 스택과 큐 자료 구조를 복습한다.스택스택은 LIFO(후입선출) 구조의 자료를 말한다.사용 예시로 이전에 재귀에서 살펴본 시스템 스택이나 DFS을 생각할 수 있다. 구현은 3가지 정도의 방법으로 해볼수 있다.- 리스트를 이용해 전역변수로 구현하는 방법- 구조체리스트를 통해서 마지막 인덱스와 리스트를 함께- allocation(malloc, realloc...) 을 활용한 동적 스택 생성 스택문제의 대표 예시는 다음과 같다.- 괄호 검사 알고리즘- 전위, 중위, 후위 표기식큐큐는 FIFO(선입선출) 구조의 자료를 말한다.사용 예시로 BFS, CPU 스케줄링을 생각할 수 있다 구현은 선형 큐 혹은 원형 큐의 형태로 만들게 된다.퀴즈스택과 큐의 차이점을 설명하고, 각 자료구조가 실제 문제 해결에 어떻게 ..

알고리즘의 점근적 효율성입력의 크기가 커질수록 알고리즘의 효율성을 따지는 것은 매우 중요한 문제다.오늘은 알고리즘의 효율성을 점근적인 평가방식에 대해서 이야기 한다. 알고리즘의 실행 시간알고리즘이 실행완료되는데에 걸리는 실행시간은 입력의 크기에 따라서 달라진다.특히 알고리즘이 돌아가는 하드웨어에 따라, 운영 환경에 따라서 달라지는 부분이다.따라서 실제적인 시간을 따지는 것은 측정이 정확하지 않다. 이런 이유로 우리는 기본 연산(산술/ 비교...)이 몇번 실행되는지를 통해서 측정하게 된다.다만 이 경우 또한 입력 데이터에 따라서 달라진다. 예를 들어서 정렬 알고리즘의 기본연산 횟수를 세어보려고 한다.극단적으로 생각해서, 입력으로 들어오는 값이 이미 정렬된 채로 들어오는 경우가 있을 수 있다.반대로 정렬과 ..

알고리즘 문제를 풀면서 가장 기본적이고, 많이 이용하게 되는 반복과 재귀에 대해서 알아보자.반복우리가 보통 사용하는 while문이나 for문등을 통해서 명령의 반복적인 실행을 통해 로직을 구성하고, 해결하는 것을 말한다.재귀와 비교했을때 일반적으로는 속도가 더 빠르고, 스텍 메모리를 사용하지 않는다는 장점이 있다.다만 무한루프가 생기는 경우에 CPU사이클이 반복적으로 사용된다는 문제가 발생한다.재귀재귀는 함수 자기자신을 다시 호출하여 수행하는 형태의 로직을 말한다.즉, 큰 문제를 풀기 위해서 동일한 구조의 작은 문제로 분할하여 해결한다.반복문보다는 속도가 느릴 수 있고(알고리즘마다 다를 수 있음), 재귀 호출시에 변수나, 리턴값, 위치 등이 스택메모리에 저장되게 된다. 따라서 무한 재귀가 발생하면 스택 ..

오늘부터 매주 다년간 학교에서 공부한 내용을 짧고 간결하게 훑어보는 시간을 가지기로 했다!! 따라서 이 포스팅에는 어떤 공부를 했는지에 대한 개요와 관련 포스팅url을 업로드 할 예정이다.  소프트웨어의 기초 (자료구조+알고리즘)재귀와 반복 https://he-kate1130.tistory.com/114알고리즘의 성능 https://he-kate1130.tistory.com/115스택 / 큐 https://he-kate1130.tistory.com/116우선순위 큐정렬색인과 이진검색트리균형 검색 트리해시 테이블그래프

형식 언어 컴파일러를 만들기 위해서는 언어에 대한 이해가 선행되어야 한다는 것을 지난 장에서 살펴보았다. 언어에 대해서 잘 이해하고, 체계적으로 전개하기 위해서는 "잘 정의된 언어"가 어떤것인지 알아야 한다. 이처럼 잘 정의된 언어를 형식 언어라고 부른다. 형식언어는 보통 문장의 집합으로 정의된다. 2장에서는 언어를 형식적으로 정의하고, 언어를 표현하는 방법으로 사용되는 문법을 정의한다. 형식 언어의 기본 개념 형식언어는 문장들의 집합으로 정의된다. Alphabet 알파벳은 문장을 이루는 기본 심볼(기호)들의 유한 집합이다. 형식언어이론에서는 알파벳이 보통 소문자 a, b, c... 과 같은 심벌들을 사용한다. String (sentence, word) 알파벳 T에 대한 스트링은 알파벳 T에 속하는 심벌..

데이터베이스 데이터베이스는 조직에 필요한 정보를 얻기 위해서 논리적으로 연관된 데이터들을 모아 구조적으로 통합해둔 것을 말한다. 즉 데이터베이스는 여러사람이 공용으로 사용하기 위해서 통합하고, 저장한 운영 데이터의 집합을 말한다. 데이터베이스 시스템(DBMS) 데이터베이스 시스템은 각 조직에서 사용하던 데이터를 통합하고 공유할 때 생기는 장점을 이용하는 시스템이다. 데이터베이스 시스템은 아래 세가지로 구성된다. DBMS: 사용자와 데이터베이스를 연결하는 소프트웨어 데이터베이스: 데이터를 모아둔 집합 데이터모델: 데이터 저장 기법 관용적으로 데이터베이스 시스템을 DBMS라 표현하기도 한다. 정보 처리 기술의 발전 현재까지 정보 처리 기술의 발정 양상 예시를 살펴보자. 시기 단계 정보통신 기술 특징 1970..

컴파일러를 만든다면 한땀한땀...직접 코드를 넣어야 하는걸까? N개의 언어를 사용할 수 있고, M개의 컴퓨터에서 동작하게 하려면 우리는 NxM개의 컴파일러를 작성해야 한다. 완전 무리..! 하지만 우리에게는 컴파일러 자동화 도구, 컴파일러 생성기가 있습니다. (컴파일러의 컴파일러) 컴파일러 생성기는 컴파일러의 전 과정이나 각 단계를 자동 생성하는 도구들을 말한다. 컴파일러 생성기 컴파일러 생성기는 목적 기계에 대한 기계 표현을 입력으로 받아서 하나의 컴파일러를 출력하게 된다. 이렇게 출력된 컴파일러는 소스 프로그램을 입력으로 받아 목적 기계의 코드로 번역하는 컴파일러이다. Lexical Analyser Generator 어휘 분석기 생성기는 어휘분석기를 자동생성하는 도구이다. 토큰에 대한 표현을 입력으로..

컴파일러는 고급 언어로 쓰인 프로그램을 어떤 특정 컴퓨터에서 직접 실행이 가능한 형태의 프로그램으로 번역해주는 컴퓨터 프로그램이다. 일반 컴파일러 구조 컴파일러의 일반적인 구조는 다음과 같이 생겼다. 크게 프론트 앤드와 백앤드로 나눌 수 있다 프론트앤드: 소스 언어에 의존하는 부분으로, 소스 프로그램을 분석하고, 중간 코드를 생성한다. 백엔드: 목적 기계에 의존하는 부분으로, 중간 코드를 특정 기계를 위한 목적 코드로 번역한다. 프론트앤드 프론트앤드는 언어에 의존하므로, 각 언어마다 하나씩 필요하다. 기계에 비하면 언어의 문법이 명확히 정의되어있기 때문에 프론트앤드는 잘 정립되어있는 부분이다. 프론트앤드의 기능에 대해 살펴보자면, 프론트앤드의 역할은 소스 프로그램을 읽어들이고, 어휘분석, 구문 분석을 통..

번역기 번역기란 하나의 프로그래밍 언어로 작성된 프로그램을 입력으로 받아 동등한 의미를 갖는 다른 프로그래밍 언어로 된 프로그램을 출력하는 시스템 프로그램을 말한다. 여기서 입력되는 프로그램을 소스 프로그램이라 하고, 출력되는 프로그램을 목적 프로그램(목적 언어로 작성된)이라 한다. 번역기의 종류 번역기는 입력과 출력 프로그램에 따라 여러 종류로 나뉘게 된다. Preprocessor 프리프로세서의 경우 #include같은 지시문이 있는 경우 이를 처리해 확장된 프로그램을 출력한다. 따라서 이 경우에는 소스와 목적 프로그램의 언어가 모두 고급 언어가 된다. 여기서 "확장"은 매크로 처리 기능, 조건부 컴파일 기능(Conditional Compile), 헤더파일이 포함된 파일 포함 기능(File includ..