SSAFY 준비 (1) - SSAFY란? & CT Basic

 

Writer: Harim Kang

SSAFY란?

• 삼성 청년 소프트웨어 아카데미를 의미합니다.
• 삼성의 SW 교육 경험과 고용노동부의 취업 지원 노하우를 바탕으로, 취업 준비생에게 SW 역량 향상 교육 및 다양한 취업지원 서비스를 제공하여 취업에 성공하도록 돕는 프로그램입니다.

https://www.ssafy.com/ksp/jsp/swp/swpMain.jsp

삼성 청년 SW 아카데미

• SSAFY 통과를 위해서는 지원 테스트를 치루어야합니다. 우수한 성적을 받으면 면접으로 갈 수 있습니다.

SSAFY 시험 문제 구성

1. 수리/추리 논리
   • 문항 수: 15문제
   • 시간: 30분
   • 예상 유형
     • 응용수리: 5문제
     • 자료분석: 4문제
     • 논리추리: 6문제
2. Computational Thinking
   • 문항 수: 큰 문제 5문제, 각 문제 당 5개의 서브 문제 (총 25문제)
   • 시간: 30분
   • 예상 유형
     • 동적계획법: 1차원 단순 점화식
     • 그리디
     • 비트연산, 수열
     • 투포인터

Computational Thinking 기초 개념

• 단어 그대로 컴퓨터적인 사고 연산을 의미합니다.
• 개발자로서 구현을 하기위해서는 컴퓨터와의 대화가 필요합니다. 생각하는 것을 구현하기 전에 해야할 일이 바로 생각하는 것을 컴퓨터가 이해할 수 있는 구조로 바꾸는 것입니다.
• 오늘의 포스팅에서는 Computational Thinking의 기초적인 개념들에 대해서 설명하고자 합니다. 각 자료구조별로 간단한 문제 유형에 대한 설명이 있습니다. 풀이에 대한 내용은 간단하게 말로 설명하고 넘어가겠습니다.

자료구조

1. 비트연산
2. 스택
3. 큐
4. 그래프
5. 트리

비트연산

• 컴퓨터의 언어는 0과 1로 구성되어 있습니다. 이 언어를 이해하기 위해서는 비트와 바이트의 개념과 표현, 연산을 아셔야합니다.

비트와 바이트

• 컴퓨터는 2진법을 사용합니다.
• Bit(비트) : 0과 1 하나만 표현하는 가장 작은 단위 (2가지 수 표현 가능)
• Byte(바이트) : 비트 8개를 하나로 묶은 단위 (2^8 = 256가지의 수 표현 가능)
• 절반은 음의 정수, 절반은 0과 양수를 표현 가능합니다.
• 정수 하나 = 4 Byte (2^32 = 약 42억 수 표현)
  • -128~+127 표현 가능

2진법 음수 표현법

• 0에서 원하는 수의 양수를 뺀것이 해당 수의 음수 표현입니다.
• 양수를 음수로 바꾸는 순서는 아래와 같습니다.
  1. 비트를 다 바꾸어줍니다. 0을 1로, 1을 0으로 바꾸어줍니다.
  2. 바꾼 비트에 0000 0001을 더해줍니다.

스택(Stack)

• 스택은 push와 pop으로 요소를 넣거나 뺄 수 있으며, 후입선출(LIFO)입니다.
• 스택의 개념에 대한 내용과 파이썬을 이용한 구현은 아래의 포스팅에 정리되어 있습니다.

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

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

• 살펴볼 기본적인 유형은 인터넷 브라우저입니다.

인터넷 브라우저

인터넷 브라우저는 뒤로 가기 또는 앞으로 가기 기능, 새로운 페이지를 여는 기능 등을 제공합니다. 간단하게 앞의 3개의 기능을 스택과 함께 생각해 볼 수 있습니다.

• 페이지가 스택에 들어가는 요소라고 생각해봅시다.
• 뒤로 가기 기능을 구현하기 위해서 2개의 스택이 필요합니다.
• prev 스택 : 뒤로 가기에 사용하는 스택
• next 스택 : 앞으로 가기에 사용하는 스택
• 순서는 다음과 같습니다.
  1. 새로운 페이지 접속 시, prev 스택에 기존의 페이지를 push하고, next 스택은 비웁니다.
  2. 뒤로 가기 버튼을 누르는 경우, 현재의 페이지는 next 스택에 push 하고, prev 스택의 top 페이지를 pop하여 가져옵니다.
  3. 앞으로 가기 버튼을 누르는 경우, 현재 페이지를 prev 스택에 push 하고, next 스택의 값을 pop합니다.
• 문제의 예시로 사이트의 이동과정이 나열된 후, 마지막 페이지를 답으로 적는 문제가 나올 수 있습니다.

큐(Queue)

• 큐는 enqueue(또는 push)와 dequeue(또는 pop)을 통해서 요소를 넣거나 뺄 수 있으며, 선입선출(FIFO)입니다.
• 큐의 개념에 대한 내용과 파이썬을 이용한 구현은 아래의 포스팅에 정리되어 있습니다.

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

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

• 살펴볼 기본적인 유형은 원형 테이블입니다.

원형 테이블

