SSAFY 준비 (3) - Computational Thinking (CT) #1

Writer: Harim Kang

Computational Thinking (CT)

Computational Thinking은 다양한 유형 중 5가지 큰 문제가 주어지며, 각 문제 마다 더 복잡해지는 5가지의 소문제로 이루어져 있습니다. 총 25문제를 30분 안에 풀어야합니다.

문제의 유형은 아래와 같은 종류의 유형들이 존재합니다.

• 이산수학
• 수열
• 자료구조
• 1차원 점화식
• 2차원 점화식
• 투 포인터
• 그리디

해당 포스팅에서는 이산수학, 수열, 자료구조, 1차원 점화식 유형에 대한 내용과 문제 유형을 다루겠습니다.

이산수학

이산수학은 컴퓨터가 사용하는 수학에 대한 유형입니다. 대표적으로 2진수, 논리연산, 비트연산, 팩토리얼, 분류 등에 대한 문제들이 있습니다.

2진수

• 2진수와 관련된 내용은 SSAFY관련 첫번째 포스팅에 설명이 되어 있습니다.
• 아래의 링크에 비트와 바이트, 2진법의 음수 표현법에 대한 내용이 있습니다.

https://davinci-ai.tistory.com/37

[알고리즘잡스] SSAFY 준비 (1) - SSAFY란? & CT Basic

논리연산

• 논리연산 구성자
  • 논리 피연산자: True, False
  • 논리 연산자: && || !
• AND(&&): A와 B가 모두 True인 경우, True를 반환합니다.
• OR(||): A 또는 B가 True인 경우, True를 반환합니다.
• NOT(!): !A는 A가 True인 경우에는 False를, False인 경우에는 True를 반환하는 연산입니다. 참 거짓을 뒤집는 연산입니다.
• 아래와 같은 순서로 풀어내시면 됩니다. 쉬운 부분이라 빠르게 넘어갑니다.

비트연산

• 비트 연산은 논리연산을 여러 비트에 적용한 것을 의미합니다.

• 비트 연산의 구성은 다음과 같습니다.

  • 비트 피연산자: 2진수
  • 비트 연산자: & | ^ ~ - << >>

• AND(&): 2진법에서 1은 True, 0은 False입니다. 2진법 수의 각 자리들을 && 연산해줍니다.

  • 1 & 1 = 1, 1 & 0 = 0, 0 & 1 = 0, 0 & 0 = 0

    

• OR(|): 2진법 수의 각 자리들에 || 연산을 해줍니다.

  • 1 | 1 = 1, 1 | 0 = 1, 0 | 1 = 1, 0 | 0 = 0

    

• XOR(^): 2진법 수에 대해 A^B는 각 빝트에 대해 서로 다른 값이 들어있는지를 판단하는 연산입니다.

  • 1^1 = 0, 1^0 = 1, 0^1 = 1, 0^0 = 0

    

• NOT(~): 2진법 수의 각 자리들에 ! 연산을 해줍니다.

  • !1 = 0, !0 = 1

    

• 음수 표현법(-): 2진법 수의 음수표현법은 NOT연산 값에 1을 더해줍니다.

• Shift 연산(<<, >>): 전체 비트를 하나씩 왼쪽 또는 오른쪽으로 옮기는 연산입니다. (그림에는 32라고 되어있지만 결과 값 64가 맞습니다. 오타 피드백: phy님 감사합니다 :D)

  

n진법

• 10진법 수를 n진법 수로 변환하는 방법

  • 10진법 수 A를 몫이 0이 될 때까지, n으로 계속 나눕니다.

  • 계산 시마다의 나머지의 역순이 n진법으로 변환된 수입니다.

    

• 문제 유형

  1. 3의 거듭제곱

     

     • 해당 문제는 3으로 계속 나눌 때 나머지가 2이상이 하나라도 나온다면 중복이 생긴다는 의미입니다.

  2. 2 to 8

     

     • 해당 문제는 맨 오른쪽 수부터 세자리 씩 묶어서 보면 편합니다. 세자리씩 묶어서 그 숫자를 10진수로 변환하면 됩니다.

       

수열

수열 문제

• 특정 기준에서 '몇 번째 값은 무엇인가'와 같은 단순한 곳에서 실수가 많이 나옵니다.

자료구조

자료구조에 대한 내용은 SSAFY관련 첫번째 포스팅에 간단한 개념들을 정리하였습니다.

스택

• 이론 & 개념

  https://davinci-ai.tistory.com/16?category=911813

• 후위 표기법 계산

  

  

파이썬으로 구현하는 자료구조 요약 정리 - 배열(Array), 큐(Queue), Stack, Linked List

 

그래프

• 이론 & 개념

  https://davinci-ai.tistory.com/37

• 그래프 문제는 순회와 관련된 문제가 많이 출제됩니다.

[알고리즘잡스] SSAFY 준비 (1) - SSAFY란? & CT Basic

1차원 점화식

동적계획법(Dynamic Programming, DP)

• 가장 앞의 수부터 순서대로 진행하면서, 이전의 위치들의 정보를 이용하여 현재의 위치 답을 구하는 방식입니다.

• 문제 유형

  

  • 문제의 풀이

    

    • 위와같이, 앞에서 계산된 최대값을 이용하여 그 상황에서 얻을 수 있는 최대값을 넣습니다.

    • 표를 완성시키면 아래와 같습니다.

      

       

SSAFY 알고리즘잡스 대비반의 교육을 통해, Computational Thinking에 관련된 다양한 문제 유형을 접할 수 있었습니다. 자료구조와 알고리즘의 기초에 대한 내용을 학습하는 것이 좋고, 특히 DP에 익숙해지는 것이 좋을 것 같습니다.