프로그래밍 114

[알고리즘] Codeforces Global Round 19

이번에 본대회를 참가할 수 없어서 버추얼에 참가했다. A - Sorting Parts [Solved!] 길이가 $n$인 배열이 주어질 때 $1\le i\le n-1$를 정해 $[a_1,\dots,a_i], [a_{i+1},\dots,a_n]$를 정렬하여 이어붙일 때 내림차순이 아닌 배열을 만들 수 없는지 묻는 문제이다. (오름차순이 아닌 배열을 만들 수 있는지 묻는 문제) 주어진 배열이 이미 오름차순이라면 내림차순이 아닌 배열(오름차순)을 만들 수 있다. B - MEX and Array [Solved!] 배열을 $k$개의 구간으로 적당히 나누어 $ cost = c+\sum_{i=1}^c mex(\{ b_{l_i}, b_{l_{i+1}}, \dots, b_{r_i}\}) $ 라고 하자. 배열의 모든 부분배..

[알고리즘] Codeforces Round #770 (Div. 2)

이번 코드포스의 결과는 굉장히 참담했다. 그래서 다시 그린으로 내려왔다. A - Reverse and Concatenate [Solved!] 문자열이 주어졌을 때 다음 연산을 $k$번 하여 만들 수 있는 서로 다른 문자열의 수를 구하는 문제이다. 연산은 다음중 하나를 수행한다. - 문자열을 뒤집어 원래 문자열 앞에 이어 붙인다. - 문자열을 뒤집어 원래 문자열 뒤에 이어 붙인다. 우선 연산을 한 번이라도 수행하면 문자열은 팰린드롬이 된다. 또한 팰린드롬은 뒤집어서 어디에 이어 붙여도 같은 문자열이 된다. 결국 주어진 문자열이 팰린드롬인지 확인하는 문제로 환원된다. 다만 팰린드롬에 상관없이 $k=0$일 때는 답이 1이다. A번부터 뇌절을 심하게 해서 4번틀리고 AC를 받았다. (발상이 상당히 힘들었다.) ..

[알고리즘] Codeforces Round #751 (Div. 2)

연습용으로 예전 Contest에 버추얼참가를 했다. 아쉽게도 4솔에 실패했다. A - Two Subsequences [Solved!] 문자열 $s$가 주어지고 그 문자열을 $a, b$인 두 개의 문자열로 나눌건데 $a$는 사전순으로 가장 앞서는 문자열, $b$는 $s$에서 $a$를 제외한 문자열인 조건이 있을 때 나눠진 문자열들을 출력하는 문제이다. $a$는 $s$에서 사전순으로 가장 앞서는 문자 하나이면 충분하다. 예를들어 $s = ``helloworld"$일 때 $a = ``d"$이고 $b =``helloworl"$이 된다. B - Divine Array [Solved!] 배열 $a$가 주어지고 그 배열에 연산을 여러번 하려고 할 때 $k$번 연산을 수행한 후 $x$번째 위치의 수를 묻는 문제이다. ..

[알고리즘] Educational Codeforces Round 122 (Rated for Div. 2)

버추얼에 참가했다. 이번 대회는 다른 대회보다 쉬웠던 것 같다. A - Div. 7 [Solved!] 정수가 하나 주어졌을 때 변화하는 자릿수를 최소로 하며 7의 배수로 만드는 문제이다. 7의 배수이면 그냥 출력하고 아니라면 1의 자리를 0~9까지 변화하면서 7의 배수가 되는 수를 출력한다. 자릿수를 하나만 변화시켜도 7의 배수를 만들 수 있다. B - Minority [Solved!] 이진문자열이 주어졌을 때 부분 문자열을 골라 0, 1중에 개수가 작은 문자를 전부 삭제한다.(같으면 무효) 이때 삭제한 문자의 수의 최댓값을 구하는 문제이다. 전체 문자열을 부분문자열로 선택하고 둘 중에 개수가 작은 문자의 수를 출력하면 된다. 만약 같은 경우는 갯수-1을 출력하면 된다. C - Kill the Monst..

[알고리즘] Codeforces Round #769 (Div. 2)

이번에 처음으로 Div.2 에서 3솔을 하고 민트를 갔다! 당분간 3솔이 편해질때까지 버추얼만 참가할 예정... A - ABC [Solved!] 이진 문자열의 부분문자열 중 길이가 2이상인 팰린드롬이 있는지 찾는 문제이다. 보자마자 매내처생각나서 제출하고 AC를 받았다. 끝나고 생각해보니 그냥 부분문자열 길이 2이상 3이하인 팰린드롬 찾아도 풀 수 있었다. B - Roof Construction [Solved!] $n$이 주어졌을 때 배열 $(0,1,2,..., n-1)$의 순열중 인접한 xor값의 최댓값을 최소로 하는 배열을 찾는 문제이다. 접근방법이 도저히 생각안나서 C풀고 온 후 남은 90분 B풀고 끝낼 생각으로 천천히 풀었다. 우선 $n=2$~$10$까지 모든 순열에 대해 xor값의 최댓값을 구했..

