SSAFY 준비 (4) - Computational Thinking (CT) #2

Writer: Harim Kang

Computational Thinking (CT) #2

Computational Thinking은 다양한 유형 중 5가지의 큰 문제가 주어집니다. 총 30분안에 큰 5문제(총 25문제)를 해결해야 합니다.
이산수학, 수열, 자료구조, 1차원 점화식 일부분에 대한 내용은 앞선 포스팅에 있습니다.

1차원 점화식

지난 포스팅에 이어서 1차원 점화식을 사용하는 이론, 문제 유형에 살펴보겠습니다.

부분수열

• 길이가 n인 수열이 있을 때, 수열을 구성하는 수들의 순서를 유지한 채로 부분적으로 얻을 수 있는 수열을 부분수열 이라고 합니다.
• 예를 들어 1 3 4 2라는 수열이 있을 때, 1 4 2 나 3 2 는 해당 수열의 부분 수열이지만, 1 2 3은 순서가 바뀌므로 부분 수열이 아닙니다.

LIS(Longest Increasing Subsequence)

• 가장 긴 증가하는 수열은 부분 수열 중에, 증가 수열이면서 가장 긴 수열을 의미합니다.

• 이것의 길이를 구하는 문제가 나올 수 있습니다.

• 예를 들어 1 3 4 2라는 수열이 있을 때, [1, 3], [1, 4], [3, 4], [1, 2]가 길이가 2인 LIS입니다.

• 예를 들어 1 3 2 4라는 수열이 있을 때, LIS는 [1, 3, 4], [1, 2, 4] 두개가 나옵니다.

• 문제 유형

  • LIS

    

  • 가장 큰 증가하는 부분 수열

    

부분 문자열

• 어떤 문자열의 부분 문자열은 문자의 순서를 유지하면서 문자열에 속하는 부분적인 문자열을 의미합니다.
• 예를 들어 abdc에서 bc는 부분 문자열이며, cd는 부분 문자열이 아닙니다.

LCS(Longest Common Subsequence)

• 가장 긴 공통 문자열은 문자열 A와 B가 주어질 때, A의 부분 문자열 이면서, B의 부분 문자열인 문자열 중 가장 긴 문자열을 의미합니다.

• 해당 문자열의 길이를 찾는 문제가 나올 수 있습니다.

• 예를 들어 abcdc 와 adcb의 공통 부분 문자열은 [a], [a, c], [a, d], [a, b], [a, d, c]가 있습니다. 이 중 가장 긴 공통 문자열은 [a, d, c]입니다.

• 문제 유형

  • LCS

    

2차원 점화식

동적계획법

• 2차원 점화식은 1차원 점화식과 달리 여러줄의 표를 사용하는 방법을 사용합니다.

• 문제 유형

  • 강의 선택

    

투 포인터

• 투 포인터란 배열 또는 수열이 존재할 때, start와 end를 지정하는 포인터를 두는 것을 의미합니다.

• 투 포인터를 이용하여 특정 조건을 만족하는 범위를 찾는 문제를 풀 수 있습니다.

• 또한, 특정 조건을 만족하는 두 수를 찾는 문제를 풀 수 있습니다.

• 풀이 방식

  

  • 위의 방법과 같이 s, e라는 두 개의 포인터를 조건에 맞춰 움직이면서 답을 찾고 s, e가 같게 되거나 교차하면 멈추는 방식입니다.

• 문제 유형

  • 중복 없는 구간

    

  • 연속된 소수의 합

    

    

    위의 표를 작성한 후, 33의 갯수를 찾아주면 됩니다. 답은 0입니다.

슬라이딩 윈도우

• 투 포인터와 유사합니다. 투 포인터와 다른 점은 s와 e 두 포인터간의 거리를 유지한다는 점입니다.

• 구간의 길이가 주어지는 문제의 경우 슬라이딩 윈도우 문제입니다.

• 문제 유형

  • 부분 수열의 합

    

    

그리디

그리디 알고리즘

• 욕심쟁이 알고리즘이라고도 불리는 그리디 알고리즘은 현재의 상태에서 가장 최선의 선택을 따라가는 알고리즘입니다.

• 문제 유형

  • 비트변환

    

SSAFY 알고리즘잡스 대비반 교육을 통해, Computational Thinking에 관련된 다양한 문제 유형을 접할 수 있었습니다. 오늘 포스팅에서는 교육의 일부 문제에 대한 풀이 만을 포함하였습니다. 교육에서는 더 다양한 문제 유형과 풀이를 접하실 수 있습니다.

해당 포스팅의 문제 풀이 이미지들은 제가 직접 작성한 이미지들입니다.