본문 바로가기

분류 전체보기

 (169)
Lec11. Semantic Analysis (2) - 11주차 2강, 12주차 2강 2024. 12. 9. 15:39 11주차 2강, 12주차 2강 11/13, 11/2011/18은 휴강 lec10에서 언급한 내용임Abstract Interperetation의 주요 단계abstract domain: 변수는 구체적인 값 대신 추상화된 값으로 표현 됨변수의 값이 가질 수 있는 범위 또는 특성을 정의, 구간 / 옥타곤, 짝홀 등구체적인 의미로는 7에 2를 더하면 9가 되지만, 추상적인 의미로는 홀수에 2를 더하면 홀수이다연산, 불리안 판별, command 처리에 대한 simple language 만드는 과정추상 도메인 개요새로운 기호들이 등장하는데, 본문 슬라이드 내용과 같고이상하게 생긴 육각형은 맨위의 any부터 시작해서 아래로 뻗어나오는 tree처럼 생각하면 됨any: 모든 값 포함non-pos: 0 또는 음의 정수, n..
Lec10. Semantic Analysis (1) - 11주차 1강 2024. 12. 9. 15:24 11월 11일, 11주차 1강* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다.  soundness: 정확성분석기가 p가 안전하다고 생각하면, 실제로 p는 안전해야 한다만약 p가 안전하지 않다면, 분석기는 반드시 unsafe로 판단해야 한다분석기가 error를 놓치지 않아야 한다. no false negativecompleteness: 완전성p가 실제로 안전하다면, 분석기는 반드시 p의 안전성을 증명해야 하낟분석기가 p를 unsafe로 판단했다면, p는 실제로 안전하지 않음분석기가 안전한 프로그램을 위험하다고 판단하지 않아야 한다. no false positive이상적인 분석기: no false negative, no false positivehard l..
Lec09. Lexer & Parser Generators - 10주차 2강 2024. 12. 8. 23:10 11월 6일 - 10주차 2강* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다. Goal: Useful Tools for Compiler ConstructionLexing and Parsing algorithmLexer: Thompson 알고리즘 및 Subset 구성Parser: top-down, bottom-up컴파일러 제작 도구lexer, parser 수동으로 안만들어도 됨. ocamllex, ocamlyacc로 자동화 가능ocamlyacc: LALR, OCaml용 parser 생성기(구문분석기)ocamllex: OCaml용 lexer 생성기(어휘분석기)Compiler Construction with ocamllex and ocamlyacc전반적으로 ..
[백준] 1522 문자열 교환 / 구현 / python 실1 2024. 12. 4. 23:21 슬라이딩 윈도우 풍년이네https://www.acmicpc.net/problem/1522a랑 b 섞인 문자열이있고 문자 위치를 교환해서 a가 쭉 연속된 문자열로 만들기 위해필요한 최소 교환 횟수를 구해야 한다 문자열이 원형이라 처음과 끝이 이어져있다는게 관건 원형 처리를 원활하게 하기 위해 문자열을 두번 이어붙인다 처음 size만큼의 문자에서 b의 개수를 세어 초기 윈도우 값으로 사용한다 1부터 문자열 길이번째 원소까지 탐색한다슬라이딩하면서 윈도우의 왼쪽 문자를 제거하고, 오른쪽 문자를 추가하면서한 칸씩 이동한다이때 왼쪽 문자가 b였으면 b개수-1, 오른쪽 문자가 b였으면 b개수+1한다 이전 최소 값과 현재 값을 min으로 비교해서 업데이트한다 계속 윈도우를 이동시키면서 b의 개수가 최소로 포함되는 구간..
[백준] 1283 단축키지정 / 구현 / Python 실1 2024. 12. 3. 16:28 https://www.acmicpc.net/problem/1283 뭔가 오랜만에 보는 코테같은 문제...진짜 구현 같은 문제? 각 줄마다 입력되는 단어를 공백으로 구분해서 배열로 추가한다그럼 이차원 배열 형태가 된다 이차원 배열을 탐색하면서i번째 원소를 k라고 둔다k 안에도 여러 개의 단어가 들어있으니 다시 for문을 돌린다 k 안에 있는 j번째 단어는 key라고 지정한다 일단 각 단어의 첫 글자가 단축키로 지정이 되어야 하기 때문에가장 먼저 key의 0번째 요소를 본다(* 모든 요소를 비교할 때는 lower case로 바꿔서 비교해야 대소문자 구분없음 조건을 잘 충족할 수 있다 0번째 요소가 아직 단축키에 없으면(save 배열에 없으면)save 배열에 key[0]요소를 추가한다그리고 해당 단어를 출력 ..
[백준] 24037 문자열게임2 / 구현 / python 골5 2024. 12. 2. 12:23 보자마자 슬라이딩 윈도우라는 생각 https://www.acmicpc.net/submit/20437 처음에는 '20922_겹치는 건 싫어'의 풀이를 응용해보려고 했다이 풀이는 어떤 문자를 k개 이하로 포함하는 가장 긴 부분 수열을 구하는 문제 그래서 이걸 응용해서 어떤 문자를 정확히 k개 포함하는 가장 짧은 부분 수열을 구하는 것까지는 괜찮았다근데 어떤 문자를 k개 포함하면서, 처음과 끝이 그 문자로 이뤄진 수열을 구하는 부분에서 좀 오차가 있었다 from collections import defaultdictt = int(input())for i in range(t): a = list(map(str, input().strip())) k = int(input()) n = len(a) ..
[백준] 11501 주식 / 그리디 / python 실2 2024. 12. 1. 16:04 https://www.acmicpc.net/problem/11501 역순으로 풀면 풀리는 문제 처음에는 정순으로 푸려고 했다 오늘 가격보다 내일 가격 작으면현재 구매했던 티켓을 다 팔아버리기 오늘 가격보다 내일 가격이 크거나 같으면한장 사기 근데 생각해보니내일 작다고 당장 팔아버리는 것보다그 다음에 더 큰 값이 나왔을 때 존버하고 파는 게 나은건가?그런 생각이 들긴 했다 처음에 구현했던t = int(input())for i in range(t): n = int(input()) a = list(map(int,input().split())) #3 #10 7 6 #감소수열은 아무것도 안사고, 안파는게 맞음 #3 #3 5 9 #증가 수열은 하루에 하나씩 사고, 마지막날..
[백준] 2668 숫자고르기 / dfs / python 골5 2024. 11. 30. 23:14 첫째 줄 숫자를 노드로둘째 줄 숫자를 노드와 연결된 숫자로 생각하면그래프 간선이라고 생각할 수 있다 입력받을 때 방향성 그래프 형태로 구성한다 뽑힌 숫자들이 이루는 집합, 숫자들이 가리키는 숫자들이 이루는 집합이 두 개가 동일하려면 집합 내 숫자들은 사이클을 형성해야 한다최대 사이클을 찾는 문제로 해석할 수 있다 그래프를 돌면서 현재 원소를 방문한 적이 없으면 dfs함수를 돌린다해당 원소가 시작점이 되기 때문에, 해당 원소와 빈 배열을 dfs 함수로 넘겨준다 dfs 함수만약 현재 node가 이미 방문된 경우현재까지 누적된 경로에 node값이 존재한다면 사이클임path에서 사이클에 해당하는 부분을 잘라 result 집합에 추가한다 현재 node를 방문 처리한다현재 node를 path에 추가한다현재 node..
728x90

티스토리툴바