[백준]_2096번 : 내려가기(파이썬)
2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 비슷한 문제로는 RGB 거리 문제가 떠오른다. 전형적인 DP문제로 쉽게 풀 것이라고 생각했지만 모든 dp문제가 다 그렇듯이 문제마다 요구하는 특별한 방법이 있기 때문에 상황 파악이 우선이다. 필자는 이 문제를 풀 때 잘못된 접근을 하여 한동안 헤맸었다. 잘못된 접근 법은 아래에 정답 코드 이후에 설명하겠다. 접근 문제의 조건을 보면 N이 100000까지 커질 수 있기 때문에 2차원 dp N*3짜리를 만드는 것은 별로 효율적이지 않다. 따라서 dp리스트는 3*1짜리로만 풀 것이..
[백준]_11758번 : CCW(파이썬 and C언어)
11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 제목 그대로 ccw알고리즘 저격 문제이다. 심지어 ccw알고리즘을 구현하기만 하면 해결되는 문제이기 때문에 ccw가 무엇인지만 알고 있으면 그렇게 어려운 문제는 아니다. 질문 게시판에서 보이는 ccw를 사용하지 않은 풀이를 보니 왜 알고리즘을 공부해야 하는지 깨닫게 되었다. 전략 ccw는 Counter Clock Wise알고리즘을 뜻한다. ccw알고리즘은 복잡한 코드 대신 외적을 사용하여 세 점의..