[알고리즘] 2022 중앙대학교 CHAC

문제가 그렇게 어렵지 않고 재미있는 문제들이 많아 남겨보고자 한다. (푸는대로 업데이트 할 예정..) A. 2의 보수 정수를 하나 입력받아 그 수의 2의 보수를 출력하면 된다. 입력받은 정수를 $a$라고 하면 $a \oplus (2^{32}-1) + 1$ 이 정답이다. (지난 코드포스 768에서 영감받음) B. 조커 찾기 카드 27장을 섞는 방법이 주어졌을 때 $n$번 섞고 난 후 조커($1$번 카드)가 어디있는지 찾는 문제이다. - 덱 위에서 13장을 왼쪽, 14장을 오른쪽으로 보낸다. - 배열 $a$가 있을 때 $i$가 홀수이면 오른쪽, 짝수이면 왼쪽에서 $a_i$장을 가져와 새 덱 밑에 추가한다. 문제에서 나타낸대로 구현하면 된다. 파이썬으로 큐를 사용해봤는데 시간초과가 나서 리스트 전체를 조작하는..

[알고리즘] Codeforces Round #768 (Div. 2)

코드포스에 너무 어려움을 느껴 앞으로 editorial를 보고 공부하여 블로그에 정리하고자 한다.. (Div2 2솔까지는 할만한데 3솔부터 못해먹겠다.) A - min max swap [Solved!] 두 배열 $a_1, a_2, ... , a_n$과 $b_1, b_2, ..., b_n$이 주어졌을 때 같은 인덱스들을 여러번 적절히 바꾸어 만들어진 새로운 두 배열을 만든다. 만들어진 각 배열의 최댓값을 곱했을 때 가능한 최솟값을 구하는 문제이다. $a_i, b_i$를 비교하면서 두 수중 작은 값을 $a_i$, 큰 값을 $b_i$에 넣으면 최적해가 구해진다. B - Fun with Even Subarrays [Solved!] 배열이 주어졌을 때 적당한 범위 $a_l, a_{l+1}, ..., a_r$을 정..

[도커] 9. 도커 이미지 만들기

이번시간엔 좀 더 복잡한 이미지를 만들어 Dockerfile 작성을 실습해볼 예정이다. 우선 nginx를 이용해 웹 서버를 여는 이미지를 만들어보려고 한다. FROM ubuntu:20.04 MAINTAINER riroan LABEL version="0.1" RUN apt-get update RUN apt-get install nginx -y RUN echo "\ndaemon off;" >> /etc/nginx/nginx.conf ENTRYPOINT ["nginx"] EXPOSE 80 docker build --tag mynginx:0.1 . 이렇게 나오면 성공적으로 빌드한 것이다. 우선 Step이 8/8에서 끝났는데 이는 레이어가 8개임을 의미한다. 레이어는 대문자 명령어의 개수이기 때문에 8개가 나왔다..

[도커] 8. Dockerfile 요소

지난시간에 가장 간단한 Dockerfile를 빌드해 이미지를 만들었다. 이제 Dockerfile에 어떤 내용을 써야하는지 알아보려고 한다. - FROM 기반 이미지 로드 FROM ubuntu:20.04 - MAINTAINER 개발자정보 입력(잘 사용하지 않는다. 대신 LABEL사용 추천) MAINTAINER riroan - LABEL 이미지 정보 입력 LABEL version="1.0" description="this is my image" - RUN FROM에서 로드한 이미지에서 실행할 명령이나 스크립트 RUN 명령어 사용 시 사용자와의 인터렉션이 있으면 안된다.(ex : 설치시 y/n누르는 부분) # shell 에서 RUN echo hello world # shell 없을 때 RUN ["echo", ..

[도커] 7. 가장 간단한 이미지 만들기

이번시간에 도커를 사용해서 가장 간단한 이미지를 만들어 빌드해볼것이다. 만들 내용은 우분투 이미지에 hello world 를 출력하는 이미지를 만들것이다. 우선 빈 폴더를 하나 만들어서 안에 Dockerfile라는 이름의 파일을 생성한다. (스펠링이 맞아야 한다!) 이후 Dockerfile를 편집기로 열어서 아래 내용을 작성한다. FROM ubuntu ENTRYPOINT ["echo", "hello, docker"] 스크립트 내용은 차차 알아갈 것이다. Dockerfile이 있는 폴더에서 다음 명령어를 이용해 빌드를 시작한다. docker build . 현재 위치를 빌드할 것이기 때문에 .를 입력했다. 만약 빌드하려는 도커파일이 다른 위치에 있다면 해당 위치를 .대신에 써주면 된다. 이미지가 두개 생겼는..