분류 전체보기(90)
-
2022/02/04 PS 일지.
코포 버추얼을 돌렸다. -Codeforces Round #377 (Div. 2) 푼 BOJ 목록 -7-세그먼트 디스플레이 -색깔 하노이 탑 음... 아직 부족한 것 같다. 내일은 시간이 더욱 부족하니까 1버추얼과 백준 1문제 하는 걸 목표로 하자.
2022.02.05 -
BOJ 18122 : 색깔 하노이 탑
문제 링크 그림을 그리면서 관찰을 해보자. 먼저 n번째 원판들이 1->3으로 갈 때 옮기는 횟수는 n=1일 경우 3, n>1일 경우 2^(n+1)임을 알 수 있다. 그렇다면 이를 n번째 원판들까지 있다고 할 때 옮기는 총 횟수를 식으로 나타내보자. 2^(n+1)+2^n+2^(n-1).....+2^3+3 = 2^(n+1)+2^n+2^(n-1).....+2^3+2^2+2^1+2^0-4 = 2^(n+1)+2^n+2^(n-1).....+2^3+2^2+2^1+2^0+1-5 = 2^(n+2)-5 가 된다. 이제 이걸 계산해주면 되는데, 아주 큰 수를 계산한 나머지를 요구한다. 큰 수 계산, 거듭제곱 계산에는 Python이 더 유리하므로 파이썬으로 풀었다. C++로 한다면, n의 최대가 10^6이므로 그냥 O(n)으..
2022.02.05 -
BOJ 18118 : 7-세그먼트 디스플레이
문제 링크 이는 dp로 풀 수 있다. dp(i,j) = i개의 디스플레이로 만들어졌으면서, m으로 나눈 나머지를 j인 수 중 최대인 수 라고 정의하면 dp(i, (10*j+k)%m) = max(10*dp(i-1,j)+k) (0
2022.02.05 -
[2일차] Codeforces Round #377 (Div. 2)
결과는 이렇다. A. Buy a Shovel (-, 00:03) 단순한 브루트 포스이다. 이때 i=1부터 n*i을 10으로 나누었을 때 나머지가 0이나 r면 그게 답이다. 답이 얼마 안되므로 상수 시간 안에 해결 할 수 있다. 코드 B. Cormen - The Best Friend Of a Man (-, 00:08) 인접한 두 칸을 더하면서, 만약 그게 k보다 작다면 뒷칸을 인접한 두 칸의 합이 k와 같게 만든다. 뒷칸을 증가시키는 건 다음 두 칸을 볼 때 그 두 칸의 합에 영향을 미치기에 그렇다. 이건 O(n)으로 구할 수 있다. 코드 C. Sanatorium (-, 00:32) 내가 푼 방식은 원래 이렇지 않지만, 끝나고 찾은 풀이가 훨씬 간단하기에 이 풀이를 쓸 것이다. m = max(b,d,s)라..
2022.02.05 -
[1일차] Educational Codeforces Round 68 (Rated for Div. 2)
내가 처음으로 코포를 쳤던 라운드를 쳤다. 결과는 이렇다. A. Remove a Progression (-, 00:01) 문제의 그림을 참고해서 잘 관찰하면, 답은 무조건 2x임을 알 수 있다. 답은 쿼리당 O(1)만에 구할 수 있다. 코드 B. Yet Another Crosses Problem (-1, 00:15) 각 행과 열에 대해 '.'의 갯수를 세준 다음, 모든 행과 열 중 하나씩 골라서 '.'의 갯수의 최소를 구해준다. 이때 행과 열의 교차점에 '.'이 있을 수 있으므로 그때는 1을 빼준다. 이는 O(nm)만에 구할 수 있고, nm=fr(t)를 만족해야 한다. -p에 있는 문자를 t랑 비슷하게 만들기 위해 s에 끼워넣을 때, 다 끼워넣은 후 s=t를 만족해야 한다. 이는 각 쿼리당 O(|p|)로..
2022.02.04 -
2022/2/2 - 내가 앞으로 PS를 공부할 방법
내가 다른분들의 도움을 받아서 작성한 방법이고, 내가 이렇게 하는 방법이 PS공부를 하는데 있어서 무조건 정확한 답은 아니라는걸 미리 말한다. -구현 문제 https://www.acmicpc.net/workbook/view/2771 https://www.acmicpc.net/problem/15949 https://www.acmicpc.net/problem/15898 필자는 구현이 특히 약하다. 구현하다가 뇌절하는 경우가 꽤 많으니 구현할때 순서도 같은 거 쓰면서 하자. -알고리즘 부족 문제 요즘 드는 생각이 필자가 알고리즘을 자세히 이해하고 넘어가지 않고 무조건 문제만 풀려고 하는게 있는 거 같다는 거다. 그러니 다음 항목들을 실천하자. =알고리즘 복습으로 해당 알고리즘에 관한 문제 풀기. 그리고 정해가..
2022.02.02