구사과

알고리즘 하시던 분들을 현실에서 만나게 되면 자주 듣는 질문이 "왜 ID가 구사과인가" 라는 질문이다. PS를 시작한 것은 고등학교 때지만 "컴덕후" 로 살던 초등학생 시절이 있었다. 2008년 집에서 새로 산 (보급형) 컴퓨터에 윈도우 비스타가 깔려 있었는데, 잘 알려졌다시피 비스타는 새 컴퓨터에서 돌리기에도 조금 많이 느렸다. 이 문제를 해결하기 위해 유출된 윈도우 7 비공개 베타를 주워서 설치했고, 신세계가 열렸다. 컴덕후 생활의 시작이었다. 시간이 지났고 그때 활동하던 커뮤니티에서 윈도우 8에 대한 이야기가 돌기 시작했다. "플랫 UI" 라는 미명하에 등장한 추태는 초등학생인 나에게 큰 상처를 남겼다. 이것이 미래라면 나는 도망치겠다고, 2달 동안 밥만 먹고 컴퓨터를 붙잡은 끝에 OS X Snow..

Example 1 (https://koosaga.com/319 마지막 단락) 그래프가 주어질 때 이 그래프의 maximal independent set 을 구하는 문제를 생각해 보자. maximal independent set은 maximum independent set을 approximate할 수 없다. 하지만 maximal matching과 $\Delta+1$ edge coloring을 구하는 데 사용할 수 있고 이들은 각각 그들의 optimal variant의 constant approximation이다. 다음 과정을 정점이 1개 이상일 때까지 반복하면 된다: 각 노드에 $[0, 1]$ 사이의 random real을 배정한다. 이를 $r(v)$ 라고 하자. 만약 어떠한 노드에 대해 $\max_{w ..

PA 2016. Shuffle 문제에서 주어진 셔플 연산은 카드 덱을 뒤집는 연산과 동일합니다. 이 사실은 수학적 귀납법으로 증명 가능합니다. $2$ 개의 카드에 대해서는 자명히 뒤집는 연산과 동일합니다. $2^k$ 개의 카드에 대해서는, 덱을 절반으로 나눈 후 각각을 뒤집고 둘의 순서를 바꾸는 것이니, 이 역시 뒤집는 연산과 동일합니다. 카드 덱을 두번 뒤집는 건 아무것도 안하는 것과 동일하니, $t$ 가 홀수일 때 배열을 뒤집은 후 출력해 주면 됩니다. ROI 2022 P5. Максимизация выигрыша 입력으로 주어진 문자열의 길이가 $19$ 이하일때만 문제를 해결할 수 있어도 됩니다. 만약 맨 앞 문자가 전체 문자열의 최댓값이 아닐 경우, 가장 가까운 최댓값을 맨 앞 문자로 옮깁니다. ..