• n명의 사람이 원형 테이블로 앉아있을 때, 1번 사람부터 원에서 나가고, 나간사람으로부터 k번째 사람이 차례대로 나가는 문제입니다.
• 예를 들어서 n=8, k=3일 때, 1 - 4 - 7 - 3 - 8 - 6 - 2 - 5 순서대로 나가는 것을 찾으면 됩니다.
• 큐를 이용하여 하는 방법이 있지만, 숫자를 적어놓고 하나씩 지워가는 방법이 더 빠른거 같습니다.
• 참고로 큐를 이용한 방법은 처음부터 뽑고, 기록하고, k개 만큼씩 뽑아서 마지막 것을 기록하고 나머지는 push하는 방식을 반복하는 방법입니다.

그래프

• 그래프는 정보들 사이에 관계가 있는 자료구조입니다.
• 방향의 유무에 따라, 두가지 그래프가 있습니다.
  • 유향 그래프: 방향이 존재하는 그래프
  • 무향 그래프: 방향이 존재하지 않는 그래프
• Cycle: 같은 간선을 두번이상 지나지 않고 돌아올 수 있는 경우를 사이클(Cycle)이라고 합니다. 다양한 문제에서 이 사이클을 이용하는 경우가 많습니다.

구슬크기

• 무게가 다른 n개의 구슬이 있을 때, k번의 구슬 두개씩의 크기 대소 비교 측정 결과가 주어집니다. 이때, 자신이 몇번 째로 무거운 구슬인지를 아는 구슬의 수를 구하는 문제입니다.
• 그래프로 각 번호의 구슬을 연결시켜서 해결할 수 있습니다.

트리

• 트리는 그래프 종류의 하나로, 전체가 모두 연결되어 있고, 사이클이 존재하지 않는다는 특징을 가진 그래프입니다.
• 용어 설명
  • Node: 트리를 구성하는 각각의 정보(요소)입니다. 위의 그림에서는 원들이 모두 노드입니다.
  • Root: 트리에는 계층이 존재합니다. 가장 높은 곳의 노드를 루트라고 부릅니다.
  • Edge: 각각의 노드들의 관계를 간선으로 이은 것을 엣지라고 부릅니다.
  • 노드 수가 n개 일 때, 간선(Edge)의 개수는 n-1개 입니다. (루트를 제외한 나머지 노드들이 위로 향하는 간선을 가지기 때문입니다.)
  • 이진 트리: 각각의 노드가 최대 두개의 자식 노드를 가지는 트리 구조를 의미합니다.

이진트리 순회

순회는 각각의 트리를 돌면서 출력한다는 의미입니다. 기본적으로 왼쪽부터 순회를 진행합니다. 순회 시, 출력을 먼저하냐 나중에 하냐에 따라서 전위 순회, 중위 순회, 후위 순회의 세가지 종류가 있습니다.

• 전위 순회

  

  • 해당 위치의 노드를 먼저 출력하고, 왼쪽-오른쪽 순서로 순회를 진행하는 것을 의미합니다.

• 중위 순회

  

  • 해당 위치의 노드에서 왼쪽 자식 노드가 존재하면 먼저 이동합니다. 왼쪽 자식 노드가 없으면 현재의 노드를 출력합니다.

• 후위 순회

  

  • 왼쪽과 오른쪽이 먼저 출력하였을 때, 자신을 출력하는 순서로 순회를 합니다.

트리 복구

• 문제에서는 중위 순회 결과와 전위 또는 후위 순회 결과를 주고 나머지 순회 결과를 묻거나 그래프를 그리는 문제가 가능합니다.

• 단서 얻기

  1. 전위 순회 결과에서 얻는 단서

     

     • 전위 순회의 경우, 맨 앞의 노드가 바로 루트입니다.

  2. 후위 순회 결과에서 얻는 단서

     

     • 후위 순회의 경우, 맨 뒤의 노드가 바로 루트입니다.

  3. 중위 순회 결과에서 얻는 단서

     

     • 중위 순회 출력을 통해서 각 노드들의 상대적인 위치를 확인 할 수 있습니다.

• 이를 이용하여 세가지 중 중위를 포함한 두가지 순회 결과를 알 때, 나머지 하나의 순회 결과 또는 그래프를 찾을 수 있습니다.

SSAFY 알고리즘잡스 대비반의 교육을 통해, 다양한 문제 유형을 접할 수 있었습니다. 물론 첫날이라, 전공 공부시에 배웠던 것들을 복습하는 기분이었지만, 문제 유형을 접하고, 꿀팁을 들을 수 있었습니다. 관련된 포스팅 꾸준히 업로드 하겠습니다.

//2020.05.13 기준 SSAFY 관련 글 추가

2020/04/19 - [IT/SSAFY공부] - [알고리즘잡스] SSAFY 준비 (2) - 수리/추리논리

[알고리즘잡스] SSAFY 준비 (2) - 수리/추리논리

2020/04/27 - [IT/SSAFY공부] - [알고리즘잡스] SSAFY 준비 (3) - Computational Thinking (CT) #1

[알고리즘잡스] SSAFY 준비 (3) - Computational Thinking (CT) #1

2020/05/04 - [IT/SSAFY공부] - [알고리즘잡스] SSAFY 준비 (4) - Computational Thinking (CT) #2

[알고리즘잡스] SSAFY 준비 (4) - Computational Thinking (CT) #2

2020/05/12 - [IT/SSAFY공부] - [알고리즘잡스] SSAFY 준비 (5) - SSAFY 4기 모집 안내 & 시험 준비

[알고리즘잡스] SSAFY 준비 (5) - SSAFY 4기 모집 안내 & 시험 준비