본문 바로가기

구현

 (72)
[Python] 30959번 앙상블할래? https://www.acmicpc.net/problem/30959 24/05/14  간단한 브루트포스 문제다. 파이썬은 이러한 문제에 있어서 쉽게 구현을 할 수 있어서 좋은 것 같다. 문제 접근 방식:  $N$의 제한이 $16$까지이고, 항상 홀수 개의 모델만 선택한다고 했으므로 전수조사를 해도 충분히 시간안에 들어올 수 있음을 생각할 수 있다. 하나의 조합을 통해 앙상블을 구성하는 것은 조합의 크기와 예측 항목의 개수를 곱한 크기에 비례함을 확인할 수 있다. 그 수가 그렇게 많지 않으므로, 모든 조합을 확인해보면 된다. 파이썬의 itertools 모듈의 combinations함수를 사용하면 n개 중 r개를 선택하는 모든 조합의 경우들을 확인할 수 있으므로, 이를 사용하여 쉽게 구현할 수 있다. 인덱스..
[Python] 31462번 삼각 초콜릿 포장 (Sweet) https://www.acmicpc.net/problem/31462 24/05/14  업다운 랜디를 하다가 만난 문제로, 간단하게 그리디적 발상 + 살짝 귀찮은 구현을 요구하는 문제이다. 문제 접근 방식:  그림을 잘 관찰해보면, 빨간색 모양의 초콜릿은 뾰족한 부분이 위에 올라와있고, 파란색 모양의 초콜릿은 뾰족한 부분이 밑으로 내려와 있음을 확인할 수 있다. 따라서 위에서부터 아래로, 왼쪽에서부터 오른쪽으로 탐색을 진행할 때, 아직 발견하지 않은 빨간색 초콜릿을 발견한다면, 이는 빨간색 초콜릿의 뾰족한 부분이라고 결론 지을 수 있다. 마찬가지로, 똑같은 방법으로 탐색을 진행할 때 아직 발견하지 않은 파란색 초콜릿을 발견한다면, 이는 파란색 초콜릿의 평평한 부분이라고 결론 지을 수 있다. 따라서, 배열을..
[Python] 28692번 선형 회귀는 너무 쉬워 2 https://www.acmicpc.net/problem/28692 28692번: 선형 회귀는 너무 쉬워 2 주어진 점이 $(7, 32)$, $(18, 67)$, $(40, 137)$이므로, $n = 3$, $S_x = 65$, $S_y = 236$, $S_{xx} = 1\,973$, $S_{xy} = 6\,910$이다. 즉, $a_2 = \frac{3 \times 6\,910 - 65 \times 236}{3\times 1\,973 - {65}^2} = \frac{5\,390}{1\,694}=\frac{35}{11} www.acmicpc.net 23/08/21 선형 회귀는 너무 쉬워 시리즈의 두 번째 문제이다. 얼핏 보면 어려운 문제일 것 같지만, 문제만 잘 읽으면 쉽게 해결할 수 있다. 문제 접근 방..
[Python] 2608번 로마 숫자 https://www.acmicpc.net/problem/2608 2608번: 로마 숫자 첫째 줄과 둘째 줄에 하나씩 로마 숫자로 표현된 수가 주어진다. 입력된 각 수는 2000 보다 작거나 같고, 두 수의 합은 4000보다 작다. www.acmicpc.net 24/02/27 단순한 구현 + 문자열 문제이다. 사소한 실수로 두 번 정도 틀렸습니다를 받았다. 문제 접근 방식: 문제에서 요구하고자 하는 것은 로마 숫자로 주어진 두 수를 더하고, 그 결과를 하나는 아라비아 숫자로, 하나는 로마 숫자로 출력하는 것이다. 문제를 읽던 도중 생각난 방법은 아라비아 숫자와 로마 숫자 사이의 일대일 대응 표를 만들어서 각 자리 숫자 별로 매칭을 시키면 충분할 것이라는 방법이었다. 마침 문제 제한을 보았고, 두 수가 모..
[Python] 23309번 철도 공사 https://www.acmicpc.net/problem/23309 23309번: 철도 공사 첫 번째 줄에 공사를 시작하기 이전에 있는 역의 개수를 나타내는 양의 정수 $N$과 공사 횟수를 나타내는 양의 정수 $M$이 주어진다. ($1 \le N \le 500\,000$, $1 \le M \le 1\,500\,000$) 두 번째 줄에는 공사 www.acmicpc.net 24/02/13 파이썬으로 해결하기 정말 힘든 문제로, C++을 사용할 수 있는 사람이라면 웬만해서는 C++로 해결하기를 권장하는 문제다. 주어진 그대로 잘 구현을 했음에도 불구하고 여러 기술들을 활용해야만 시간 초과를 면할 수 있다. Python3로는 통과한 사람이 없는 것으로 보아, Pypy를 사용해야만 풀 수 있는 문제로 보인다. 문..
[Python] 17504번 제리와 톰 2 https://www.acmicpc.net/problem/17504 17504번: 제리와 톰 2 $$ 1 - \cfrac{1}{2 + \cfrac{1}{7 + \cfrac{1}{1 + \cfrac{1}{8}}}} = 1 - \cfrac{1}{2 + \cfrac{1}{7 + \cfrac{8}{9}}} = 1 - \cfrac{1}{2 + \cfrac{9}{71}} = 1 - \cfrac{71}{151} = \cfrac{80}{151} $$ www.acmicpc.net 24/01/24 수학에 구현을 덧붙인 재미있는 문제다. 말로는 설명하기 힘들어 예시를 하나 직접 따라가 보면 쉽게 이해할 수 있다. 문제 접근 방식: 제리가 훔쳐간 치즈의 무게만 구하면 톰이 가지고 있는 치즈의 무게를 구할 수 있다. $a_1,..
[Python] 2290번 LCD Test https://www.acmicpc.net/problem/2290 2290번: LCD Test 첫째 줄에 두 개의 정수 s와 n이 들어온다. (1 ≤ s ≤ 10, 0 ≤ n ≤ 9,999,999,999)이다. n은 LCD 모니터에 나타내야 할 수 이며, s는 크기이다. www.acmicpc.net 24/02/04 좀 귀찮은 구현 문제로, 침착하게 구현하면 맞을 수 있는 문제이다. 문제 접근 방식: 문제의 요구 사항은 꽤나 명확한 편이다. 숫자의 크기가 주어지고, 이 크기를 가지는 숫자를 그대로 출력하면 된다. 나는 숫자 하나와 그 크기를 입력 받아 그 크기를 가지는 숫자를 리스트로 반환하는 함수를 구현했다. 아래 코드를 보면 알 수 있듯, $8$의 경우는 모든 세그먼트가 다 켜진다고 간주할 수 있기 때..
[Python] 4659번 비밀번호 발음하기 https://www.acmicpc.net/problem/4659 4659번: 비밀번호 발음하기 좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtp www.acmicpc.net 24/01/13 살짝 구현량이 있는 구현 문제이지만, 문제에서 요구하는 것을 그대로 구현하면 쉽게 해결할 수 있는 문제다. 문제 접근 방식: 문제에서 요구하는 세 가지 조건을 판단해야 한다. 첫번째, 모음을 포함하고 있을 것. 두 번째, 모음 3개 또는 자음 3개가 연속으로 오면 안 될 것. 세 번째, 같은 글자가 연속으로 두 번 오면 안 될 것, 다만 'ee'나 'oo'는 예외다. 이 세 ..

티스토리툴바