솔

4.1 Introduction 컴파일러 설계의 필수 단계컴파일러를 제대로 배우려면 한 학기 정도의 집중적인 설계·구현 경험이 필요하다.그 과정의 첫 파트가 어휘 분석(lexical analysis)·구문 분석(syntax analysis)이다.특히 구문 분석기(parser)는 컴파일러의 “심장” 역할을 하며, 이후 단계인 의미 분석기(semantic analyzer)와 중간 코드 생성기가 파서의 결과에 의존한다.⇒ 핵심 개념: 컴파일 파이프라인에서 파서가 전체 흐름을 주도한다.프로그래밍 언어 교재에서 컴파일러 단원을 다루는 이유문법(grammar)의 자연스러운 응용: 3장에서 배운 BNF 등 문법 이론을 실제로 쓰는 가장 직접적인 예시가 파서 설계이다.응용 범위의 확장성: 컴파일러를 쓰지 않는 프로그램(..

3.1 Introduction (서론) 프로그래밍 언어를 간결하면서도 이해하기 쉽게 기술하는 작업은 매우 어렵지만, 그 언어의 성공을 위해 반드시 필요하다.과거 ALGOL 60과 ALGOL 68이라는 언어는 매우 간결하고 형식적인 설명을 사용했으나, 당시 사람들에게 익숙하지 않은 새로운 표기법(notation) 때문에 오히려 이해하기가 어려웠고 그 결과 두 언어 모두 널리 받아들여지지 못했다. 반대로, 어떤 언어는 너무 간략하고 비형식적인 설명 때문에 조금씩 다른 여러 방언(dialect)이 생겨 혼란이 발생하기도 했다. 언어를 설명하는 과정에서 중요한 어려움 중 하나는 이 언어 설명을 읽고 이해해야 하는 사람들이 매우 다양하다는 점이다. • 초기 평가자(initial evaluators)언어의 초기 평..

위상 정렬이란?위상 정렬은 그래프 알고리즘 중 DAG(Directed Acyclic Graph), 즉 방향성이 있으면서 싸이클이 없는 그래프에서 정점들을 순서대로 정렬하는 방법이다.  위상 정렬은 다음과 같은 상황에서 유용하다.- 작업 스케쥴링- 선수 과목에 대한 문제- 데이터 처리 파이프라인 위상 정렬의 조건위상 정렬을 사용하기 위해선 위에서 언급한 것처럼1. edge(간선) 에 방향이 있어야 한다.2. 비순환 그래프 즉, 싸이클이 없어야 한다. 이 두가지 조건을 만족해야 한다. 위상 정렬은 큐 기반 위상 정렬과 dfs 기반 위상 정렬로 나뉜다.두 방식에 대해 각각 알아보자.큐 기반 위상정렬큐 기반 위상정렬은 다음과 같은 단계를 따른다.1.각 정점의 진입 차수(inDegree)를 계산한다.2.진입 차수..

https://www.acmicpc.net/problem/11689  문제자연수 n이 주어졌을 때, 1~n 의 자연수 중 n 과 서로소인 숫자의 개수를 구하는 문제이다. 접근 방법오일러 파이 함수를 이용해야 한다.이는 1부터 n까지의 수 중에서 n과 서로소인 수의 개수를 계산하는 함수이므로 이 문제를 해결하기에 적합하다.따라서, n의 소인수만 찾으면 효율적으로 계산이 가능하다. 오일러 피 함수의 원리는 에라토스테네스의 체와 비슷하다.이렇게, 소수를 찾아서 순차적으로 p[i] = p[i] - (p[i]/2) 연산을 반복적으로 수행해주면 최종 결과는 오일러 피 함수의 결괏값이 배열에 남게 된다. 코드#include #include #include #include // 오일러 파이 함수 구현long long ..

https://www.acmicpc.net/problem/1016  문제 정의min 과 max 가 주어졌을 때, 제곱수로 나누어지지 않는 정수의 개수를 찾아야 한다. 예제 입력 1에서 min=1 , max=10 이 주어졌을 떄, 1보다 큰 제곱수(4,9)로 나누어지지 않는 정수의 개수는 1,2,3,5,6,7,10 으로 7개이다.  위 그림과 같이 2부터 제곱수가 max값을 넘기 전까지 제곱수로 나누어지는 수들을 하나씩 제거해주면 된다.  배열 초기화입력받은 min, max 값에 따라 범위를 설정해주고 배열을 초기화한다.long long range = max - min + 1;std::vector is_power(range, false);  제곱수로 나누어지는 수 순차적으로 탐색i^2 형태의 제곱수를 순회..

https://www.acmicpc.net/problem/1931  여러 시간대가 주어지고, 시간이 겹치지 않으면서 가능한 한 많은 회의실 사용 횟수를 구하려고 한다. 이를 구하기 위해서는, 가장 빨리 끝나는 회의를 찾고, 그 이후에 시작하는 회의 중 가장 빨리 끝나는 회의를 찾고, 이렇게 찾아나가면 될 것 같다. 위와 같이 회의 시간을 찾기 위해서는, 끝나는 시간을 기준으로 정렬되어 있어야 한다.  이를 위해 다음과 같은 구조체와 배열을 만들어 주고,이렇게 끝나는 시간을 기준으로 정렬해주는 cmp함수까지 완성해주면 준비는 끝났다.(끝나는 시간이 같은 경우 시작 시간을 기준으로 정렬)bool cmp(const t& a, const t& b) { if (a.eTime != b.eTime) return a..

https://www.acmicpc.net/problem/1300  이 문제를 풀 때 N의 최댓값이 10^5 이므로 이차원 배열(N x N)을 만들어 문제를 풀면 100억의 메모리가 필요하고, 10^10(log(10^10)) 의 시간이 필요한데 사실상 불가능하다.메모리O(N^2)시간O(N^2 log(N^2))  이 문제에서 요구하는 것은 "정렬된 배열에서 k번째로 작은 값"이다. 만약 어떤 값 x를 기준으로 배열(B) 에서 x 이하의 원소가 몇 개인지만 구하면  “x 이하가 k개 이상이면 → B[k]는 x 이하여야 함”“x 이하가 k개 미만이면 → B[k]는 x 보다 커야 함”위와 같은 기준을 얻을 수 있고, 이분탐색을 이용해 원하는 B[k]를 빠르게 구할 수 있다.   문제를 보면 이론상으론1 이지만,..

int main(){ const int width = 1280, height = 960; const int canvasWidth = width / 80, canvasHeight = height / 80; ... • width, height: 실제 윈도우가 갖게 될 해상도(픽셀 수). • canvasWidth, canvasHeight: 우리가 직접 그릴 ‘캔버스’ 크기를 단순히 줄여서 사용할 수 있음. 위 예시 코드에서는 80으로 나누어, 예를 들어 16x12 정도의 작은 캔버스를 만듦(계산값에 따라 다름). 이 캔버스 크기만큼의 텍스처를 생성해서, 그 텍스처를 풀스크린 사각형에 맵핑하는 구조. WNDCLASSEX wc = { sizeof(WNDCLASSEX), CS_CLASSD..

1. Install the visual studio 2022 community To get started, download Visual Studio 2022 Community Edition using the link below. https://visualstudio.microsoft.com/ko/vs/ Visual Studio 2022 | 무료 다운로드Visual Studio에서 코드 완성, 디버깅, 테스트, Git 관리, 클라우드 배포를 사용하여 코드를 작성합니다. 지금 무료로 커뮤니티를 다운로드하세요.visualstudio.microsoft.comFor this study, we only need the C++ development environment.  2. Install ImGui using V..

8.1 Lower Bounds for Searching Only by Comparisons of Keys 이 섹션에서는 키 비교만을 사용하여 배열에서 특정 키를 검색할 때 소모되는 최악의 경우 비교 횟수의 하한을 다룹니다.특히, Binary Search와 Sequential Search의 의사결정 트리(Decision Tree)를 사용하여 검색 과정의 효율성을 분석합니다. 의사결정 트리 (Decision Tree) • 정의:의사결정 트리는 키 를 배열에서 검색하는 과정에서 발생하는 모든 비교를 나타냅니다. • 각 내부 노드는 키 비교를 나타냅니다. • 각 리프 노드는 검색 결과를 나타냅니다 (성공적으로 검색된 위치 또는 실패). • 예시: • Figure 8.1: 정렬된 배열에서 이진 탐색(Binary ..