전체 글 (23) 썸네일형 리스트형 Codeforces 769(Div2, 1632)-C "Strange Test" https://codeforces.com/problemset/problem/1632/C - DP로 풀려 했는데, 상태 정의가 어려워 보인다. - 비트와이즈 OR 연산이 매우 중요해보인다. $a := a | b$의 연산은 $a >= b$의 상태로 만들어 준다. 총 매칭에서 이 연산을 두 번 하는 것이 의미가 없는 건 아닐까? - "어느 상태에서든 OR 연산을 한 번 진행하면 다시 OR 연산을 하는 것은 불필요한 일이다"라는 걸 증명해야함 - 복잡하게 증명할 필요없이 위에서 말한 것 하나로도 증명이 된다. 문제에서 $a$가 커질 수 있는 방법은 두 가지이지만, $b$가 커지는 방법은 한 가지 방법 밖에 없다. 그렇다면 결국 $a >= b$ 상태가 되었을 때는, $a - b$의 횟수로만 서로 같은 값에 도달할.. 소프트웨어 빌드 시스템 원리와 활용 요약 (2) - 2. Make 기반 빌드 시스템 2. Make 기반 빌드 시스템 - GNU Make의 예시와 작동 방식을 보여주는 챕터이다. - 책에서는 c 파일로 예제를 진행하는데, 나는 c++로 수정하여 작성하였다. 코드와 Makefile은 https://github.com/lss0815/software_build_system_review/tree/main/chap2를 참고하면 된다. 2.1 계산기 프로그램 예제 - add.c, calc.c, muilt.c, numbers.h, sub.c의 소스코드가 있을 때, calculator라는 타겟파일을 생성할 것이다. $ g++ -g -c add.cpp $ g++ -g -c calc.cpp $ g++ -g -c mult.cpp $ g++ -g -c sub.cpp $ g++ -g -o calculator a.. 소프트웨어 빌드 시스템 원리와 활용 요약 (1) - 0. 서론, 1. 빌드 시스템 개요 0. 서론 빌드 시스템 개선의 필요성 - 20인 이하의 개발 조직에서 빌드에 인한 평균 생산성 저하량 10% 책에서 다루는 내용 - 빌드 시스템 원리 이해 - 빌드 시스템 경험 공유 1. 빌드 시스템 개요 1.1 빌드 시스템이란? 특정 유형의 데이터(입력물)를 다른 유형의 데이터(출력물)로 변환하는 과정에 포함된 활동을 관리하는 시스템 - 컴파일형 언어 버전 관리 도구 -> 소스 트리 -> 오브젝트 트리 -> 릴리즈 패키지 1.2 빌드 시스템의 구성 요소 - 버전 관리 도구 git이 대표적인 툴, 소스 파일 협업, 수정 이력 관리 - 소스 트리와 오브젝트 트리 디렉토리에 저장된 구조를 말함 - 컴파일 도구와 빌드 도구 C 컴파일러: C 언어 소스 파일을 기계어 코드로 변환하여 오브젝트 파일 생성 링커(L.. 소프트웨어 빌드 시스템 원리와 활용 요약 (0) 언젠가부터 회사 프로그램들 빌드 속도가 느려진 것 같아서 최적화 방법을 찾아보다가 책을 한 번 구매해봤다. 알라딘 중고서점에서 나름 저렴하게 책을 살 수 있었는데, 책 상태는 괜찮아 보인다. 책 정보는 링크에서 찾아볼 수 있고, 빌드 시스템에 대해 설명하는 책이다. 내가 업무에서 사용하고 있는 툴을 다루기도 하고 번역본으로 쉽게쉽게 읽어보며 정리해볼 것이다. 알고리즘 스터디 Week5 문자열 문자열 용어 - 문자열의 크기 표현: 문자열 $S$= "avada"이라 하면, $|S|=\ 5$ - 문자열의 $i$번째 문자: $0 \le i \lt |S|$인 $i$에 대해 $S[i]$는 $i$번째 문자. $S$="avada"이라 하면, $S[3]$ = 'd' - 부분문자열(substring): 문자열 $S$에 대해서 $i$번째 문자부터 $j$번째 문자까지로 구성한 문자열을 말한다. - 접두어(prefix): 부분문자열 중 0번째 문자부터 구성한 문자열 - 접미어(suffix): 부분문자열 중 $|S| - 1$번째 문자로 끝나게 구성한 문자열 문자열 검색 문제 - 문자열 $H$의 부분문자열 중 $N$와 같은 부분문자열들의 모든 위치를 구하는 문제 - $H$= "abbabba", $N$="bba".. ubuntu 22.04 터미널 실행 에러, apt 에러 해결 케이스 갑자기 terminal 실행이 안되기 시작했는데, 찾아보니 python link에러를 먼저 의심해야한다는 내용을 보고 IDE 내부 터미널로 접속해서 일단 terminal 실행 문제는 해결했다. 내 케이스의 경우, python --version python3 --version 으로 문제가 생긴것을 바로 알 수 있었다. 이 후 ls -al /usr/bin/python* 으로 링크가 문제가 있었는지 확인할 수 있다. 이후 링크 파일을 덮어씌워주면 된다. sudo ln -fs /usr/bin/python3.10 /usr/bin/python3 이 후, 패키지들을 업데이트 하는 과정에서 apt 에러가 나기 시작했다. (아마 파이썬 에러가 있을 때, 패키지 쪽을 업데이트하려했었기 때문에 패키지 설치 중에 버그가 났을.. 알고리즘 스터디 Week4 알고리즘 문재해결전략 리뷰 20. 문자열 문자열의 검색 짚더미(haystack) 문자열 $H$가 바늘(needle) 문자열 $N$을 부분 문자열로 가지는 부분 문자열 $N$의 $H$에서의 시작위치들을 찾아내는 것을 문자열의 검색 문제라고 한다. 가장 먼저 생각나는 방법은 $H$의 모든 위치에서 $N$을 비교하는 방법이다. std::vector NaiveSearch(const std::string& H, const std::string& N) { std::vector found; for (int begin = 0; begin + N.size() $(N-K)K$가 승부의 개수이므로 최대일 때는 $K$가 $[ {N \over 2} ]$일 때이다. - 그러면 일단, 절반($[ {N \over 2} ])으로 나누.. 알고리즘 스터디 Week3 18. 선형 자료 구조 1) 동적 배열 - 원소들은 메모리의 연속된 위치에 저장함 - 주어진 위치의 원소를 반환하거나 변경할 때 $O(1)$의 상수시간이 필요 - 배열의 크기를 변경하는 $resize()$ 연산이 가능하며, 배열의 크기 N에 대해 $O(N)$의 시간이 필요 - 주어진 원소를 배열의 맨 끝에 추가할 수 있으며, 이 때 $O(1)$의 상수시간이 필요 어떻게 구현할 지를 정리해보자. 1, 2, 3번의 조건을 달성하기 위해선 밑 코드에서 첫번째 $append()$ 함수로 가능하지만, 상수시간으로 append를 처리할 수 없게 된다. 항상, 배열의 크기 $O(N)$의 시간이 필요하다. 매번 원소를 추가할 때마다 복사를 하지 않기 위해서 두번째 $append()$와 같이 $capacity$라는 변수.. 이전 1 2 3 다음
