computational thinking_02

1.수열

-수열 문제는 어떤 수열을 만드는 규칙이 주어진다. 이 규칙을 통해 수열을 만들 때, "~번째 값은 무엇인지" 혹은 "~번째까지 중 ~한것은  몇 개 있는지" 등을 물어보는 문제가 나온다.

-해결과정은 조합과 비슷하게 한번에 묶을 수 있는 것들을 최대한 묶어서 처리하는 것이다.

ex) 10 부터 12개의 수를 적었다고 한다면, 마지막 수는 21일까? 22일까? 23일까?

정답은 21이다. 시작하는 수를 포함하여 계산해야 하기 때문인데, 이런 사고가 전제 되어야 풀이를 빠르게 시작할 수 있다.

 

2.스택

-나중에 들어간 것이 먼저 나온다.

3.그래프 순회

-그래프는 노드와 간선으로 이루어진 자료구조를 말한다.

-각 객체르 노드라고 하고 노드를 잇는 선을 간선이라고 한다.

-각 노드를 잇는 간선을 통해 이동할 때, 중복되지 않는 간선을 따라 이동해 처음 노드로 돌아오면 그것을 사이클이라고 한다.

4.1차원 단순점화

-DP : dynamic programming (동적계획법)

-가장 앞의 수부터 마지막 수까지 순서대로 보면서 이전 위치들의 정보를 이용해 현재 위치까지의 정답을 구한다.

ex)

이전까지의 정보들을 보니 현재 위치는 정답이 된다./안된다.

이전까지의 정보들을 보니 현재 위치까지의 최댓값은 ~이다.

이전까지의 정보들을 보니 현재 위치로 오는 경우의 수는 ~이다.