Category: Algorithm

2018
0
DevelopmentAlgorithm

[책 후기] Hello Coding 그림으로 개념을 이해하는 알고리즘

책 표지 짧은 후기표지는 정말 유치해보이긴 했지만 그림으로 개념을 이해한다는 것이 마음에 들어 읽게 됐다.그동안 공부했었던 알고리즘을 다시 복습할 수 있었고, 새롭게 알게된 알고리즘들도 있었다.확실히 그림으로 설명되어있어서 이해하기 편했다. 하지만, 초보자 입문용이다 보니 내용을 깊게 다루지는 않아서 아쉽긴 했다. 그래도 책에서 다루지 못한 다양한 알고리즘

0
DevelopmentAlgorithm

ACMICPC - 계단 오르기(2579)

계단 오르기 스티커 문제와 비슷한 느낌이다. 해당 계단을 포함해서 오르느냐 안오르냐로 나누어서 생각했다. 만약 N번째 계단을 선택하지 않는다면 2칸을 한번에 건너뛸 수 없으므로 N-1번째 계단은 반드시 선택해야 한다. N번째 계단을 선택한다면 이렇게 두 가지 경우가 있다. N-1번째 계단을 오르고, N-2번째 계단을 오르지 않아야 한다. (연속된 세 개의

0
DevelopmentAlgorithm

ACMICPC - 가장 긴 증가하는 부분 수열(11053)

가장 긴 증가하는 부분 수열 문제가 점점 어려워진다. 으악.. 여러가지 시도해보았지만 오답이 많았다.. 일단 풀이 방법만 적어 놓겠다. D[N]에는 처음부터 N번째 까지의 값들 중 가장 긴 증가하는 부분 수열의 길이를 담기로 했다. 그 다음 D에 담겨있는 값중 최대값을 결과로 출력하면 된다.기본값은 자기 자신만 있을 때의 길이인 1이다. D[N]에는 처음부

0
DevelopmentAlgorithm

ACMICPC - 스티커(9465)

스티커 어.. 진짜 고민 많이했던 문제였다. 그리디로 하면 분명 안될 것 같고 계속 최선의 방법을 남겨두면서 풀어야 하는게 아닐까 고민했다. 여러 삽질이 있었지만 이번 풀이에 사용한건 한줄씩 자르고 각 상태 3가지를 정의해줬다. N 열 N 열 N 열 0번째 행 X O X 1번째 행 X X O 상태 0 1 2 그러면 N열에 있는

0
DevelopmentAlgorithm

ACMICPC - 2×n 타일링(11726)

2xn 타일링 고3때 수업시간에 봤던 문제다. 그때는 수업시간에 DP는 이해하지 못하고 넘어갔었는데.. 아마 확통 배우던 참이라 시그마와 조합을 이용해서 엄청 복잡하게 생긴 공식을 만들어서 풀었던것 같은 기억이 있다. 이 문제 말고도 오늘은 쉬운 DP문제들을 여러개 풀어봤는데 어떻게 문제를 작게 쪼개고 패턴을 찾느냐가 중요한 것 같았다. 이 문제의 경우는

0
DevelopmentAlgorithm

ACMICPC - 에디터(1406)

에디터 처음에 이 문제를 보았을때 가장 문제가 되었던건 문자열 중간에 문자를 추가, 삭제하는 연산이었다.입력받는 문자열의 최대 길이가 10만이고 명령어가 최대 50만개 들어올 수 있는 상황이라 O(N)이 걸리는 추가/삭제 연산때문에 시간 초과가 뜰 것 같았다. 처음에 짰던 소스는 이랬다. first.py123456789101112131415161718192