알고리즘
Posts
67 posts
알고리즘 응용문제 챕터 진입, 실패, 그리고 반성
어느새 탑코더 알고리즘 트레이닝 책의 마지막 단원인 응용문제 파트까지 도달했다. 블로그에 올린게 8문제, 그리고 따로 푼게 그 정도이니 한 달 치고는 꽤 많은 문제를 다뤄본 셈이다. 그런데 이 응용문제 파트, 정말 그동안 내가 뭘 했나 싶을 정도로 절망감을 안겨준다. 시도한 문제는 '바이너리 플립' 으로 디비전1의 레벨 2에 위치한 문제. 처음으로 마주치게 된 디비전 1 문제이다. 0이 쓰여진 카드가 A장, 1이 쓰여진 카드가 B장 존재한다. 각 턴에 K개를 뒤집을 때 모두 1로 만드는 것은 가능한가? 가능하다면 그 최소 턴은? 그리고 저자는 '이 문제를 제한 시간 내에 풀 수 있으면 레드 코더에 가까울 것' 이라는 말로 호승심을 불태웠다. 생각한 방법은 당연
![[TopCoder] 해밀턴 패스(Hamilton Path) 분석 및 풀이](https://img.zoomtrend.com/2017/03/30/b0057850_58dc7f6e0424f.png)
[TopCoder] 해밀턴 패스(Hamilton Path) 분석 및 풀이
* 문제 번호 * SRM452 Div2 Lv3 * 문제 유형 * 수학 * 사용 언어 * C++ * 풀이 상태 * FAIL * 소요 시간 * 6시간 * 나의 전략 * 먼저 불가능한 경우는 총 두 가지가 존재한다. 1. Y가 3개 이상 붙은 도시. 2. 1 - 2 - 3 - 1 같이 순환하는 연결. 테스트 케이스에서 제공하기에 쉽게 판별할 수 있었다. 그리고 필수적으로 가야하는 경로로 묶인 그룹을 C, 모두 NNN...으로 고립된 도시를 I라고 할 때, 찾아야하는 경로의 수가 (C + I) * 2 * I 임은 쉽게 알 수 있었다. (뒤의 2 * I 는 각 그룹이 서로 끝점으로 연결될 수 있는 가지 수) 이 떄, Y가 하나
![[TopCoder] 둥근 모양의 국가들(CirclesCountry) 분석 및 풀이](https://img.zoomtrend.com/2017/03/28/b0057850_58da2e25142bd.png)
[TopCoder] 둥근 모양의 국가들(CirclesCountry) 분석 및 풀이
* 문제 번호 * SRM443 Div2 Lv2 * 문제 유형 * 수학 * 사용 언어 * C++ * 풀이 상태 * SUCCESS * 소요 시간 * 10분 * 나의 전략 * 레벨 2의 문제 치고 너무 쉽게 풀려서 당황했던 문제. 그 흔한 함정조차 없었다. 요점은 시작점과 도착점이 '반드시' 하나의 원형 경계를 넘는 경우를 캐치할 수 있냐는 것. 아주 당연하게도, 두 점 중 하나가 원 하나의 radius 내부에 존재하고, 하나가 바깥에 존재하는 경우만 해당된다. 즉, (x-x1)^2 + (y-y1)^2
