본문 바로가기

알고리즘

 (368)
[24/07/04] UCPC 2019 예선 https://www.acmicpc.net/category/detail/2053A번 - import sysinput = sys.stdin.readlineprint([1, 2, 3, 4, 5, 4, 3, 2][int(input()) % 8 - 1])B번 -좀 귀찮은 구현. 빠르게 구현하는 실력을 길러보자.# 17363번 우유가 넘어지면?# 구현import sysinput = sys.stdin.readlineN, M = map(int, input().split())translate = {'.': '.', 'O': 'O', '-':'|', '|':'-', '/':"\\", '\\':'/', '^':'', '>':'^'}mat = [list(input().rstrip()) for _ in ..
[24/07/04] Latin America Regional Contests 2022 https://www.acmicpc.net/category/detail/3579A번 - (업솔빙 예정)B번 - (업솔빙 예정)C번 - (업솔빙 예정)D번 - (업솔빙 예정)E번 - (업솔빙 예정)F번 - (업솔빙 예정)G번 -(업솔빙 예정)H번 -(업솔빙 예정)I번 -(업솔빙 예정)J번 -(업솔빙 예정)K번 -(업솔빙 예정)L번 -(업솔빙 예정)M번 -(업솔빙 예정)
[Python] 17623번 괄호 https://www.acmicpc.net/problem/17623 24/07/01  업다운 랜디를 하다가 만난 문제이다. 복습 겸 의식의 흐름대로 적어보고자 한다. 문제 접근 방식:  요구 사항은 다음과 같다. 괄호 문자열은 소괄호, 중괄호, 대괄호로 만들 수 있음.괄호 문자열은 두 괄호 문자열을 서로 Concatenate하거나 하나의 괄호 문자열을 감싸면 만들 수 있음.val함수를 통해 괄호 문자열의 값을 정수로 알 수 있음.또한 dmap함수를 통해 괄호 문자열의 값을 정수로 알 수 있음.어떤 정수 $N$이 주어질 때, $val(x) = N$이 되도록 하는 괄호 문자열 $x$를 찾는 것이 우리의 목적임.이러한 $x$가 여러 개 있다면 $dmap(x)$가 최소가 되도록 하는 것이 우리의 목적임. dma..
[Python] 3673번 나눌 수 있는 부분 수열 https://www.acmicpc.net/problem/3673 24/07/01  간단한 조합론 + 누적 합 문제이다. 업다운 랜디를 하며 풀었다. 문제 풀이 방식 자체는 간단하지만 이를 떠올리는 과정이 좋은 것 같아서 적어보고자 한다. 문제 접근 방식:  요구 사항은 연속하는 부분 수열의 합이 $d$로 나누어 떨어지는 것의 개수를 구하는 것이다.(물론 원래 수열 $A$도 주어지고, $d$값도 주어진다.) 나의 의식의 흐름은 다음과 같았다. 수열의 크기가 테스트 케이스 하나당 최대 5만 정도임. $\rightarrow$ 테스트 케이스 수는 최대 $200$임. $\rightarrow$ 둘을 곱하면 1000만정도 되므로, 하나의 테스트 케이스 당 $\mathcal{O}(N)$의 시간 복잡도로 문제를 해결해..
[Atcoder] ABC 360 A번 - A Healthy Breakfast (2:40, +, AC)'R', 'M', 'S'가 각각 하나씩 들어있는 길이 3짜리 문자열이 주어질 때 'R'이 'M'보다 왼쪽에 있으면 'Yes'를 아니면 'No'를 출력하는 문제.순간 당황했으나. 'R', 'M', 'S'로 만들 수 있는 모든 문자열의 개수는 6개 밖에 안되고, 이중 'Yes'를 만들 수 있는 문자는 'RSM', 'RMS', 'SRM' 총 3개 이므로 여기에 해당하는 문자열이라면 'Yes'를 출력하도록 하면 된다.B번 - Vertical Reading (14:11, +, AC)두 문자열 $S$와 $T$가 주어지면 $S$를 길이 $w$마다 쪼개어 배열했을 때 세로로 읽으면 문자열 $T$가 나타나는지의 여부를 판단하는 문제.살짝 까다로웠다. 체..
[Python] 13172번 Σ https://www.acmicpc.net/problem/13172 24/05/29  클래스에 있던 문제 중에 하나로, 간단한 정수론 문제이다. 문제 접근 방식:  친절하게도, 문제에 대한 답이 다음과 같이 써져있다. $$\frac{S_1}{N_1} + \frac{S_2}{N_2} + \cdots + \frac{S_M}{N_M}$$ 이를 그대로 구현해주면 된다. 이때, 답은 기약분수로 나타내야 하므로, $S_i$와 $N_i$를 입력받을 때마다, $\text{gcd}(S_i, N_i)$로 두 수를 나눠준다. 또한, 모듈로 역원은 파이썬에서는 pow함수의 지수부분에 -1을 넣음으로써 쉽게 구할 수 있으므로 이를 활용하면 쉬워진다. 아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 ..
[Python] 12070번 gNumbers (Small) / 12071번 gNumbers (Large) https://www.acmicpc.net/problem/12070https://www.acmicpc.net/problem/12071 24/05/21  스몰과 라지 풀이 방식이 거의 유사해서 같은 글로 적어보려고 한다.  문제 접근 방식:  문제 설명에 앞서서 편의 상 선공이 지는 포지션을 Cold position, 선공이 이기는 포지션을 Hot position이라고 부르겠다. 문제의 내용은 Small문제에 들어가면 wizardrabbit님이 번역해놓은 것이 있으므로 이를 참고해보자.https://www.acmicpc.net/board/view/143383 Small의 경우는 제한이 $N = 1, 000$까지이므로, DP배열을 $1,000$까지 선언하여 DP를 돌리면 된다. 이 때 어떤 숫자가 g-num..
[Python] 3878번 점 분리 https://www.acmicpc.net/problem/3878 23/10/06  이전에 볼록 껍질 문제를 쭉 푼 적이 있었는데, 그 때 해결 했던 문제 중 하나이다. 흥미로운 문제라고 생각되어 기록으로 남겨보고자 한다. 문제 접근 방식:  문제의 요구 사항은 검은 점과 흰 점을 오직 하나의 직선만으로 서로 분리할 수 있는지 판단하는 것이다. 검은 점끼리를 고무줄로 감싸고, 흰 점끼리를 고무줄로 감쌌을 때, 두 고무줄이 겹치지 않으면 가능하다고 판단했다. 여기서 볼록껍질이라는 말을 사용하지 않은 이유는 고무줄이라는 용어가 더 적합하다고 생각했기 때문이다. 볼록껍질은 고무줄이라는 말을 온전히 대변하지 않는다. 예를 들어, 두 점만 있는 경우 볼록 껍질을 정의하기가 어려운데, 고무줄은 정의할 수 있다. 한..

티스토리툴바