비트와 바이트
1.비트란 무엇인가?
-컴퓨터는 기본적으로 2진법으로 작동하는데, 그래서 우리는 메모리에 저장되는 데이터 형식에 대해서 알아보겠다.
-비트란 각 2진법으로 표현가능한 가장 작은 단위를 말한다.
| 2⁷ | 2⁶ | 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
-위와 같이 각 자리를 비트라고 한다.
2.바이트란 무엇인가?
-그렇다면 바이트란 무엇인가 하면, 각 비트가 모여 바이트를 이루는데, 8개의 비트가 모이면 1바이트라고 할 수 있다.
-"8비트 = 1바이트"라면 1바이트로 표현할 수 있는 정수는 2⁷=128개이다.
3.음의 정수는 어떻게 표현할 수 있을까?
-1바이트에서 표현가능한 정수는 128개라고 했다.
-음수는 -64부터 -1까지이고 양수는 1부터 63까지이다. 거기에 0을 포함하면 총 128개의 정수가 된다.
-음의 정수를 표현하는 방법에는 간단하다.
-12을 표현하는 방법은 다음과 같다.
-(2³ *1 + 2²*1 + 2¹*0 + 2⁰*0 = 12) 이 식을 표에 대입하면 다음과 같다.
| 2⁷ | 2⁶ | 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
-따라서 이진법을 표현했을 때 00001100 이라고 표현할 수 있다.
-그럼 12의 음의 정수는 더욱 간단하다.
-가장먼저 비트를 뒤집는다. 11110011
-그리고 1을 더해준다.
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | |
| + | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
-결과는 11110100이 된다.
-원리를 알아보면 X + -X는 0이라는 점을 이용하고, 컴퓨터가 인식 가능한 비트를 넘으면 0으로 인식한다.
-즉 00001100+11110100을 하면 1 00000000이 되는데 해당 8비트의 자리를 넘어선 1은 인식하지 못하기 때문에 가능한 원리이다.
스택
1.스택이란 무엇인가?
-자료구조의 일종으로 마치 무언가 쌓인듯 한 자료구조를 말하는데, 자료를 처리할 때 먼저 들어온 것이 나중에 처리된다.
-쉽게 얘기하면 아래가 막힌 통 을 세우고, 그 안에 폭이 같은 물체들을 넣으면, 꺼낼 때에는 나중에 넣은 순서대로 꺼내야 하는 것과 같은 말이다.
-컴퓨터에게 A의 일을 시키는 중 B의 일을 시키면 B를 시작하고 그 중에 C의 일을 시키면 C를 시작한다.
-위와 같이 일을 시키는 것을 PUSH라고 하고, 끝난 일을 빼거나 일을 제거하는 것을 POP, 가장 나중에 쌓인 일을 TOP이라고 한다.
2.스택은 어디에 이용되는가?
-인터넷 브라우저에서 뒤로가기와 앞으로 가기 버튼에서도 볼 수 있다.
-뒤로가기 스택과, 현재 페이지 스택, 앞으로가기 스택이 있다고 할 때
-A 페이지에서 B 페이지로 접속했을 때, 뒤로가기 스택에 A페이지가 PUSH된다.
-그리고 C 페이지에 또 접속하면, 뒤로가기 스택에 B페이지가 PUSH 되어 B페이지가 TOP이 된다.
-C 페이지에서 뒤로가기를 누른다면 B페이지가 로딩되고, A페이지가 TOP이 되고, C페이지는 앞으로가기 스택에 PUSH된다.
-뒤로가기 버튼을 눌렀을 때만 앞으로가기 스택에 PUSH되고, 새 페이지에 접속하면 앞으로가기 스택의 POP된다.
큐
1.큐란 무엇인가?
-스택과는 달리 먼저 들어간 것이 먼저 나오는 자료구조를 말한다.
-선입선출과 같이 영어로는 FIFO라고 한다.
2.큐는 어디에 이용되는가?
-N개의 수가 있다고 했을 때, K번째에 해당하는 수를 탈출시킨다면 각 탈출되는 수의 순서를 구하는 법과 같은 문제에 이용할 수 있다.
-8개의 수가 있고, 3번째 마다 탈출한다고 했을 때 그 순서를 구하라.
-풀이는 다음과 같은 원통을 준비한다.
| 1 2 3 4 5 6 7 8 |
-3번째에 해당하는 수를 탈출시킨다. 그리고 탈출시킨 수까지 지운다.
| 3 |
-지운 수에서 탈출시킨 수만 제외하고 다시 뒤에 붙인다.
| 4 5 6 7 8 1 2 | 3 |
-방금과 같이 또 탈출시킨다.
| 3 6 |
-위와 같이 반복한다.
| 7 8 1 2 4 5 | 3 6 |
| 3 6 1 |
| 2 4 5 7 8 | 3 6 1 |
| 3 6 1 5 |
| 7 8 2 4 | 3 6 1 5 |
| 3 6 1 5 2 |
| 4 7 8 | 3 6 1 5 2 |
| 3 6 1 5 2 8 |
| 4 7 | 3 6 1 5 2 8 |
| 7 | 3 6 1 5 2 8 4 |
| 3 6 1 5 2 8 4 7 |
-위의 풀이에 따라 3 6 1 5 2 8 4 7의 순서임을 알 수 있다.
그래프
1.그래프란 무엇인가?
-그래프는 정보와의 관계를 나타낸 자료 구조이다.
-예를 들면 먹이사슬이나. 지하철 2호선과 같은 구조를 말한다.
-그래프에서 표현하고자 하는 객체를 node라고 하고 그 각 개체들의 관계를 나타내는 선을 간선이라고 한다.
-만약 node가 간선으로 중복되지 않은 선으로 다시 원 node로 복귀할 수 있다면 사이클이라고 한다.
-만약 간선이 향하는 방향이 있는 경우 유형그래프라고 하고, 반대로 없는 경우는 무형그래프라고 한다.
트리
1.트리란 무엇인가?
-그래프 중 특수한 형태의 그래프를 트리라고 한다.
-예를 들면 가계도처럼 하나의 부모 밑에 자식이 있는 형태를 말한다.
-위의 그림처럼 제일 위에 있는 A node를 root라고 한다. 나무의 뿌리라고 볼 수 있다.
-뿌리 아래에 뻗어져있는 것은 자식이라고 한다. leaf라고 할 수 있다.
-트리는 사이클이 없고, 어떤 노드에서 출발해도 간선을 따라서 모든 노드를 갈 수 있어야 한다.
-트리의 노드 수가 n개라면 간선의 개수는 항상 n-1개 이다.
-위와 같이 부모 node 밑에 자식 node가 둘인 트리를 이진트리라고 한다.
2.이진트리 순회란 무엇인가?
-순회에는 전위 순회, 중위 순회, 후위 순회가 있다.
-전위 순회는 현재 보고 있는 노드를 출력한 뒤 왼쪽으로 내려간다. 왼쪽에 대한 출력이 전부 다 끝나면 오른쪽으로 내려가 출력한다. 출력이 다 끝나면 다시 위로 올라가고 모든 출력이 끝날 때 까지 올라간다.
(출력 -> 왼쪽 -> 오른쪽) [A B D E C F G]
-중위 순회는 가장 왼쪽으로 내려간다. 그리고 출력한 후 오른쪽을 확인하고 오른쪽이 있다면 내려가서 출력하고 다시 올라와 위의 패턴을 반복한다.
(왼쪽 -> 출력 -> 오른쪽) [D B E A C G F]
-후위 순회는 가장 왼쪽으로 내려간다. 그리고 오른쪽을 확인하고 내려갈 수 있다면 내려가고 더이상 없으면 출력하고 다시 올라와 출력한 후 다시 올라가며 자식 노드를 출력하면서 올라간다.
(왼쪽 -> 오른쪽 -> 출력) [D E B G F C A]
3.트리를 복구하려면 어떻게 해야할까?
-중위 순회를 알고 각 전위순회, 후위순회 중 하나만 알면 트리를 복구할 수 있다.
-전위 순회는 출력을 먼저한다. 따라서 루트가 가장 앞에 있다.
-후위 순회는 출력을 마지막에 한다. 따라서 루트가 마지막에 있다.
-중위 순회는 루트보다 먼저 출력되는 노드는 루트의 왼쪽에 있는 노드들이고, 루트 나중에 출력되는 노드는 오른쪽에 있는 노드들이다.
-위의 규칙을 이용해 트리를 복구하면 된다.
위의 내용은 기본 중에 기본으로 알고리즘의 설계역량을 키우기 위해 필요한 지식이다. 연습장에 풀어가며 숙달하자.
'🌌SSAFY > Computational thinking' 카테고리의 다른 글
| computational thinking_04 (0) | 2023.04.13 |
|---|---|
| computational thinking_03 (0) | 2023.04.13 |
| computational thinking_02 (0) | 2023.04.13 |
| computational thinking_01 (0) | 2023.03.30 |
